Modelling
You do not learn models by heart here: you learn the techniques for building them. Thirty memorised formulations are no help in front of a new text; a dozen links between variables, knowing why they work, are.
By the end of this part you can
- Translate a logical condition into linear constraints, and prove that they really impose it.
- Link a binary variable to a continuous or integer one: activation, fixed cost, minimum lot, a big-M read from the data.
- Derive a bound from the linear relaxation and write its dual by hand.
- Build a feasible solution by hand, and say which bound it gives.
- Take the model into Python/Gurobi and read what the solver answers.
Six chapters, in this order: what a MIP model is; the bounds, from the relaxation side and from its dual; the solver, with the classical models written in Python; the constructive heuristics, which give the bound from the other side; the logic of binary variables; and the fourteen links between variables, which are the heart of modelling and come when every tool to judge them is already in hand.
Every chapter has a script producing all the numbers quoted and a notebook that opens in Colab. No value appears on these pages unless it comes out of a reproducible run.
-
1. What is a MIP model
Data, variables, objective, constraints. Why rounding fails. The two LP relaxations and which side the bounds are on. Three gaps not to be confused. Branch-and-bound in one page.
-
2. Relaxations, duality and bounds
The primal/dual conversion table, three recipes for building a dual solution by hand, valid inequalities and cover cuts, and why the LP duals are not the marginal prices of the MILP.
-
3. From the model to Python/Gurobi
The four classes of variables, one
addConstrsper family, and how to readStatus,SolCount,ObjVal,ObjBound,MIPGap,NodeCountand the tolerances. The course protocol, from start to finish. -
4. Constructive heuristics
Next-fit, first-fit, best-fit, LPT, covering constructive heuristic, knapsack constructive heuristic and lot sizing: pseudocode, trace, feasibility check and bound. A failure of the constructive heuristic does not prove infeasibility.
-
5. Logic and binary variables
AND, OR, NOT; clauses and conjunctive normal form; the three rules turning a CNF into linear constraints; implications, contrapositives and splits; five solved exercises, all checked by enumeration.
-
6. Links between variables
Fourteen techniques for linking different families of variables: activation, fixed cost, minimum lot, counts, maximum, min-max, absolute value, big-M, precedences, "if and only if", types, alldiff, penalties, piecewise functions. Plus the map.