Quindici modelli numerici

Classe: BIP · ILP · MILP · Script: uno per modello, python/ex01_furgone.py … python/ex15_orario.py

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:

1. l'enunciato, con i dati dell'istanza;
2. le variabili, con il loro dominio e il loro conteggio;
3. il modello dell'istanza, primale e duale;
4. una soluzione ammissibile costruita a mano, che dà il bound primale;
5. 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