Integer programming in SciPy - Step-by-Step Execution

Concept Flow - Integer programming

Define variables with integer constraints

↓

Set objective function to maximize or minimize

↓

Add linear constraints

↓

Call solver to find integer solution

↓

Check if solution is feasible

Yes No↓

Output solution

Integer programming solves optimization problems where variables must be whole numbers, by defining variables, constraints, and objective, then using a solver to find the best integer solution.

Execution Sample

SciPy

from scipy.optimize import milp, LinearConstraint

c = [-1, -2]
A = [[1, 1], [3, 1]]
b = [4, 6]

lc = LinearConstraint(A, [0, 0], b)

res = milp(c, constraints=[lc], integrality=[1, 1])
print(res.x)

This code solves a simple integer programming problem minimizing -x - 2y with constraints, finding integer values for x and y.

Execution Table

Step	Action	Variables	Constraint Check	Solver Status	Output
1	Define objective coefficients c = [-1, -2]	c = [-1, -2]	N/A	N/A	N/A
2	Define constraints A and b	A = [[1,1],[3,1]], b = [4,6]	N/A	N/A	N/A
3	Set integrality for variables	integrality = [1,1]	N/A	N/A	N/A
4	Call milp solver	Variables unknown	Check Ax <= b	Solving...	N/A
5	Solver finds solution x=[2,2]	x = [2,2]	1*2+1*2=4 <=4 (True), 3*2+1*2=8 <=6 (False)	Infeasible, solver tries alternatives	N/A
6	Solver tries x=[0,4]	x = [0,4]	1*0+1*4=4 <=4 (True), 3*0+1*4=4 <=6 (True)	Feasible solution found	N/A
7	Output solution	x = [0,4]	Constraints satisfied	Success	[0. 4.]

💡 Solver stops after finding feasible integer solution x=[0,4] satisfying all constraints.

Variable Tracker

Variable	Start	After Step 4	After Step 5	After Step 6	Final
c	undefined	[-1, -2]	[-1, -2]	[-1, -2]	[-1, -2]
A	undefined	[[1,1],[3,1]]	[[1,1],[3,1]]	[[1,1],[3,1]]	[[1,1],[3,1]]
b	undefined	[4,6]	[4,6]	[4,6]	[4,6]
integrality	undefined	[1,1]	[1,1]	[1,1]	[1,1]
x	undefined	unknown	[2,2]	[0,4]	[0,4]
Solver Status	idle	solving	infeasible	feasible	success

Key Moments - 3 Insights

Why does the solver reject x=[2,2] even though it looks close?

Because the second constraint 3*2+1*2=8 is greater than 6, violating the constraint. See execution_table row 5.

How does the solver find the final solution x=[0,4]?

It tries alternative integer values until all constraints are satisfied, as shown in execution_table row 6.

Why must variables be integers in integer programming?

Because the problem requires whole number solutions, enforced by integrality=[1,1], ensuring solver only picks integer values.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the value of x and is it feasible?

A x=[2,2], constraints violated

B x=[1,3], constraints satisfied

C x=[2,2], constraints satisfied

D x=[1,3], constraints violated

💡 Hint

Check the 'Variables' and 'Constraint Check' columns in row 5 of execution_table.

At which step does the solver find a feasible solution?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look at the 'Solver Status' column for 'Feasible solution found' in execution_table.

If integrality was not set, what would likely change in the solution x?

A x would still be integers

B x could be fractional values

C Solver would fail to find any solution

D Constraints would be ignored

💡 Hint

Refer to variable_tracker row for 'integrality' and how it restricts variable values.

Concept Snapshot

Integer programming solves optimization problems where variables must be integers.
Define objective coefficients and linear constraints.
Set integrality constraints for variables.
Use scipy.optimize.milp to solve.
Solver finds integer solutions satisfying constraints.
Output is the best integer variable values.

Full Transcript

Integer programming is a method to find the best solution to a problem where variables must be whole numbers. We start by defining the objective function coefficients and the constraints as linear inequalities. Then, we specify which variables must be integers. Using scipy's milp solver, we ask it to find values for the variables that minimize or maximize the objective while respecting the constraints and integrality. The solver tries possible integer values, checking constraints each time. If a candidate solution violates constraints, it tries others until it finds a feasible one or reports no solution. In the example, the solver first tries x=[2,2], which violates a constraint, then finds x=[0,4], which satisfies all constraints and is output as the solution.

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