Quindici modelli numerici
Classe: BIP · ILP · MILP · Script: uno per modello,
python/ex01_furgone.py … python/ex15_orario.py
Prerequisiti
-
Da questo modulo, Capitolo 2 «Rilassamenti, dualità e bound»: il duale del rilassamento LP e la soluzione duale costruita a mano.
-
Da questo modulo, Capitolo 4 «Euristiche costruttive»: le euristiche costruttive e il bound primale.
-
Da questo modulo, Capitolo 6 «Legami fra variabili»: i legami fra variabili (attivazione, lotto minimo, conteggi interi, min-max).
Obiettivi
Alla fine di questo capitolo sarai in grado di:
-
scrivere le variabili e il modello di un'istanza a dati espliciti, primale e duale;
-
costruire a mano una soluzione ammissibile e una soluzione duale, e chiudere il sandwich \(\lb \le \zmilp \le \ub\);
-
riconoscere in ogni enunciato la tecnica di cui il modello ha bisogno;
-
confrontare i bound costruiti a mano con l'ottimo dato dal solver.
I quindici modelli numerici del corso, da EX 1 a EX 15. Dati espliciti, poche variabili, una tecnica per modello: sono i più facili, e vengono prima delle famiglie di problemi e dei problemi misti.
Ogni modello numerico ha sempre le stesse cinque parti:
- l'enunciato, con i dati dell'istanza;
- le variabili, con il loro dominio e il loro conteggio;
- il modello dell'istanza, primale e duale;
- una soluzione ammissibile costruita a mano, che dà il bound primale;
- una soluzione duale costruita a mano, che dà il bound duale, e il confronto con l'ottimo del solver.
Ogni modello ha la sua pagina, il suo script e il suo notebook.
| Modello | Che cosa mette in gioco | Notebook |
|---|---|---|
| EX 1 — Il furgone da otto posti | selezione con capacità e un'implicazione fra gruppi | |
| EX 2 — Linee di autobus | assegnamento con capacità in numero di linee | |
| EX 3 — Staffetta | assegnamento con più risorse che compiti; matrice totalmente unimodulare | |
| EX 4 — Hub-and-spoke | copertura: il minimo numero di hub | |
| EX 5 — Fondi acquistabili a lotti | conteggi interi a lotti, con un vincolo di proporzione | |
| EX 6 — Veicoli con quantità minima | lotto minimo: una quantità minima se il tipo si produce | |
| EX 7 — Aerei su commessa con costo fisso | costo fisso di attrezzaggio e quantità libera fino alla richiesta | |
| EX 8 — Seminari | cardinalità esatta, non-adiacenza, duale con variabile libera | |
| EX 9 — Le regine sulla scacchiera | packing su scacchiera: righe, colonne e diagonali | |
| EX 10 — Utensili di una macchina CNC | selezione con corredo di utensili: attivazione disaggregata | |
| EX 11 — Scarpe con soglia minima di produzione | lotto minimo con tre risorse condivise | |
| EX 12 — Bilanciamento fra due operai | min-max contro differenza: stesse soluzioni, valori diversi | |
| EX 13 — I turni del pronto soccorso | copertura dei fabbisogni giornalieri con turni settimanali | |
| EX 14 — Scarpe: produzione, scorte e assunzioni | bilancio delle scorte e organico su tre mesi | |
| EX 15 — L'orario della scuola di musica | conflitti, non-adiacenza e preferenze da evitare |
In sintesi
In sintesi
-
Ogni modello numerico ha cinque parti: enunciato, variabili, modello dell'istanza, bound primale e bound duale.
-
Una tecnica per modello, in ordine di difficoltà: selezione, assegnamento, copertura, lotti, quantità minime, bilanciamento, turni.
-
Il bound primale viene da un'euristica costruttiva, il bound duale da una soluzione ammissibile del duale del rilassamento.
-
L'ottimo del solver sta sempre dentro il sandwich: quando non ci sta, c'è un errore nel modello o in un bound.