Nella programmazione lineare le variabili possono assumere qualunque valore reale. Per molti problemi va benissimo: litri di carburante, ore di lavoro, chilogrammi di mangime. Ma non si possono comprare 2,7 camion, aprire mezzo magazzino o assegnare un turno a un terzo di persona. Quando alcune variabili devono essere intere si entra nel mondo della programmazione lineare intera (PLI), molto più espressivo e molto più difficile.
Perché arrotondare non basta
La tentazione è risolvere il problema lineare e arrotondare. Funziona a volte, ma può dare soluzioni non ammissibili o lontane dall'ottimo. Un esempio:
massimizza x + y
-2x + 2y ≥ 1
-8x + 10y ≤ 13
x, y ≥ 0, interi
L'ottimo continuo è x = 4, y = 4,5, con valore 8,5. Arrotondare y a 4 o a 5 viola un vincolo in entrambi i casi. L'ottimo intero è x = 1, y = 2, con valore 3: lontanissimo dal punto continuo. Nei problemi reali, con centinaia di variabili, l'arrotondamento è ancora meno affidabile.
La forza delle variabili binarie
Il vero potere della PLI sta nelle variabili binarie, che valgono 0 o 1 e rappresentano decisioni sì/no. Con esse si modellano situazioni che la PL non può esprimere:
- costi fissi: se si apre il magazzino j (y_j = 1) si paga un costo fisso, e solo allora vi si possono spedire merci: x_ij ≤ capacità_j · y_j;
- scelte esclusive: al massimo uno tra i progetti A e B: y_A + y_B ≤ 1;
- implicazioni: se si fa A bisogna fare anche B: y_A ≤ y_B;
- vincoli alternativi: rispettare almeno uno di due vincoli, con la tecnica della «big M» che disattiva un vincolo quando una variabile binaria vale 0.
Assegnamenti di turni, localizzazione di impianti, orari, pianificazione della produzione con lotti minimi, scelta di investimenti: quasi tutti i problemi di decisione aziendale si scrivono in PLI.
Il rilassamento lineare
Dato un problema intero, il suo rilassamento lineare è lo stesso problema senza i vincoli di interezza. Due proprietà lo rendono utilissimo:
- in un problema di massimo, il valore del rilassamento è un limite superiore all'ottimo intero, perché toglie vincoli;
- se la soluzione del rilassamento è già intera, è anche l'ottimo intero.
Il rilassamento si risolve in fretta con il simplesso, ed è il motore del metodo più usato per la PLI.
Branch and bound
Branch and bound («dirama e limita») esplora in modo intelligente l'albero delle possibilità.
- Risolvi il rilassamento lineare. Se la soluzione è intera, hai finito.
- Branch: scegli una variabile frazionaria, per esempio x = 2,6, e crea due sottoproblemi: uno con x ≤ 2, l'altro con x ≥ 3. Nessuna soluzione intera va persa, perché ogni intero rispetta uno dei due vincoli.
- Risolvi il rilassamento di ciascun sottoproblema.
- Bound: tieni traccia della migliore soluzione intera trovata finora, detta incumbent. Se il rilassamento di un sottoproblema dà un valore non migliore dell'incumbent, quel ramo non può contenere niente di meglio e si scarta senza esplorarlo.
- Scarta anche i sottoproblemi inammissibili, e continua finché restano nodi aperti.
La potatura del passo 4 è ciò che rende il metodo praticabile: invece di esaminare tutte le combinazioni, si scartano interi rami grazie ai limiti.
Il gap di ottimalità
Durante la ricerca si conoscono due numeri: il valore dell'incumbent (una soluzione vera) e il miglior limite tra i nodi ancora aperti. La differenza relativa tra i due è il gap di ottimalità.
| Momento | Incumbent | Miglior limite | Gap |
|---|---|---|---|
| Dopo 1 minuto | 9.200 | 10.100 | circa 9% |
| Dopo 10 minuti | 9.750 | 9.900 | circa 1,5% |
| Al termine | 9.810 | 9.810 | 0% |
Nella pratica è normale fermarsi quando il gap scende sotto una soglia accettabile, per esempio l'1%: si ha una soluzione con una garanzia di qualità, cosa che le euristiche pure non offrono.
Tagli e formulazioni forti
Due modelli corretti dello stesso problema possono comportarsi in modo diversissimo. Ciò che conta è quanto il rilassamento lineare è vicino all'ottimo intero: più è stretto, più il branch and bound pota.
- I piani di taglio sono vincoli aggiuntivi rispettati da tutte le soluzioni intere ma violati dalla soluzione frazionaria corrente. I tagli di Gomory sono l'esempio classico; i risolutori moderni ne generano molti tipi in automatico. Combinare tagli e diramazione si chiama branch and cut.
- Le formulazioni forti evitano costanti «big M» enormi, che rendono il rilassamento debole: conviene scegliere il valore più piccolo che non tagli soluzioni valide.
- Le simmetrie rallentano molto: se dieci camion identici sono intercambiabili, il risolutore esplora dieci volte la stessa soluzione con nomi diversi. Aggiungere vincoli che impongono un ordine tra elementi identici aiuta.
Consigli pratici
- Partite da un modello piccolo e corretto, poi aggiungete i dettagli.
- Fornite al risolutore una buona soluzione iniziale, magari da un'euristica: un buon incumbent fin dall'inizio aumenta la potatura.
- Impostate un limite di tempo e una soglia di gap realistici.
- Se il modello è troppo lento, prima di cambiare risolutore provate a rafforzare la formulazione.
In sintesi
- La PLI aggiunge variabili intere e binarie, indispensabili per decisioni sì/no e costi fissi.
- Arrotondare la soluzione lineare può dare risultati non ammissibili o pessimi.
- Branch and bound divide il problema sulle variabili frazionarie e scarta i rami senza speranza.
- Il gap tra soluzione trovata e miglior limite misura la qualità garantita della soluzione.
- Tagli, formulazioni forti e rimozione delle simmetrie contano spesso più del risolutore.
