Come si lavora con il corso
Che cosa si impara a fare
- Leggere un problema e scriverne il modello. Quali sono le decisioni, quali variabili servono e con che dominio, e come ogni frase dell'enunciato diventa un vincolo.
- Far vedere che il modello fa quello che deve. Un vincolo che lega due variabili impone un'implicazione: si dimostra che la impone davvero, nei due versi.
- Trovare una buona soluzione a mano, con un'euristica che si costruisce in pochi passi e si sa giustificare.
- Costruire il duale del rilassamento e ricavarne quanto, al massimo, si potrebbe ancora guadagnare.
- Dire quanto vale la soluzione che si ha in mano. Su un'istanza grande il solver si ferma prima dell'ottimo: restano una soluzione e due numeri che la racchiudono. Se distano poco, quella soluzione si usa — e lo si può dimostrare.
- Scrivere e risolvere il modello con Gurobi, e capire che cosa risponde il solver.
Come il corso ci arriva
- Il metodo, in sei capitoli: logica e variabili binarie, i quattordici legami fra variabili con le loro dimostrazioni, rilassamenti e bound, euristiche costruttive, Gurobi.
- Trentotto problemi svolti per intero: quindici modelli numerici, uno per tecnica, con i dati scritti per esteso; e ventitré problemi delle tre famiglie — assegnamento e scheduling, localizzazione e copertura, pianificazione della produzione — più i problemi misti. Ciascuno con enunciato, modello, istanza, euristica, duale, ottimo e confronto.
- Due o tre domande aggiuntive su ogni problema: si cambia un dato o si aggiunge un vincolo, e si rifanno modello e bound. Per ciascuno degli esercizi una variante è svolta per intero, come modello di risposta.
- Quaranta problemi da modellare, dati come arrivano davvero e senza il modello già scritto: venti con i dati numerici espliciti e venti in forma simbolica.
- Quarantacinque notebook che girano in Colab, senza installare niente: lo stesso codice delle pagine, cella per cella.
- Nessun risultato trascritto a mano: ogni numero viene da uno script che si può rilanciare, e un controllo automatico verifica che il testo e il codice dicano la stessa cosa.
Il formato di ogni esercizio
Modello → legami fra le variabili → istanza → euristica (upper bound) → duale del rilassamento LP (lower bound) → soluzione con il solver → domande di modellazione aggiuntive.
Il corso in breve
6 capitoli di modellazione · 38 problemi svolti per intero · 40 problemi da modellare · 45 notebook in Colab. L'elenco completo, capitolo per capitolo, sta nel programma.
Per cominciare
Non serve installare niente: ogni script del corso ha il suo notebook che si apre in Colab e gira nel browser.
Chi preferisce lavorare in locale trova i comandi e le note sulla licenza Gurobi nella pagina del materiale scaricabile.
Il percorso è in due parti: prima si imparano gli strumenti di modellazione, poi li si applica a problemi completi. Il filo che le tiene insieme è uno solo — un modello non si limita a scriverlo: se ne racchiude l'ottimo fra due numeri, \(\mathit{LB} \le z(\mathit{MILP}) \le \mathit{UB}\), prima ancora di affidarlo al solver.
Percorso in due parti
| Contenuto | Obiettivi di apprendimento | |
|---|---|---|
| Parte I | Modellazione | riconoscere un legame fra variabili (attivazione, massimo, big-M, se e solo se…) e dimostrare che il modello lo impone davvero |
| Parte II | I problemi | applicare i legami a tre famiglie di problemi reali e ai problemi misti, dal modello al codice Gurobi |
Il formato di ogni esercizio
Ogni problema del corso segue lo stesso schema in quattro quesiti:
- Modello. Scrivere il MILP: variabili (con il conteggio), obiettivo, vincoli con la loro descrizione, e — se ci sono due famiglie di variabili collegate — spiegare il legame: qual è l'implicazione, e come il vincolo (o l'ottimo) la impone, nei due versi.
- Istanza. Scrivere il modello per un'istanza numerica piccola.
- Euristica. Progettare un algoritmo costruttivo che trovi una soluzione ammissibile dell'istanza, ed eseguirlo passo per passo per ottenere un upper bound (lower bound se il problema è di massimo).
- Duale. Scrivere il duale del rilassamento LP, per il modello generale e per l'istanza, e costruire a mano una soluzione duale ammissibile per ottenere il bound dal lato opposto.
Il lb ≤ z(\mathit{MILP}) ≤ ub che ne risulta è il filo conduttore del corso: un
modello non si limita a scriverlo: se ne racchiude l'ottimo fra due numeri prima di
affidarlo al solver. Un solver interrotto a metà, del resto, un certificato lo
fornisce eccome — l'incumbent ObjVal e il bound ObjBound racchiudono
l'ottimo in un intervallo, e il MIPGap ne misura l'ampiezza. Il punto
didattico è un altro: saper costruire quei due numeri a mano serve a capire
da dove vengono, a giudicare se l'intervallo che il solver riporta è stretto
perché il modello è buono o largo perché è formulato male, e a produrre un bound
anche quando il solver non arriva a nulla di utile.
Gli errori più comuni
- Scrivere un'implicazione la cui tesi è vera comunque (controinversa vacua): prima di scriverla, verificare che antecedente e conseguente siano entrambi genuini.
- Dimostrare un solo verso di un'implicazione «imposta dal vincolo» — servono sempre entrambi gli "if".
- Confondere una relazione «imposta dal vincolo» con una che «segue dall'ottimo»: la seconda richiede l'argomento di scambio in sei passi, non basta dire «si vede che conviene».
- Concludere «in ogni soluzione ottima» quando il coefficiente è solo \(\ge 0\) (non \(> 0\)): la conclusione corretta è più debole, «esiste un ottimo in cui…».
- Usare un big-M enorme «per sicurezza»: peggiora il rilassamento LP senza bisogno.
- Dimenticare che un vincolo di mutua esclusione (\(A + B \le 1\)) non implica che almeno uno dei due valga 1.
- Scrivere il duale del rilassamento sbagliando il verso o il segno di una variabile duale rispetto al verso del vincolo primale.
- Costruire una soluzione duale ammissibile ma non verificarne l'ammissibilità su tutti i vincoli.
Riproducibilità
Nessun numero di queste pagine è scritto a mano: escono tutti da uno script che si può rilanciare, e un controllo automatico verifica che testo e codice dicano la stessa cosa. I comandi stanno nella pagina del materiale scaricabile.