Laboratorio interattivo
Le idee del corso da toccare con mano: rilassamenti, bound, euristiche e formulazioni. Scegli un'app: si apre a tutta pagina. Tutto gira nel browser, senza Gurobi; i problemi sono piccoli, così ogni passo si vede.
2. Rilassamenti, dualità e bound
-
Punti interi e rilassamento
I punti interi dentro il poliedro, l'ottimo del rilassamento continuo e l'ottimo intero: muovi i vincoli e la funzione obiettivo e guarda quanto è largo il divario fra i due.
4. Euristiche costruttive
-
Zaino: euristica per rapporto contro ottimo
L'euristica costruttiva per rapporto riempie lo zaino in ordine di valore/peso: seguila oggetto per oggetto e confronta il suo valore con l'ottimo e con il bound del rilassamento continuo.
-
TSP: nearest neighbour contro giro ottimo
Il giro del nearest neighbour si costruisce passo passo, poi il 2-opt lo migliora: si confronta con il giro ottimo, con la lunghezza di entrambi.
-
Bin packing e scheduling
Next Fit, First Fit, Best Fit e First Fit Decreasing riempiono i contenitori, List scheduling e LPT assegnano i lavori alle macchine: passo passo, con il bound inferiore accanto alla soluzione e l'ottimo alla fine.
5. Logica e variabili binarie
-
Big-M e rilassamento
Un vincolo condizionato scritto con il big-M: sposta \(M\) con il cursore e guarda il rilassamento continuo allargarsi quando \(M\) supera il minimo, e l'insieme del MILP perdere pezzi quando è troppo piccolo.
6. Legami fra variabili
-
Formulazioni deboli e forti
Due formulazioni con gli stessi punti interi, sovrapposte: quanto si avvicina ciascuna all'involucro convesso, e che cosa cambia nel bound del rilassamento.