Skip to content
Torna ai risultati

Programmazione Intera — IP e Programmazione Lineare Intera Mista (MIP)

Introdotto da
Ralph Gomory (cutting planes, 1958); land-and-doig branch-and-bound (1960)
Anno
1958
Tipo
Mathematical optimisation — exact combinatorial method

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

Dimensione del carattere

A cosa serve?

La programmazione intera (IP), detta anche programmazione lineare intera mista (MIP) quando solo alcune variabili sono ristrette a numeri interi, è una branca dell'ottimizzazione matematica in cui alcune o tutte le variabili decisionali devono assumere valori interi o binari.

Basandosi sulla programmazione lineare, è stata formalizzata attraverso il metodo dei piani di taglio di Ralph Gomory (1958) e l'algoritmo branch-and-bound di Land e Doig (1960), ed è da allora diventata il quadro esatto standard per problemi di pianificazione, assegnazione, instradamento e allocazione di risorse.

L’intuizione alla base del metodo

La programmazione lineare ordinaria trova il punto migliore in una regione ammissibile continua. Ma molte decisioni reali sono discrete: non si possono impiegare 2,7 infermieri o aprire mezzo magazzino. La programmazione intera aggiunge il vincolo che alcune o tutte le variabili debbano essere numeri interi (o scelte binarie 0/1). Il prezzo di tale vincolo è computazionale: l'insieme ammissibile non è più una superficie liscia ma un insieme sparso di punti, e trovarne il migliore può richiedere l'esame di un numero enorme di soluzioni candidate. I solutori gestiscono questo suddividendo intelligentemente il problema in sotto-problemi più piccoli (branching) e potando i rami che non possono superare la migliore soluzione trovata finora (bounding), mentre allo stesso tempo stringono l'approssimazione continua attraverso disuguaglianze aggiunte (piani di taglio).

Storia

La programmazione intera è emersa alla fine degli anni '50, quando i ricercatori cercavano di estendere la programmazione lineare alle decisioni discrete. Ralph Gomory introdusse il metodo sistematico dei piani di taglio nel 1958, dimostrando che qualsiasi programma intero poteva in linea di principio essere risolto aggiungendo un numero finito di tagli. Land e Doig (1960) formalizzarono il branch-and-bound, che divenne l'algoritmo esatto dominante. Wolsey (1998) e Nemhauser e Wolsey (1988) fornirono i trattamenti canonici da manuale su cui il campo fa ancora affidamento. La rivoluzione pratica arrivò con lo sviluppo dei solutori branch-and-cut negli anni '90, che combinavano entrambe le tecniche con euristiche avanzate, e più tardi con l'esplosione delle prestazioni dei solutori commerciali e open-source che oggi consentono applicazioni su larga scala nel mondo reale.

Quando usarlo

Utilizzare la programmazione intera quando le decisioni sono intrinsecamente discrete — scelte binarie sì/no, quantità intere, o vincoli logici on/off — e quando si necessita di una soluzione ottima esatta o quasi esatta con un limite di qualità dimostrabile. Si adatta a problemi di pianificazione, assegnazione di personale e risorse, instradamento di veicoli, localizzazione di impianti, budgeting di capitale e selezione di portafoglio. Non vi è alcun requisito di dimensione minima del campione poiché la IP è un quadro di ottimizzazione deterministica piuttosto che una procedura di inferenza statistica. I tipi di variabili possono essere binari, categorici (codificati come binari) o continui (nel caso misto intero). Il requisito pratico chiave è che il problema possa essere modellato con un obiettivo lineare e vincoli lineari; se l'obiettivo o i vincoli sono non lineari, sono necessarie estensioni di programmazione non lineare intera mista (MINLP).

Limiti e considerazioni

  • La programmazione intera è NP-hard in generale; il tempo di soluzione può crescere esponenzialmente con la dimensione del problema e una formulazione scadente.
  • Una rilassatezza LP debole (ampio divario di integralità) porta ad alberi di ricerca profondi e costosi e a lunghi tempi di esecuzione.
  • L'espansione binaria di variabili categoriche a cardinalità elevata può far esplodere la dimensione del modello.
  • Per istanze molto grandi, i solutori potrebbero dover essere terminati anticipatamente con una tolleranza di divario anziché raggiungere un divario zero.

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 ottimali esatte con un divario di ottimalità certificato, a differenza delle euristiche che non offrono garanzie di qualità.
  • Gestisce nativamente variabili binarie e intere generali, rendendola il quadro naturale per decisioni combinatorie.
  • Applicabile a una vasta gamma di problemi di dominio — pianificazione, instradamento, assegnazione, zaino — con la stessa strumentazione matematica.
  • I moderni solutori branch-and-cut possono risolvere problemi con milioni di variabili e vincoli che sarebbero stati intrattabili decenni fa.

Applicazioni

  • Pianificazione del personale e degli infermieri — assegnazione di turni per soddisfare i requisiti di copertura rispettando le normative sull'orario di lavoro.
  • Instradamento di veicoli e logistica — ricerca di percorsi di consegna a costo minimo sotto vincoli di capacità e finestre temporali.
  • Localizzazione di impianti — decisione su quali magazzini o stabilimenti aprire per minimizzare il costo totale di distribuzione.
  • Budgeting di capitale — selezione di un portafoglio di progetti di investimento entro un budget per massimizzare il rendimento totale.
  • Pianificazione della produzione — determinazione di lotti interi nel tempo per bilanciare costi di setup e costi di mantenimento.
  • Progettazione di reti — scelta di quali collegamenti installare in una rete di comunicazione o di trasporto.

Come funziona

Come funziona

1

Il problema viene formulato come un programma matematico: definire le variabili decisionali (che devono essere dichiarate come intere o binarie dove il problema lo richiede), scrivere una funzione obiettivo lineare da minimizzare o massimizzare, ed elencare tutti i vincoli lineari. Una formulazione stretta — una la cui rilassatezza lineare (LP) continua sia il più vicina possibile all'ottimo intero vero — riduce drasticamente il tempo di soluzione.

2

Le restrizioni di integralità vengono temporaneamente abbandonate per ottenere la rilassatezza LP. Risolvere questa rilassatezza è veloce e fornisce un limite: il suo valore ottimo è sempre almeno pari all'ottimo intero vero (un limite inferiore per la minimizzazione). Se la soluzione della rilassatezza risulta essere intera, il problema è risolto. Altrimenti, il divario tra la rilassatezza e l'integralità guida la ricerca.

3

Una variabile frazionaria nella soluzione della rilassatezza viene selezionata e il problema viene diviso in due sotto-problemi — uno che richiede che la variabile venga arrotondata per difetto, uno per eccesso. Ciascun sotto-problema viene a sua volta rilassato e risolto, creando un albero di ricerca. I rami il cui limite di rilassatezza è peggiore della migliore soluzione intera trovata finora vengono potati senza ulteriore esplorazione.

4

I piani di taglio sono disuguaglianze lineari valide che tagliano parte della regione ammissibile della rilassatezza LP senza rimuovere alcun punto intero ammissibile. L'aggiunta di tagli forti (tagli di Gomory, disuguaglianze di copertura, tagli di clique) stringe il limite LP e riduce il numero di nodi che il solutore deve esplorare.

5

La migliore soluzione intera ammissibile trovata attraverso tutti i nodi esplorati viene restituita come ottimo. Viene riportato il divario di ottimalità — la differenza percentuale tra la migliore soluzione intera e il migliore limite rimanente; un divario pari a zero certifica l'ottimalità globale. Per istanze NP-hard di grandi dimensioni, il solutore può terminare anticipatamente con una tolleranza di divario specificata dall'utente, restituendo una soluzione quasi ottimale con un limite dimostrabile.

Errori comuni

  • Dichiarare variabili come continue quando dovrebbero essere intere — o viceversa — produce silenziosamente soluzioni errate; verificare sempre che i tipi di variabili corrispondano alla realtà fisica del problema.
  • Una formulazione lasca con un ampio divario di rilassatezza LP causa un'eccessiva ramificazione; investire tempo nel rafforzamento della formulazione (disuguaglianze forti, rottura di simmetrie) prima di risolvere.
  • Ignorare il divario di integralità nell'output del solutore: un valore obiettivo riportato è solo la migliore soluzione intera trovata, non necessariamente l'ottimo globale a meno che il divario non sia zero.
  • Applicare la IP a problemi il cui obiettivo o vincoli sono non lineari senza un appropriato trattamento MINLP produrrà modelli errati.
  • Per problemi di pianificazione o instradamento, non aggiungere disuguaglianze valide (come tagli di clique o di copertura) lascia sul tavolo sostanziali guadagni di performance.

Domande frequenti

Qual è la differenza tra IP e MIP?

Nella programmazione intera pura (IP) ogni variabile decisionale deve essere un intero. Nella programmazione lineare intera mista (MIP), alcune variabili sono intere o binarie mentre altre sono permesse di essere continue. La MIP è il quadro più generale e più comunemente utilizzato nella pratica, poiché la maggior parte dei problemi reali mescola scelte discrete con quantità continue.

Perché la programmazione intera è NP-hard se la programmazione lineare è polinomiale?

La programmazione lineare ottimizza su un politopo convesso e può essere risolta in tempo polinomiale con i metodi del simplesso o dei punti interni. L'aggiunta di vincoli di integralità frantuma questa convessità: l'insieme ammissibile diventa un insieme finito ma potenzialmente astronomicamente grande di punti interi, e non è noto alcun algoritmo a tempo polinomiale per trovarne il migliore in generale. La rilassatezza LP fornisce un limite ma non una soluzione diretta.

Come faccio a sapere se la mia soluzione è ottimale?

Il solutore riporta un divario di ottimalità — la differenza percentuale tra la migliore soluzione intera trovata e il migliore limite inferiore rimanente. Un divario dello 0% certifica l'ottimalità globale. Per problemi di grandi dimensioni è possibile impostare una tolleranza di divario (ad es. 1%) e accettare una soluzione quasi ottimale; il limite garantisce comunque che l'ottimo vero non possa essere migliore di quella percentuale.

Cosa rende una formulazione 'stretta' e perché è importante?

Una formulazione stretta è quella la cui rilassatezza LP fornisce un limite vicino all'ottimo intero, lasciando un piccolo divario di integralità. Quando il divario è piccolo, il branch-and-bound deve esplorare meno nodi e termina più velocemente. L'aggiunta di disuguaglianze valide come tagli di Gomory, disuguaglianze di copertura o tagli di clique stringe la formulazione ed è spesso il modo più efficace per accelerare un solutore.

Metodi correlati

Fonti

  1. Wolsey, L.A. (1998). Integer Programming. Wiley.

    ISBN: 9780471283669
    Copiato.
  2. Nemhauser, G.L. & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. Wiley.

    ISBN: 9780471359432
    Copiato.