Fifteen numerical models
Class: BIP · ILP · MILP · Scripts: one per model,
python/ex01_van.py … python/ex15_timetable.py
Prerequisites
-
From this module, Chapter 2 «Relaxations, duality and bounds»: the dual of the LP relaxation and the dual solution built by hand.
-
From this module, Chapter 4 «Constructive heuristics»: constructive heuristics and the primal bound.
-
From this module, Chapter 6 «Links between variables»: the links between variables (activation, minimum lot, integer counts, min-max).
Objectives
At the end of this chapter you will be able to:
-
write the variables and the model of an instance with explicit data, primal and dual;
-
build by hand a feasible solution and a dual solution, and close the sandwich \(\lb \le \zmilp \le \ub\);
-
recognise in each statement the technique that the model needs;
-
compare the hand-built bounds with the optimum given by the solver.
The fifteen numerical models of the course, from EX 1 to EX 15. Explicit data, few variables, one technique per model: they are the easiest ones, and they come before the three families of problems and the mixed problems.
Every numerical model always has the same five parts:
- the statement, with the data of the instance;
- the variables, with their domain and their count;
- the model of the instance, primal and dual;
- a feasible solution built by hand, which gives the primal bound;
- a dual solution built by hand, which gives the dual bound, and the comparison with the solver's optimum.
Every model has its own page, its own script and its own notebook.
| Model | What it brings into play | Notebook |
|---|---|---|
| EX 1 — The eight-seat van | selection with a capacity and an implication between groups | |
| EX 2 — Bus lines | assignment with a capacity in number of lines | |
| EX 3 — Relay | assignment with more resources than tasks; totally unimodular matrix | |
| EX 4 — Hub-and-spoke | covering: the minimum number of hubs | |
| EX 5 — Mutual funds bought in lots | integer counts in lots, with a proportion constraint | |
| EX 6 — Vehicles with a minimum quantity | minimum lot: a minimum quantity if the type is produced | |
| EX 7 — Custom aircraft with a fixed set-up cost | fixed set-up cost and a free quantity up to the order | |
| EX 8 — Seminars | exact cardinality, non-adjacency, dual with a free variable | |
| EX 9 — Queens on the chessboard | packing on a chessboard: rows, columns and diagonals | |
| EX 10 — Tools of a CNC machine | selection with a tool set: disaggregated activation | |
| EX 11 — Shoes with a minimum production threshold | minimum lot with three shared resources | |
| EX 12 — Balancing between two workers | min-max against difference: same solutions, different values | |
| EX 13 — Emergency department shifts | covering the daily requirements with weekly shifts | |
| EX 14 — Shoes: production, inventory and hirings | inventory balance and workforce over three months | |
| EX 15 — The music school timetable | conflicts, non-adjacency and preferences to avoid |
In summary
In summary
-
Every numerical model has five parts: statement, variables, model of the instance, primal bound and dual bound.
-
One technique per model, in increasing order of difficulty: selection, assignment, covering, lots, minimum quantities, balancing, shifts.
-
The primal bound comes from a constructive heuristic, the dual bound from a feasible solution of the dual of the relaxation.
-
The solver optimum is always inside the sandwich: when it is not, the model or a bound contains a mistake.