Skip to content
Torna ai risultati

Programmazione Lineare Intera Mista — Ottimizzazione esatta su decisioni continue e intere

Introdotto da
Ralph Gomory (branch-and-bound cuts, 1958); Land & Doig (branch-and-bound, 1960)
Anno
1958–1960
Tipo
Mathematical optimization
Famiglia
Simulation / optimization

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

La Programmazione Lineare Intera Mista (MIP) è un quadro di ottimizzazione matematica in cui alcune variabili decisionali devono assumere valori interi mentre altre possono essere continue.

Generalizza la programmazione lineare ed è ampiamente utilizzata nella ricerca operativa, nella logistica, nella pianificazione, nell'allocazione delle risorse e nella progettazione ingegneristica, dove sorgono naturalmente vincoli di indivisibilità — come decisioni sì/no o quantità in unità intere.

L’intuizione alla base del metodo

Molti problemi di ottimizzazione reali coinvolgono decisioni che non possono essere suddivise: si apre una struttura o non la si apre, si assegna esattamente un lavoratore a un turno, si ordinano unità intere. La programmazione lineare continua ignora queste realtà e può produrre risposte frazionarie non implementabili. La MIP impone l'integralità direttamente nel modello. Il risolutore esplora sistematicamente lo spazio delle soluzioni intere ammissibili tramite branch-and-bound: risolve sottoproblemi continui rilassati per delimitare la migliore soluzione possibile in ciascuna regione, scarta le regioni che non possono migliorare la migliore soluzione intera trovata finora e aggiunge piani di taglio per restringere la ricerca. Il risultato è un piano provabilmente ottimale o quasi ottimale.

Storia

Le fondamenta della programmazione intera furono poste da Ralph Gomory, che introdusse il metodo dei piani di taglio nel 1958, e da Land e Doig, che formalizzarono il branch-and-bound nel 1960. I decenni successivi videro lo sviluppo della teoria del rilassamento LP, della combinatoria poliedrica (Edmonds, Padberg, Grötschel) e, negli anni '90, i risolutori commerciali resero praticabile la MIP su larga scala. Il campo è trattato in modo completo in Nemhauser e Wolsey (1988) e Wolsey (1998).

Quando usarlo

Utilizzare la MIP quando il problema ha un obiettivo e vincoli lineari o linearizzabili e include decisioni che devono essere a valori interi (localizzazione di strutture, pianificazione dell'equipaggio, budget di capitale, progettazione di reti, problemi di taglio). È il metodo di scelta quando si necessita di una soluzione provabilmente ottimale o con un divario di ottimalità limitato e la dimensione del problema è trattabile (migliaia di variabili con risolutori moderni). NON utilizzare la MIP quando l'obiettivo o i vincoli sono altamente non lineari (utilizzare invece la programmazione non lineare o mista intera non lineare), quando il problema è così grande che i metodi esatti sono proibitivi (considerare euristiche o meta-euristiche), o quando le approssimazioni continue sono sufficientemente accurate (utilizzare LP per velocità).

Limiti e considerazioni

  • La complessità nel caso peggiore è NP-hard; il tempo di soluzione può crescere esponenzialmente con il numero di variabili intere.
  • Richiede una formulazione matematica precisa; modelli formulati male possono essere intrattabili anche quando il problema sottostante è gestibile.
  • Elementi non convessi o non lineari richiedono linearizzazione aggiuntiva o risolutori specializzati, aumentando la complessità del modello.
  • I costi di licenza dei risolutori possono essere significativi per gli strumenti commerciali, sebbene esistano alternative open-source di alta qualità.
  • I risultati sono buoni solo quanto il modello: una specifica errata dei vincoli porta a ottimi privi di significato.

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Produce soluzioni provabilmente ottimali con un divario di ottimalità quantificabile, consentendo una rigorosa giustificazione delle decisioni.
  • Gestisce nativamente variabili binarie e intere generali, catturando indivisibilità e vincoli logici del mondo reale.
  • I risolutori moderni (Gurobi, CPLEX, SCIP) sfruttano avanzati branch-and-bound, piani di taglio e presolve per gestire efficientemente istanze di grandi dimensioni.
  • La trasparente formulazione del modello rende le assunzioni esplicite e verificabili da esperti di dominio.
  • Supporta analisi di sensibilità e studi parametrici per comprendere come le soluzioni cambiano con i dati di input.
  • Ampiamente supportato da linguaggi di modellazione (AMPL, GAMS, Pyomo, JuMP) che consentono una rapida prototipazione.

Applicazioni

  • Catena di approvvigionamento e logistica: routing dei veicoli, localizzazione di strutture e ottimizzazione delle scorte con quantità di spedizione intere.
  • Pianificazione della forza lavoro: rostering degli infermieri, assegnazione dell'equipaggio e pianificazione dei turni con variabili di assegnazione binarie.
  • Budget di capitale: selezione di un portafoglio di progetti di investimento indivisibili soggetti a vincoli di budget.
  • Progettazione di reti e telecomunicazioni: espansione della capacità e routing con decisioni binarie di attivazione dei collegamenti.
  • Sistemi energetici: commitment delle unità nelle reti elettriche decidendo quali generatori accendere o spegnere ogni ora.
  • Produzione: lot-sizing, pianificazione delle macchine e problemi di taglio con dimensioni di lotto intere.

Come funziona

Come funziona

1

Definire il modello di ottimizzazione: una funzione obiettivo (combinazione lineare di variabili decisionali da minimizzare o massimizzare), vincoli lineari di disuguaglianza e uguaglianza, e requisiti di integralità. Le variabili continue gestiscono quantità che possono essere frazionarie; le variabili binarie (0/1) o intere generali gestiscono decisioni discrete.

Formula
\min_{x,y}\; c^\top x + d^\top y \quad \text{s.t.}\; Ax + By \leq b,\; x \geq 0,\; y \in \mathbb{Z}^p
2

Risolvere il rilassamento LP (Linear Programming) ignorando temporaneamente i vincoli di integralità. Questo fornisce un limite inferiore (per la minimizzazione) sull'obiettivo MIP ottimale e una soluzione candidata che può essere frazionaria.

Formula
\text{LP relaxation: replace } y \in \mathbb{Z}^p \text{ with } y \geq 0
3

Selezionare una variabile intera frazionaria dalla soluzione del rilassamento LP. Creare due sotto-problemi figli aggiungendo un vincolo di arrotondamento per difetto in uno e un vincolo di arrotondamento per eccesso nell'altro, partizionando lo spazio ammissibile senza perdere alcun punto intero ammissibile.

Formula
\text{Select fractional } y_j^*; \text{ create subproblems: } y_j \leq \lfloor y_j^* \rfloor \text{ and } y_j \geq \lceil y_j^* \rceil
4

Risolvere il rilassamento LP di ciascun sotto-problema. Se il limite è peggiore della migliore soluzione intera trovata finora (l'incumbent), potare quel ramo. Se la soluzione LP risulta essere intera ammissibile, aggiornare l'incumbent se migliora l'obiettivo.

Formula
\text{Prune node if LP bound} \geq \text{incumbent; update incumbent when integer-feasible solution found}
5

Opzionalmente, aggiungere piani di taglio — disuguaglianze valide che tagliano la soluzione LP frazionaria senza rimuovere alcun punto intero ammissibile. I tagli di Gomory sono l'approccio classico; i tagli specifici del problema (ad es., tagli di clique, tagli di flusso) possono ridurre drasticamente la dimensione dell'albero.

Formula
\text{Add Gomory or problem-specific cutting planes to tighten LP relaxation before branching}
6

Interrompere quando l'albero branch-and-bound è completamente esplorato o quando il divario tra la migliore soluzione intera e il limite inferiore globale rientra in una tolleranza specificata dall'utente (ad es., 0.01%). Restituire la soluzione incumbent con il suo certificato di ottimalità.

Formula
\text{Stop when all nodes pruned; return incumbent } x^*, y^* \text{ with optimality gap} \leq \epsilon

Errori comuni

  • Scegliere una tolleranza del divario di ottimalità troppo stretta può far sì che il risolutore venga eseguito indefinitamente; impostare sempre un divario pratico (ad es., 1%) per istanze di grandi dimensioni.
  • La simmetria nel modello (ad es., strutture intercambiabili) crea rami ridondanti e fa esplodere l'albero di ricerca — utilizzare vincoli di rottura della simmetria.
  • Rilassamenti LP deboli (ampio divario di integralità) portano ad alberi branch-and-bound molto grandi; investire tempo nell'aggiungere disuguaglianze valide o nel raffinare la formulazione.
  • Trattare tutte le variabili come intere quando solo alcune ne hanno bisogno è inutilmente costoso; utilizzare variabili binarie solo dove i vincoli logici lo richiedono.
  • Ignorare il warm-starting con una buona soluzione ammissibile iniziale spreca tempo del risolutore nel trovare il primo incumbent.

Domande frequenti

In che modo la MIP differisce dalla programmazione lineare (LP)?

La LP richiede che tutte le variabili decisionali siano continue (a valori reali), il che può produrre soluzioni frazionarie fisicamente infattibili (ad es., 2.7 camion). La MIP aggiunge vincoli di integralità su alcune o tutte le variabili, imponendo soluzioni a numero intero o binarie al costo di una maggiore complessità computazionale.

Quando dovrei usare un'euristica invece della MIP?

Quando il problema ha milioni di variabili, una struttura altamente non lineare, o richiede una soluzione quasi in tempo reale, la MIP esatta può essere troppo lenta. Le meta-euristiche (algoritmi genetici, simulated annealing) possono produrre buone soluzioni rapidamente, ma senza garanzie di ottimalità. La MIP è preferita quando la certificazione della qualità della soluzione è importante.

Cos'è il divario di ottimalità e quanto dovrebbe essere piccolo?

Il divario è (obiettivo incumbent - limite LP) / limite LP, espresso in percentuale. Certifica quanto la migliore soluzione intera conosciuta possa essere lontana dall'ottimo vero. Per la maggior parte delle applicazioni pratiche un divario dello 0.1–1% è sufficiente; divari più stretti richiedono un tempo di risoluzione esponenzialmente maggiore.

La MIP può gestire obiettivi o vincoli non lineari?

La MIP standard presuppone la linearità. Le relazioni non lineari devono essere linearizzate (ad es., approssimazione lineare a tratti, espansione binaria di prodotti) o gestite da risolutori di programmazione non lineare intera mista (MINLP), che sono significativamente più difficili da risolvere.

Quali risolutori sono raccomandati per la MIP?

Commerciali: Gurobi e CPLEX sono i benchmark del settore. Open-source: SCIP, CBC (tramite COIN-OR) e HiGHS sono competitivi per problemi di dimensioni moderate. Tutti supportano interfacce di modellazione standard come AMPL, Pyomo e JuMP.

Metodi correlati

Fonti

  1. Nemhauser, G. L., Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience, New York.

    ISBN: 9780471359432
    Copiato.
  2. Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.

    ISBN: 9780471283669
    Copiato.