Interactive lab¶
Here you can get your hands on integer linear programming. Pick an app: it opens full page. Drag the points and move the sliders; the ▶ button next to a parameter makes it move by itself. The numbers are exact fractions.
Models and bounds¶
-
Integer points and the LP relaxation
The polyhedron, the integer points, the LP optimum and the ILP optimum: move the level line and see the gap.
Strengthening the formulation¶
-
Valid inequalities and the convex hull
Add the valid inequalities one at a time and watch the bound of the relaxation fall toward the integer optimum.
Exact methods¶
-
Cutting plane with Gomory cuts
At each iteration the cut enters the picture and the new LP optimum moves toward the integer optimum.
-
Branch-and-bound step by step
The tree grows and the region is partitioned: choose the variable rule and the node rule, follow LB and UB.