Interactive lab
The ideas of the course, hands on: relaxations, bounds, heuristics and formulations. Pick an app: it opens full page. Everything runs in the browser, without Gurobi; the problems are small, so that every step can be seen.
2. Relaxations, duality and bounds
-
Integer points and relaxation
The integer points inside the polyhedron, the optimum of the continuous relaxation and the integer optimum: move the constraints and the objective and see how wide the gap between them is.
4. Constructive heuristics
-
Knapsack: ratio heuristic versus optimum
The constructive ratio heuristic fills the knapsack by value/weight: follow it item by item and compare its value with the optimum and with the bound of the continuous relaxation.
-
TSP: nearest neighbour versus optimal tour
The nearest-neighbour tour is built step by step, then 2-opt improves it: it is compared with the optimal tour, with the length of both.
-
Bin packing and scheduling
Next Fit, First Fit, Best Fit and First Fit Decreasing fill the bins, List scheduling and LPT assign the jobs to the machines: step by step, with the lower bound next to the solution and the optimum at the end.
5. Logic and binary variables
-
Big-M and relaxation
A conditional constraint written with big-M: move \(M\) with the slider and watch the continuous relaxation grow when \(M\) exceeds the minimum, and the MILP set lose pieces when it is too small.
6. Links between variables
-
Weak and strong formulations
Two formulations with the same integer points, one on top of the other: how close each one gets to the convex hull, and what changes in the bound of the relaxation.