Integer programming in SciPy

Introduction

Integer programming helps us find the best solution when some choices must be whole numbers, like counting items or people.

Deciding how many products to make when you can't make fractions of a product.

Planning staff shifts where the number of workers must be whole numbers.

Allocating resources like machines or vehicles that come in whole units.

Scheduling tasks that require integer time slots.

Optimizing delivery routes with whole number stops.

Syntax

SciPy

from scipy.optimize import milp

result = milp(c=c, A_ub=A, b_ub=b, bounds=bounds, integrality=integrality)

c is the coefficients of the objective function to minimize.

integrality is a list indicating which variables must be integers (1) or continuous (0).

Examples

Minimize -x - 2y with integer x and y, subject to constraints.

SciPy

from scipy.optimize import milp

c = [-1, -2]
A = [[2, 1], [1, 1]]
b = [20, 16]
bounds = [(0, None), (0, None)]
integrality = [1, 1]

result = milp(c=c, A_ub=A, b_ub=b, bounds=bounds, integrality=integrality)
print(result)

Minimize 3x + 5y where x is integer and y is continuous.

SciPy

from scipy.optimize import milp

c = [3, 5]
A = [[1, 0], [0, 2]]
b = [4, 12]
bounds = [(0, None), (0, None)]
integrality = [1, 0]

result = milp(c=c, A_ub=A, b_ub=b, bounds=bounds, integrality=integrality)
print(result)

Sample Program

This program finds the greatest profit for x and y with integer values that satisfy the constraints.

SciPy

from scipy.optimize import milp

# Objective: maximize profit = 4x + 3y
c = [-4, -3]

# Constraints:
# 2x + y <= 8
# x + 2y <= 8
A = [[2, 1], [1, 2]]
b = [8, 8]

# Variables x and y must be integers and >= 0
bounds = [(0, None), (0, None)]
integrality = [1, 1]

result = milp(c=c, A_ub=A, b_ub=b, bounds=bounds, integrality=integrality)

if result.success:
    x, y = result.x
    print(f"Optimal solution: x = {int(round(x))}, y = {int(round(y))}")
    print(f"Maximum profit: {-result.fun:.2f}")
else:
    print("No solution found")

Important Notes

Integer programming problems can be slower to solve than regular linear problems.

Always check if the solver found a solution by looking at result.success.

Rounding the solution is not reliable; use the integrality option to enforce integer variables.

Summary

Integer programming finds the best whole-number solutions under constraints.

Use scipy.optimize.milp with integrality to specify integer variables.

Check solver success and interpret results carefully.