Integer Programming

2016. Deutsche Lufthansa plans schedules for 400 aircraft and 10,000 flights. Without ILP, this would require hundreds of person-years of manual work. Gurobi solves it in a few hours. The traveling salesman problem, hospital staffing, venture portfolio selection - none of these can be solved with ordinary LP. Integers change everything.

• **Aviation**: crew pairing - some of the largest ILP instances in existence, millions of variables, Gurobi/CPLEX solves in hours
• **ML engineering**: feature selection and neural architecture search as 0-1 ILP - finds the optimal feature subset under a fixed computation budget
• **Amazon logistics**: distribution of inventory across warehouses via MIP, reducing delivery time by 15-20%

Historical context

In 1958, Ralph Gomory at IBM developed the cutting planes method (Gomory cuts) for solving ILP. Before this, no systematic algorithm existed for integer problems. Branch and Bound was independently proposed by Land and Doig in 1960. The combination of Branch & Bound with Gomory cuts became the foundation of all modern ILP solvers. Gurobi (founded 2008 by Bixby, Gu, Rothberg, and Wunderling - the same team that built CPLEX) and CPLEX (IBM, 1988) implement these ideas augmented with thousands of additional cut types: Cover cuts, MIR cuts, Clique cuts, Lift-and-project cuts. Modern solvers are 1 billion times faster on typical instances than 1990s solvers - mostly from algorithmic improvements, not hardware.

ILP formulation

LP allows variables to take fractional values - for example, 2.7 aircraft. But real decisions are discrete: hiring 3.5 employees is not possible, opening 0.8 of a warehouse is not possible. **Integer Linear Programming (ILP)** adds the constraint xᵢ ∈ ℤ (or xᵢ ∈ {0,1} for binary decisions). This transforms the problem from polynomial to NP-hard. Yet real instances with millions of variables are solved routinely by modern solvers.

**Feature selection as 0-1 ILP:** choose k features from n, maximizing model quality under budget k. Variable xᵢ = 1 means 'include feature i'. Constraint: Σxᵢ ≤ k. PuLP + CBC handles n=100-500 features in seconds.

Branch and Bound

Naive enumeration for n binary variables requires checking 2ⁿ candidates. **Branch and Bound** is smarter: it builds a tree of sub-problems, solves the LP-relaxation (dropping integrality) at each node, and prunes branches that cannot improve the current best integer solution. The LP-relaxation always provides an upper bound (for maximization) on what any integer solution in that subtree can achieve.

Key insight: LP-relaxation always gives an **upper bound** for maximization. If lp_relaxation(node) ≤ current_best_integer_solution - prune the branch without expanding it. This cuts the tree exponentially in practice, even though worst-case complexity remains exponential.

Branch and Bound guarantees finding the **global optimum**, but in pathological cases still explores exponentially many nodes. A good initial feasible solution (lower bound from a heuristic) is critical for effective pruning - the tighter the gap, the more branches get cut.

Cutting planes

**Cutting planes** take a different approach: instead of branching, add new linear constraints (cuts) that slice off the fractional LP optimum without removing any feasible integer solution. Repeat until the LP optimum becomes integer. The key guarantee: cuts never eliminate integer feasible points - they only tighten the LP relaxation polytope around the integer hull.

**Branch & Cut** is the standard in modern ILP solvers (Gurobi, CPLEX, CBC). It combines Branch & Bound with cutting planes: at each node it adds cuts to strengthen the LP bound, then branches. This enables solving problems with millions of variables. Modern solvers use dozens of cut types: Gomory cuts, Cover cuts, MIR cuts, Clique cuts - each specialized for different problem structures.

MIP in practice: PuLP and CBC

Mixed-Integer Programs (MIP) are problems where some variables are integer and some real - the most general ILP form. In practice, specialized solvers implement Branch & Cut with presolve, warm starts, and thousands of tuned heuristics. Gurobi (commercial) and CPLEX solve airline crew scheduling with millions of variables in hours. CBC (open-source) handles problems with hundreds of thousands of variables.

**Feature selection in ML as 0-1 ILP:** formulate choosing k from n features. Variable xᵢ ∈ {0,1}. Objective: maximize model quality (accuracy, AUC). Constraint: Σxᵢ ≤ k plus computation budget. PuLP + CBC handles n=100-500 features in seconds - guaranteed optimal selection, unlike greedy or random search.

Key ideas

• **ILP** adds integrality constraints to LP; the problem becomes NP-hard but real instances with millions of variables are solvable
• **Branch & Bound** builds a tree of LP sub-problems, pruning branches by LP bounds; guarantees global optimum
• **Cutting planes (Gomory cuts)** strengthen LP-relaxation by adding linear constraints without removing any integer feasible points
• **Branch & Cut** = B&B + cuts - industry standard (Gurobi, CPLEX, CBC); solves MIP with millions of variables

Вопросы для размышления

• Why does LP-relaxation provide an upper bound (for maximization) on the ILP optimum? How does this relate to the fact that the ILP feasible set is a subset of the LP feasible set?
• The assignment problem's constraint matrix is totally unimodular - its LP-relaxation always gives integer solutions. What structural property of the matrix causes this?
• QAOA can approximate ILP solutions for certain problem structures. Under what conditions would a quantum approach outperform Gurobi on a real combinatorial optimization instance?

Связанные уроки

• opt-03 — LP-relaxation is solved at every node of Branch and Bound - the foundational technique here
• opt-05 — Convex optimization: LP duality connects the LP bounds in B&B to the dual problem
• opt-09 — Combinatorial optimization: TSP, knapsack, set cover - all classical ILP formulations
• sci-04 — SVD and ILP both find the best solution in a constrained space - low rank versus integer constraints
• qc-04 — QAOA builds quantum circuits to solve the same combinatorial optimization problems that ILP addresses classically
• ds-04-consistent-hashing
• alg-32-branch-bound