Skip to content

Fifteen numerical models

Class: BIP · ILP · MILP · Scripts: one per model, python/ex01_van.py … python/ex15_timetable.py

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:

  1. the statement, with the data of the instance;
  2. the variables, with their domain and their count;
  3. the model of the instance, primal and dual;
  4. a feasible solution built by hand, which gives the primal bound;
  5. 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 Open in Colab
EX 2 — Bus lines assignment with a capacity in number of lines Open in Colab
EX 3 — Relay assignment with more resources than tasks; totally unimodular matrix Open in Colab
EX 4 — Hub-and-spoke covering: the minimum number of hubs Open in Colab
EX 5 — Mutual funds bought in lots integer counts in lots, with a proportion constraint Open in Colab
EX 6 — Vehicles with a minimum quantity minimum lot: a minimum quantity if the type is produced Open in Colab
EX 7 — Custom aircraft with a fixed set-up cost fixed set-up cost and a free quantity up to the order Open in Colab
EX 8 — Seminars exact cardinality, non-adjacency, dual with a free variable Open in Colab
EX 9 — Queens on the chessboard packing on a chessboard: rows, columns and diagonals Open in Colab
EX 10 — Tools of a CNC machine selection with a tool set: disaggregated activation Open in Colab
EX 11 — Shoes with a minimum production threshold minimum lot with three shared resources Open in Colab
EX 12 — Balancing between two workers min-max against difference: same solutions, different values Open in Colab
EX 13 — Emergency department shifts covering the daily requirements with weekly shifts Open in Colab
EX 14 — Shoes: production, inventory and hirings inventory balance and workforce over three months Open in Colab
EX 15 — The music school timetable conflicts, non-adjacency and preferences to avoid Open in Colab