Integer Programming Examples

Optimization · Axiom Academy

EXAMPLE Integer Programming Methods Master IP formulation and solution techniques through three complete worked examples Example 1: Capital Budgeting Problem A company has 100 million to invest in projects. Each project requires upfront investment and generates NPV (net present value). Each project is indivisible: either fully funded or not at all. Excellent work! You've mastered three fundamental IP problem types. Here's what we learned: Binary Variables: Decision variables that are either 0 or 1 model yes/no decisions like project selection, facility opening, or set membership. LP Relaxation: Relaxing integrality constraints (allowing 0 ≤ x ≤ 1) gives an upper bound on the optimal IP objective. This bound guides branch and bound. Branch and Bound: Systematically partitions the feasible region by branching on fractional variables, pruning branches that cannot beat the current best solution. Modeling Patterns: Capital budgeting uses knapsack structure, facility location combines fixed costs with assignment, and set covering ensures all requirements are met. Integrality Gap: The difference between LP and IP optimal values indicates problem difficulty. Small gaps mean LP relaxation is tight; large gaps require more branching. These formulation techniques apply to scheduling, routing, production planning, and many other optimization problems. Practice recognizing which binary variables to define and how to model business constraints!

This is the written version of the interactive lesson above. See the full Optimization course.