La programmazione intera è una classe di modelli di ottimizzazione in cui alcune variabili decisionali devono assumere valori interi o binari. È uno strumento centrale della ricerca operativa perché permette di rappresentare decisioni discrete: scegliere o no un impianto, assegnare una risorsa, attivare una rotta, pianificare turni, selezionare investimenti, decidere lotti, costruire reti o imporre vincoli logici.
Rispetto alla programmazione lineare, la difficoltà aumenta molto: la regione ammissibile non è più un poliedro continuo da esplorare lungo vertici frazionari, ma un insieme discreto di combinazioni. Anche poche variabili binarie possono generare un numero enorme di configurazioni possibili.
1. Forma generale
Un modello lineare intero misto, spesso chiamato MILP, può essere scritto come:
con vincoli:
x rappresenta variabili continue, y variabili binarie, c e f i coefficienti della funzione obiettivo, A e B le matrici dei vincoli. Se alcune variabili devono essere intere ma non solo binarie, si scrive:
o, più spesso, si distingue tra variabili continue, intere e binarie:
Quando tutte le variabili sono intere si parla di programmazione intera pura; quando convivono variabili continue e intere si parla di programmazione intera mista.
2. Variabili binarie
Nel caso binario:
Le variabili binarie modellano decisioni sì/no:
| Variabile | Interpretazione |
|---|---|
| y_j=1 | decisione attiva, arco aperto, impianto scelto, attività avviata |
| y_j=0 | decisione non attiva, arco chiuso, impianto escluso |
Esempi tipici sono aprire un magazzino, assegnare un operaio a un turno, scegliere un progetto, accendere una macchina, pagare un costo fisso, usare una rotta logistica o includere un vincolo condizionale.
3. Vincoli logici
La forza della programmazione intera sta nel tradurre logica in vincoli lineari. Per esempio, se la scelta A implica la scelta B, si può scrivere:
Se esattamente una tra più alternative deve essere scelta:
Se al massimo una può essere attiva:
Se almeno una deve essere attiva:
Queste relazioni sono semplici ma potenti: permettono di rappresentare esclusioni, precedenze, dipendenze, selezioni e configurazioni di sistema senza introdurre funzioni non lineari.
4. Vincolo Big-M
Il vincolo Big-M collega una quantità continua a una decisione binaria. Se una quantità x può essere positiva solo quando y=1:
Se y=0, allora x=0; se y=1, x può arrivare fino a M. Il parametro M deve essere un limite fisico realistico: un valore troppo grande indebolisce la rilassazione lineare e peggiora il calcolo.
Il Big-M è utile, ma pericoloso. Se M è enorme, il modello resta formalmente corretto ma diventa numericamente debole: il rilassamento lineare permette soluzioni frazionarie poco informative, il branch-and-bound esplora più nodi e il solver può avere problemi di stabilità numerica. Una buona modellazione cerca il valore più stretto possibile di M, derivato da capacità, domanda, limiti fisici o dati operativi.
5. Costi fissi
Se x\gt 0, il modello forza y=1 e quindi il costo fisso viene pagato.
Questo schema appare in impianti produttivi, magazzini, trasporti con costo di apertura, rotte logistiche, lotti minimi e attivazione di macchine. La parte cx rappresenta un costo variabile proporzionale; il termine Fy rappresenta il costo fisso della scelta. Senza variabile binaria, una programmazione lineare pura non può modellare correttamente il salto di costo tra non usare e usare una risorsa.
6. Esempio di assegnamento
Un caso classico è assegnare n operatori a n lavori. Si usa una variabile binaria:
Ogni operatore deve ricevere un lavoro:
e ogni lavoro deve ricevere un operatore:
L’obiettivo può essere minimizzare il costo:
Questo è il problema di assegnamento. In questo caso speciale la struttura del modello è così regolare che spesso si ottengono soluzioni intere anche dal rilassamento lineare; in modelli generali, invece, l’integrità va gestita esplicitamente.
7. Rilassamento lineare
Il rilassamento lineare si ottiene sostituendo i vincoli binari con:
Il modello diventa una programmazione lineare continua. Il suo valore ottimo fornisce un bound: per un problema di minimizzazione, il rilassamento dà un limite inferiore al valore intero ottimo; per un problema di massimizzazione, dà un limite superiore.
La qualità del rilassamento è decisiva. Se il rilassamento è vicino alla soluzione intera, il solver pota molti sottoproblemi. Se è molto debole, il solver deve esplorare molte combinazioni. Per questo due formulazioni matematicamente equivalenti possono avere tempi di soluzione completamente diversi.
8. Branch-and-bound, tagli ed euristiche
I problemi interi si risolvono spesso con branch-and-bound. L’idea è:
- risolvere il rilassamento lineare;
- se la soluzione è intera, è candidata ottima;
- se una variabile binaria è frazionaria, si ramifica imponendo y_j=0 in un ramo e y_j=1 nell’altro;
- si usano i bound per potare rami che non possono migliorare la soluzione migliore nota.
I solver moderni aggiungono piani di taglio, euristiche primal, preprocessing, riduzione dei domini, simmetria, branching intelligente e strategie di ricerca. Per questo il metodo pratico viene spesso chiamato branch-and-cut quando i tagli sono integrati nell’albero di ricerca.
9. Formulazioni forti
Una formulazione è forte quando il suo rilassamento lineare è stretto rispetto al politopo intero. In pratica, una buona formulazione:
| Scelta di modellazione | Effetto |
|---|---|
| Big-M piccoli e giustificati | bound più forti e meno instabilità numerica |
| vincoli logici diretti | meno variabili ausiliarie inutili |
| limiti superiori e inferiori stretti | domini più piccoli |
| tagli validi | rilassamento più vicino all’inviluppo intero |
| eliminazione di simmetrie | meno soluzioni equivalenti da esplorare |
La programmazione intera è quindi tanto modellazione quanto calcolo. Un solver potente non compensa automaticamente una formulazione debole.
10. Applicazioni
La programmazione intera compare in:
| Area | Esempi |
|---|---|
| Logistica | localizzazione di impianti, instradamento, carichi, turni |
| Produzione | lotti, setup, sequenziamento, capacità macchina |
| Energia | unit commitment, reti, accumuli, manutenzione |
| Finanza | selezione di portafoglio con vincoli discreti |
| Informatica | allocazione di risorse, scheduling, reti |
| Gestione progetti | scelta di investimenti, precedenze, budget |
Molti problemi reali mescolano quantità continue e scelte discrete: quanta merce spedire e se aprire la rotta; quanta produrre e se attivare la linea; quanta energia generare e se accendere un impianto.
11. Errori comuni
Il primo errore è arrotondare una soluzione di programmazione lineare e sperare che resti ottima o ammissibile. L’arrotondamento può violare vincoli di capacità, assegnamento, domanda o logica.
Il secondo errore è scegliere Big-M enormi. Il modello sembra più flessibile, ma diventa più debole e numericamente fragile. Il terzo è introdurre variabili binarie dove una struttura di rete o una formulazione lineare speciale garantirebbe già soluzioni intere.
Il quarto errore è valutare solo il valore obiettivo, ignorando tempi di soluzione, gap di ottimalità, robustezza dei dati e interpretabilità della soluzione. Nei problemi grandi, una soluzione buona con gap certificato può essere più utile di una ricerca infinita dell’ottimo esatto.
Vedi anche: Programmazione lineare, Branch-and-bound, Problema di assegnamento, Ricerca operativa, Ottimizzazione su reti, Formulario di ricerca operativa.