Skip to main content

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-MM bound.
  • Validate integrality, capacity, objective value, and solver status independently.

Formulation before solver choice​

Let xA,xB∈Z≥0x_A,x_B\in\mathbb{Z}_{\ge0} be indivisible outreach-kit batches per week and y∈{0,1}y\in\{0,1\} 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,

max⁡ 9xA+7xB−4y\max\ 9x_A+7x_B-4y

subject to 4xA+3xB≤114x_A+3x_B\le11, xB≤3yx_B\le3y, and the declared domains. The linking constant M=3M=3 is derived from capacity: even with all staff assigned to B, at most ⌊11/3⌋=3\lfloor11/3\rfloor=3 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-MM can weaken bounds; an invalidly small one removes feasible plans.
  • status == 0 certifies 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.