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.