Programmazione intera

La programmazione intera (PI; ingl. integer programming, IP) è una branca dell'ottimizzazione matematica che studia problemi in cui alcune o tutte le variabili devono assumere esclusivamente valori interi.

Il caso particolare più studiato è la programmazione lineare intera (PLI; ingl. integer linear programming, ILP), in cui la funzione obiettivo e i vincoli sono lineari. A differenza della programmazione lineare, dove le variabili possono assumere qualsiasi valore reale, il requisito di interezza rende i problemi di PI notevolmente più difficili da risolvere.

La programmazione intera trova ampia applicazione in economia, logistica, pianificazione della produzione e in altri settori in cui le variabili sono per natura discrete (ad esempio, il numero di unità prodotte o il numero di lavoratori).

Definizione e terminologia

Il problema generale della programmazione lineare intera può essere formulato come segue:

Trovare il vettore $x$ che:

massimizza (o minimizza) $c^{T}x$

soggetto ai vincoli:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{Z}}^n$ (tutte le componenti del vettore $x$ sono numeri interi)

dove $x$ è il vettore delle variabili, $c$ e $b$ sono vettori e $A$ è la matrice dei coefficienti.

In base ai requisiti sulle variabili si distinguono i seguenti tipi di problemi:

• Programmazione interamente intera: tutte le variabili devono essere intere.
• Programmazione mista intera (ingl. mixed-integer programming, MIP): solo una parte delle variabili deve essere intera.
• Programmazione booleana (0-1): le variabili assumono solo i valori 0 o 1, consentendo di modellare decisioni logiche del tipo «sì/no».

Proprietà fondamentali e complessità

Complessità computazionale

Il problema della programmazione lineare intera è in generale NP-difficile. Ciò significa che non esiste alcun algoritmo noto in grado di trovare la soluzione ottimale esatta per un problema arbitrario di PI in tempo polinomiale. La complessità è dovuta alla natura combinatoria del problema, poiché il numero di soluzioni intere possibili può crescere esponenzialmente all'aumentare del numero di variabili.

Relazione con la programmazione lineare (rilassamento LP)

Per qualsiasi problema di PI è possibile formulare la sua rilassamento lineare — un problema di programmazione lineare (PL) in cui il requisito di interezza delle variabili viene eliminato. La soluzione del rilassamento LP presenta due importanti proprietà:

1. Può essere trovata molto più rapidamente (in tempo polinomiale).
2. Il valore ottimale della funzione obiettivo del rilassamento LP fornisce una stima (limite superiore per i problemi di massimizzazione e limite inferiore per quelli di minimizzazione) del valore ottimale del problema intero originale.

Tuttavia, il semplice arrotondamento della soluzione frazionaria del rilassamento LP ai numeri interi più vicini non conduce in generale a una soluzione ottimale, né a una soluzione ammissibile del problema intero.

Proprietà di totale unimodularità

Esiste un'importante classe di problemi PLI che si risolvono con la stessa facilità dei rispettivi rilassamenti LP. Si tratta dei problemi in cui la matrice dei vincoli $A$ è totalmente unimodulare (ossia il determinante di qualsiasi sua sottomatrice quadrata è uguale a 0, +1 o −1). Se la matrice $A$ è totalmente unimodulare e il vettore $b$ è intero, allora tutti i vertici del poliedro delle soluzioni ammissibili del rilassamento LP saranno automaticamente interi. Di conseguenza, la soluzione trovata con il metodo del simplesso sarà intera. Esempi di tali problemi sono il problema di trasporto e il problema di assegnazione.

Metodi di soluzione

Per risolvere i problemi generali di PI privi della proprietà di totale unimodularità sono stati sviluppati metodi esatti basati sull'idea dell'enumerazione implicita.

• Metodo branch and bound (ingl. Branch and Bound) — il principale metodo esatto, basato sulla suddivisione sistematica dell'insieme delle soluzioni ammissibili in sottoinsiemi (ramificazione) e sull'eliminazione di quei sottoinsiemi che certamente non contengono la soluzione ottimale. Per valutare la promettenza dei sottoinsiemi viene utilizzato il rilassamento LP.

• Metodo dei piani di taglio (metodo di Gomory; ingl. Cutting Plane Method) — un approccio iterativo che aggiunge progressivamente al problema nuovi vincoli lineari («tagli»). Questi tagli «eliminano» le soluzioni frazionarie del rilassamento LP senza escludere alcuna soluzione intera ammissibile, avvicinando gradualmente la regione ammissibile del rilassamento LP all'inviluppo convesso delle soluzioni intere.

I moderni risolutori utilizzano in genere algoritmi ibridi, come il metodo branch and cut (ingl. Branch and Cut), che combina i vantaggi di entrambi gli approcci.

Esempi e aree di applicazione

La programmazione intera consente di modellare numerosi problemi classici di ottimizzazione combinatoria.

• Problema dello zaino: classico problema di programmazione 0-1 in cui occorre selezionare un insieme di oggetti con il massimo valore totale senza superare il limite di peso complessivo.
• Problema del commesso viaggiatore: problema di ricerca del percorso più breve che attraversi un insieme dato di città. Può essere formulato come problema di programmazione intera, dove le variabili determinano l'inclusione degli archi del grafo nel percorso finale.

Grazie alla sua flessibilità, la PI è uno degli strumenti più richiesti nella ricerca operativa e trova applicazione in settori quali:

• Logistica e gestione della catena di fornitura: ottimizzazione dei percorsi di trasporto, localizzazione dei magazzini, gestione delle scorte.
• Pianificazione della produzione: elaborazione di programmi di produzione, allocazione delle risorse, pianificazione dell'utilizzo dei macchinari.
• Finanza ed economia: composizione del portafoglio di investimenti, pianificazione degli investimenti in conto capitale.
• Telecomunicazioni ed energia: progettazione di reti di comunicazione, pianificazione dell'esercizio delle unità di generazione.

Vedi anche

• Programmazione lineare
• Metodo branch and bound

Note

</references>