Integer and Binary Optimization
Continuous allocations can be useful planning approximations, but a half vehicle, an unstaffed opened site, or 2.4 indivisible kits is not an executable decision. Integer and binary variables make those restrictions explicit.
Prerequisites
Complete multi-objective optimization and Pareto frontiers.
Learning goals
- Declare integer and binary decision domains rather than rounding a continuous answer.
- Read an LP relaxation as a bound, not as an implementable plan.
- Connect fixed-charge logic with a defensible big- bound.
- Validate integrality, capacity, objective value, and solver status independently.
Formulation before solver choice
Let be indivisible outreach-kit batches per week and say whether site B opens. One A batch uses 4 staff-hours and yields 9 benefit points; one B batch uses 3 staff-hours and yields 7 points, but opening B costs 4 points. With 11 staff-hours available,
subject to , , and the declared domains. The linking constant is derived from capacity: even with all staff assigned to B, at most batches fit. A casual value such as one million weakens relaxations, can worsen numerical behavior, and hides a missing business bound.
SciPy's milp sends this mixed-integer linear model to HiGHS. OR-Tools CP-SAT could represent the same integer logic, but a solver switch must not change the mathematical model silently.
The verified environment uses SciPy 1.18.1 and OR-Tools 9.15.6755. OR-Tools itself is Apache-2.0 licensed and publishes wheels for Python 3.9 through 3.14; an optional third-party solver or separately loaded commercial interface can have its own license and installation terms. This batch uses the bundled CP-SAT, routing, and graph interfaces plus SciPy's maintained HiGHS interfaces—no hosted or proprietary solver is required.
Worked example
import numpy as np
from scipy.optimize import Bounds, LinearConstraint, milp
c = np.array([-9.0, -7.0, 4.0]) # milp minimizes
bounds = Bounds([0.0, 0.0, 0.0], [np.inf, np.inf, 1.0])
constraints = LinearConstraint(
[[4.0, 3.0, 0.0], [0.0, 1.0, -3.0]],
[-np.inf, -np.inf],
[11.0, 0.0],
)
integer = milp(c, integrality=[1, 1, 1], bounds=bounds, constraints=constraints,
options={"mip_rel_gap": 0.0})
relaxed = milp(c, integrality=[0, 0, 0], bounds=bounds, constraints=constraints)
if integer.status != 0 or relaxed.status != 0:
raise RuntimeError((integer.message, relaxed.message))
x_a, x_b, opened = integer.x
used = 4 * x_a + 3 * x_b
print(f"integer_status={integer.status} batches=({x_a:.0f},{x_b:.0f}) open_b={opened:.0f}")
print(f"staff_used_hours={used:.0f} objective_points={-integer.fun:.1f}")
print(f"lp_relaxation_bound={-relaxed.fun:.2f} implementable=False")
Expected output:
integer_status=0 batches=(2,1) open_b=1
staff_used_hours=11 objective_points=21.0
lp_relaxation_bound=24.75 implementable=False
Status 0 means HiGHS reported an optimum for the encoded MILP. Direct substitution confirms integral domains, 11 staff-hours used, the linking constraint, and 21 points. The fractional relaxation is an upper bound for this maximization problem, not a schedule to round: independent enumeration of all feasible integer triples confirms that 21 is the exact model optimum. Neither result establishes real-world feasibility.
Limitations and common mistakes
- Rounding an LP solution can violate capacity or linking constraints and need not preserve optimality.
- A binary variable represents a declared yes-or-no decision; it does not prove the real operation is truly all-or-nothing.
- A loose big- can weaken bounds; an invalidly small one removes feasible plans.
status == 0certifies the encoded model within solver tolerances, not demand, causal benefit, or operational validity.- Mixed-integer solve time can grow sharply with instance structure; this three-variable result is not a scalability claim.
Practice
Raise site B's fixed cost from 4 to 8 points. Enumerate all feasible integer triples, solve again, and explain why the LP-relaxation bound can remain optimistic even when every constraint is linear.
Next steps
Use one-choice-per-row constraints in assignment and matching problems.
Primary sources
Checked 2026-10-19: SciPy 1.18.1, milp integrality, statuses, limits, and MIP gap and BSD license; HiGHS, official documentation; Google OR-Tools 9.15, release and Python support, Apache-2.0 license statement, solver selection overview, and CP-SAT status semantics.