Integer programming in SciPy - Mini Project: Build & Apply

Integer Programming with SciPy

📖 Scenario: You are managing a small factory that produces two products. Each product requires a certain amount of resources, and you want to maximize your profit. However, you can only produce whole units of each product (no fractions). You will use integer programming to find the best number of units to produce.

🎯 Goal: Build a program using SciPy to solve an integer programming problem that maximizes profit while respecting resource limits.

📋 What You'll Learn

Create arrays for profit coefficients and resource constraints

Set up integer constraints for the decision variables

Use SciPy's milp function to solve the integer programming problem

Print the optimal number of units to produce for each product

💡 Why This Matters

🌍 Real World

Integer programming helps businesses decide how many whole units of products to make when resources are limited.

💼 Career

Many data science and operations research jobs require solving optimization problems like this to improve efficiency and profits.

1

Set up profit and resource data

Create a NumPy array called c with values [-20, -30] representing the negative profits for two products. Create a 2D NumPy array called A_ub with values [[1, 2], [3, 1]] representing resource usage per product. Create a NumPy array called b_ub with values [40, 30] representing resource limits.

SciPy

# Create arrays c, A_ub, and b_ub with the exact values
# Your code here

Hint

Use np.array to create arrays with the exact values given.

2

Define integer constraints

Create a NumPy array called integrality with values [1, 1] to specify that both decision variables must be integers.

SciPy

import numpy as np

c = np.array([-20, -30])
A_ub = np.array([[1, 2], [3, 1]])
b_ub = np.array([40, 30])

# Create the integrality array
# Your code here

Hint

Use np.array with [1, 1] to indicate integer variables.

3

Solve the integer programming problem

Import milp and Bounds from scipy.optimize. Create a Bounds object called bounds with lower bounds 0 and no upper bounds for both variables. Use milp with arguments c=c, A_ub=A_ub, b_ub=b_ub, integrality=integrality, and bounds=bounds to solve the problem. Store the result in a variable called result.

SciPy

import numpy as np
from scipy.optimize import milp, Bounds

c = np.array([-20, -30])
A_ub = np.array([[1, 2], [3, 1]])
b_ub = np.array([40, 30])

integrality = np.array([1, 1])

# Create bounds and solve the integer programming problem
# Your code here

Hint

Use Bounds to set lower bounds to 0 and upper bounds to infinity. Call milp with all required arguments.

4

Print the optimal production quantities

Print the string "Optimal production quantities:" followed by the result.x array which contains the number of units to produce for each product.

SciPy

import numpy as np
from scipy.optimize import milp, Bounds

c = np.array([-20, -30])
A_ub = np.array([[1, 2], [3, 1]])
b_ub = np.array([40, 30])

integrality = np.array([1, 1])

bounds = Bounds([0, 0], [np.inf, np.inf])
result = milp(c=c, A_ub=A_ub, b_ub=b_ub, integrality=integrality, bounds=bounds)

# Print the optimal production quantities
# Your code here

Hint

Use print to show the message and the result.x array.

Practice

1.

What is the main purpose of integer programming in scipy?

easy

A. To perform statistical hypothesis testing

B. To solve differential equations numerically

C. To find the best solution where some variables must be whole numbers

D. To visualize data with plots

Solution

1. Step 1: Understand integer programming concept

   Integer programming is used to find optimal solutions where some or all variables are restricted to integers (whole numbers).

2. Step 2: Match with scipy usage

   In scipy, integer programming helps solve optimization problems with integer constraints, unlike other tasks like plotting or statistics.

3. Final Answer:

   To find the best solution where some variables must be whole numbers -> Option C

4. Quick Check:

   Integer programming = whole number solutions [OK]

Hint: Integer programming means variables are whole numbers [OK]

Common Mistakes:

• Confusing integer programming with plotting or statistics
• Thinking it solves differential equations
• Assuming variables can be fractional

2.

Which of the following is the correct way to specify integer variables in scipy.optimize.linprog?

from scipy.optimize import linprog

result = linprog(c, A_ub=A, b_ub=b, integrality=...)

easy

A. integrality=True # boolean for all integer

B. integrality=[1, 0, 1] # 1 means integer, 0 means continuous

C. integrality='integer' # string to specify all integer

D. integrality=None # default no integer constraints

Solution

1. Step 1: Recall integrality parameter usage

   The integrality argument takes a list or array indicating which variables are integers (1) or continuous (0).

2. Step 2: Check options

   integrality=[1, 0, 1] # 1 means integer, 0 means continuous correctly uses a list with 1s and 0s. Options A, B, and D use incorrect types.

3. Final Answer:

   integrality=[1, 0, 1] # 1 means integer, 0 means continuous -> Option B

4. Quick Check:

   integrality list = integer flags [OK]

Hint: Use list of 1/0 to mark integer variables [OK]

Common Mistakes:

• Passing a string or boolean instead of list
• Leaving integrality as None to expect integers
• Confusing integrality with other parameters

3.

What will be the output of this code snippet?

from scipy.optimize import linprog

c = [-1, -2]
A = [[1, 1]]
b = [3]
integrality = [1, 1]

result = linprog(c, A_ub=A, b_ub=b, integrality=integrality, method='highs')
print(result.x.round())

medium

A. [1. 1.]

B. [1. 2.]

C. [3. 0.]

D. [0. 3.]

Solution

1. Step 1: Understand the problem setup

   The objective is to minimize -x - 2y, which is equivalent to maximizing x + 2y, with constraint x + y ≤ 3 and both x,y integers.

2. Step 2: Find integer values maximizing x + 2y under constraint

   Feasible integer points include (0,3): x+2y=6, (1,2):5, (2,1):4, (3,0):3. Maximum at (0,3), so result.x.round() prints [0. 3.].

3. Final Answer:

   [0. 3.] -> Option D

4. Quick Check:

   Max x+2y with x+y≤3 integer = [0,3] [OK]

Hint: Maximize by checking integer combos under constraints [OK]

Common Mistakes:

• Picking suboptimal integer point like [1,2]
• Misunderstanding objective sign for maximization
• Ignoring non-negativity bounds

4.

Identify the error in this integer programming code using scipy.optimize.linprog:

from scipy.optimize import linprog

c = [1, 1]
A = [[-1, 2]]
b = [4]
integrality = [1, 1]

result = linprog(c, A_ub=A, b_ub=b, integrality=integrality)
print(result.x)

medium

A. No error; code runs correctly

B. Missing method='highs' argument causes solver failure

C. Constraint matrix A has wrong sign for inequality

D. integrality must be a boolean, not a list

Solution

1. Step 1: Check linprog default solver compatibility

   In recent SciPy, the default method is 'highs', which supports integrality for integer programming.

2. Step 2: Identify if any error exists

   integrality=[1,1] is correct format. Parameters c, A_ub, b_ub are valid. No syntax or runtime errors; code runs.

3. Final Answer:

   No error; code runs correctly -> Option A

4. Quick Check:

   Default method='highs' supports integrality [OK]

Hint: Default method='highs' supports integer constraints [OK]

Common Mistakes:

• Assuming default solver lacks integer support
• Passing integrality as boolean instead of list
• Misinterpreting constraint matrix

5.

You want to solve an integer programming problem to maximize profit with variables x and y, where x + 2y ≤ 8, x ≥ 0, y ≥ 0, and both x and y must be integers. Which scipy.optimize.linprog call correctly models this problem?

hard

A. c = [-1, -2]
A = [[1, 2]]
b = [8]
integrality = [1, 1]
linprog(c, A_ub=A, b_ub=b, bounds=[(0, None), (0, None)], integrality=integrality, method='highs')

B. c = [1, 2]
A = [[1, 2]]
b = [8]
integrality = [1, 1]
linprog(c, A_ub=A, b_ub=b, bounds=[(0, None), (0, None)], integrality=integrality, method='highs')

C. c = [-1, -2]
A = [[-1, -2]]
b = [-8]
integrality = [1, 1]
linprog(c, A_ub=A, b_ub=b, bounds=[(0, None), (0, None)], integrality=integrality, method='highs')

D. c = [-1, -2]
A = [[1, 2]]
b = [8]
integrality = [0, 0]
linprog(c, A_ub=A, b_ub=b, bounds=[(0, None), (0, None)], method='highs')

Solution

1. Step 1: Translate maximization to minimization

   Maximize profit = x + 2y is same as minimize -x - 2y, so c = [-1, -2].

2. Step 2: Set constraints and integrality

   Constraint x + 2y ≤ 8 is A = [[1, 2]], b = [8]. Variables are non-negative with bounds (0, None). Both x and y are integers, so integrality = [1, 1].

3. Step 3: Confirm method and parameters

   Use method='highs' to support integer programming.

4. Final Answer:

   The code with c = [-1, -2], A = [[1, 2]], integrality = [1, 1], method='highs' -> Option A

5. Quick Check:

   Maximize -> minimize negative, integrality=1 for integers [OK]

Hint: Maximize by minimizing negative objective with integer flags [OK]

Common Mistakes:

• Using positive c vector for maximization
• Incorrect sign or values in constraints
• Not setting integrality for integer variables
• Omitting method='highs' for integer programming