3. Dal modello a Python/Gurobi
Classe: implementazione · Script: python/cap06_gurobi.py
Prerequisiti
-
Da questo modulo, Capitolo 1 «Che cos'è un modello MIP»: le classi di variabili e la struttura di un modello.
-
Da questo modulo, Capitolo 2 «Rilassamenti, dualità e bound»: il rilassamento LP, il suo duale e gli attributi
ObjValeObjBounddel solver.
Obiettivi
Alla fine di questo capitolo sarai in grado di:
-
scrivere un modello in
gurobipy, una famiglia di variabili e di vincoli per blocco; -
dichiarare le quattro classi di variabili, ricordando i bound predefiniti;
-
leggere i risultati nell'ordine giusto:
Status,SolCount,ObjValeObjBound; -
usare correttamente le tolleranze nel leggere i valori interi;
-
risolvere il rilassamento LP con
relax()e leggerne i duali.
Il corso usa un solo solver, Gurobi da Python. Il capitolo mostra come si scrive un modello — una famiglia di vincoli per blocco, con i nomi del modello matematico — come si leggono i risultati, incluso il caso in cui il solver non ha finito, e tre modelli completi che il capitolo delle euristiche riprende.
Ogni numero di queste pagine esce da un unico script,
python/cap06_gurobi.py, e il capitolo è diviso in cinque sezioni.
-
3.1 Scrivere un modello in gurobipy
Le istruzioni di base di gurobipy, le quattro classi di variabili e la regola del corso: una famiglia di vincoli per blocco.
-
3.2 Leggere i risultati
Status,SolCount,ObjVal,ObjBound,MIPGap,NodeCount, e i tre casi in cuiObjValnon si può leggere. -
3.3 Tolleranze e rilassamenti
«Intero» entro
IntFeasTol, erelax()per ottenere il rilassamento del modello appena scritto. -
3.4 Tre modelli classici
Bin packing, makespan e commesso viaggiatore, dall'enunciato all'istanza: i tre problemi che le euristiche riprendono.
-
3.5 Il protocollo, e come si esegue
La sequenza che ogni problema ripete, dai dati alla tabella dei bound, e come si fa girare lo script.
In sintesi
In sintesi
-
Un modello
gurobipysi scrive a blocchi, unaaddConstrsper famiglia, con il nome dell'etichetta del vincolo. -
I risultati si leggono sempre nello stesso ordine; con
SolCount\(=0\) non c'è alcunObjValda leggere. -
Intero vuol dire intero a meno di una tolleranza: si controlla
x.X > 0.5, maix.X == 1. -
relax()dà il rilassamento LP e i suoi dualiPi, i numeri che la dispensa confronta con il duale costruito a mano. -
Bin packing, makespan e TSP (formulazione MTZ) sono i tre modelli che il resto del corso riusa.