Why it matters

LP + IP solve many optimization problems. Understanding shapes constrained optimization.

Advertisement

The architecture

LP: max c'x subject to Ax ≤ b, x ≥ 0.

IP: same but x ∈ ℤ.

Optimization spectrumLPpoly-time (Simplex)IPNP-hard (B&B)SolversCPLEX, Gurobi, GLPKLP relaxation of IP: solve LP, round; not always optimal
LP + IP problems.
Advertisement

How it works end to end

Simplex: polynomial in practice; exponential worst case. Modern LP solvers extremely fast.

Branch and bound: partition IP search space; prune via LP bounds.

Cutting planes: add constraints to tighten LP relaxation.