Programmazione intera - Integer programming

Un problema di programmazione intera è un'ottimizzazione matematica o un programma di fattibilità in cui alcune o tutte le variabili sono limitate ad essere intere . In molti contesti il ​​termine si riferisce alla programmazione lineare intera (ILP), in cui la funzione obiettivo ei vincoli (diversi dai vincoli interi) sono lineari .

La programmazione intera è NP-completa . In particolare, il caso speciale della programmazione lineare intera 0-1, in cui le incognite sono binarie, e solo le restrizioni devono essere soddisfatte, è uno dei 21 problemi NP-completi di Karp .

Se alcune variabili decisionali non sono discrete, il problema è noto come problema di programmazione a numeri interi misti .

Modulo canonico e standard per ILP

Nella programmazione lineare intera, la forma canonica è distinta dalla forma standard . Un programma lineare intero in forma canonica si esprime così (si noti che è il vettore che deve essere deciso): ${\displaystyle \mathbf {x}}$

${\displaystyle {\begin{allineato}&{\text{massimizza}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{soggetto a}}&&A\mathbf {x} \leq \mathbf {b} , \\&&&\mathbf {x} \geq \mathbf {0} , \\&{\text{and}}&&\mathbf {x} \in \mathbb {Z} ^{n},\end{allineato}}}$

e un ILP in forma standard è espresso come

${\displaystyle {\begin{allineato}&{\text{massimizza}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{soggetto a}}&&A\mathbf {x} +\mathbf {s} =\mathbf {b} ,\\&&&\mathbf {s} \geq \mathbf {0} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\\ &{\text{e}}&&\mathbf {x} \in \mathbb {Z} ^{n},\end{allineato}}}$

dove sono vettori ed è una matrice, dove tutte le voci sono numeri interi. Come con i programmi lineari, gli ILP non in forma standard possono essere convertiti in forma standard eliminando le disuguaglianze, introducendo variabili slack ( ) e sostituendo le variabili non vincolate al segno con la differenza di due variabili vincolate al segno ${\ Displaystyle \ mathbf {c}, \ mathbf {b}}$${\displaystyle A}$${\displaystyle \mathbf {s}}$

Esempio

Il grafico a destra mostra il seguente problema.

${\displaystyle {\begin{allineato}\max &{\text{ }}y\\-x+y&\leq 1\\3x+2y&\leq 12\\2x+3y&\leq 12\\x,y&\ geq 0\\x,y&\in \mathbb {Z} \end{allineato}}}$

I punti interi ammissibili sono mostrati in rosso e le linee tratteggiate rosse indicano il loro guscio convesso, che è il più piccolo poliedro convesso che contiene tutti questi punti. Le linee blu insieme agli assi coordinati definiscono il poliedro del rilassamento LP, che è dato dalle disuguaglianze senza il vincolo di integralità. L'obiettivo dell'ottimizzazione è spostare la linea tratteggiata nera verso l'alto pur toccando il poliedro. Le soluzioni ottime del problema intero sono i punti ed entrambi hanno valore oggettivo 2. L'unico ottimo del rilassamento è con valore oggettivo 2.8. Se la soluzione del rilassamento viene arrotondata agli interi più vicini, non è fattibile per l'ILP. ${\displaystyle (1,2)}$${\displaystyle (2,2)}$${\displaystyle (1.8,2.8)}$

Prova di durezza NP

Quella che segue è una riduzione dalla copertura minima dei vertici alla programmazione intera che servirà come prova della durezza NP.

Sia un grafo non orientato. Definire un programma lineare come segue: ${\displaystyle G=(V,E)}$

${\displaystyle {\begin{allineato}\min \sum _{v\in V}y_{v}\\y_{v}+y_{u}&\geq 1&&\forall uv\in E\\y_{v }&\geq 0&&\forall v\in V\\y_{v}&\in \mathbb {Z} &&\forall v\in V\end{allineato}}}$

Dato che i vincoli si limitano a 0 o 1, qualsiasi soluzione ammissibile al programma intero è un sottoinsieme di vertici. Il primo vincolo implica che almeno un punto finale di ogni arco sia incluso in questo sottoinsieme. Pertanto, la soluzione descrive una copertura dei vertici. Inoltre, data una copertura di vertici C, può essere impostata a 1 per any e a 0 per any , fornendo così una soluzione fattibile per il programma intero. Quindi possiamo concludere che se minimizziamo la somma di abbiamo anche trovato la copertura minima dei vertici. ${\displaystyle y_{v}}$${\displaystyle y_{v}}$${\displaystyle v\in C}$${\displaystyle v\not \in C}$${\displaystyle y_{v}}$

varianti

La programmazione lineare intera mista ( MILP ) comporta problemi in cui solo alcune delle variabili, , sono vincolate ad essere intere, mentre altre variabili possono essere non intere. ${\displaystyle x_{i}}$

La programmazione lineare zero uno (o programmazione intera binaria ) comporta problemi in cui le variabili sono limitate a 0 o 1. Qualsiasi variabile intera limitata può essere espressa come una combinazione di variabili binarie. Ad esempio, data una variabile intera, , la variabile può essere espressa utilizzando variabili binarie: ${\displaystyle 0\leq x\leq U}$${\displaystyle \lfloor \log _{2}U\rfloor +1}$

${\displaystyle x=x_{1}+2x_{2}+4x_{3}+\cdots +2^{\lfloor \log _{2}U\rfloor }x_{\lfloor \log _{2}U\ piano +1}.}$

Applicazioni

Ci sono due ragioni principali per usare le variabili intere quando si modellano i problemi come un programma lineare:

1. Le variabili intere rappresentano quantità che possono essere solo intere. Ad esempio, non è possibile costruire auto 3.7.
2. Le variabili intere rappresentano le decisioni (ad esempio se includere un arco in un grafico ) e quindi dovrebbero assumere solo il valore 0 o 1.

Queste considerazioni si verificano frequentemente nella pratica e quindi la programmazione lineare intera può essere utilizzata in molte aree applicative, alcune delle quali sono descritte brevemente di seguito.

Piano di produzione

La programmazione di numeri interi misti ha molte applicazioni nelle produzioni industriali, inclusa la modellazione del job-shop. Un esempio importante si verifica nella pianificazione della produzione agricola comporta la determinazione della resa di produzione per diverse colture che possono condividere risorse (ad esempio terra, lavoro, capitale, semi, fertilizzanti, ecc.). Un possibile obiettivo è massimizzare la produzione totale, senza eccedere le risorse disponibili. In alcuni casi, questo può essere espresso in termini di un programma lineare, ma le variabili devono essere vincolate a essere intere.

Programmazione

Questi problemi riguardano la pianificazione dei servizi e dei veicoli nelle reti di trasporto. Ad esempio, un problema può comportare l'assegnazione di autobus o metropolitane a percorsi individuali in modo da rispettare un orario e anche dotarli di autisti. Qui le variabili decisionali binarie indicano se un autobus o una metropolitana è assegnato a un percorso e se un conducente è assegnato a un particolare treno o metropolitana. La tecnica di programmazione zero-one è stata applicata con successo per risolvere un problema di selezione dei progetti in cui i progetti si escludono a vicenda e/o sono tecnologicamente interdipendenti. Viene utilizzato in un caso speciale di programmazione intera, in cui tutte le variabili di decisione sono intere. Può assumere i valori come zero o uno.

Partizionamento territoriale

Il problema del partizionamento territoriale o distrettuale consiste nel suddividere una regione geografica in distretti al fine di pianificare alcune operazioni tenendo conto di criteri o vincoli diversi. Alcuni requisiti per questo problema sono: contiguità, compattezza, equilibrio o equità, rispetto dei confini naturali e omogeneità socio-economica. Alcune applicazioni per questo tipo di problema includono: distretto politico, distretto scolastico, distretto dei servizi sanitari e distretto della gestione dei rifiuti.

Reti di telecomunicazioni

L'obiettivo di questi problemi è progettare una rete di linee da installare in modo che venga soddisfatto un insieme predefinito di requisiti di comunicazione e il costo totale della rete sia minimo. Ciò richiede l'ottimizzazione sia della topologia della rete che l'impostazione delle capacità delle varie linee. In molti casi, le capacità sono vincolate ad essere quantità intere. Di solito ci sono, a seconda della tecnologia utilizzata, ulteriori restrizioni che possono essere modellate come disuguaglianze lineari con variabili intere o binarie.

Reti cellulari

Il compito della pianificazione delle frequenze nelle reti mobili GSM prevede la distribuzione delle frequenze disponibili attraverso le antenne in modo che gli utenti possano essere serviti e le interferenze tra le antenne siano ridotte al minimo. Questo problema può essere formulato come un programma lineare intero in cui le variabili binarie indicano se una frequenza è assegnata a un'antenna.

Altre applicazioni

• Corrispondenza del flusso di cassa
• Ottimizzazione del sistema energetico
• Guida UAV

Algoritmi

Il modo ingenuo per risolvere un ILP è semplicemente rimuovere il vincolo che x è intero, risolvere il corrispondente LP (chiamato rilassamento LP dell'ILP), e quindi arrotondare gli elementi della soluzione al rilassamento LP. Ma, non solo questa soluzione potrebbe non essere ottimale, potrebbe anche non essere fattibile; cioè, potrebbe violare qualche vincolo.

Usando l'unimodularità totale

Mentre in generale la soluzione al rilassamento LP non sarà garantita come integrale, se l'ILP ha la forma tale che dove e ha tutti gli elementi interi ed è totalmente unimodulare , allora ogni soluzione ammissibile di base è integrale. Di conseguenza, la soluzione restituita dall'algoritmo del simplesso è garantita come integrale. Per dimostrare che ogni soluzione ammissibile di base è integrale, sia una soluzione ammissibile di base arbitraria. Poiché è fattibile, lo sappiamo . Siano gli elementi corrispondenti alle colonne di base per la soluzione di base . Per definizione di base, esiste una sottomatrice quadrata di con colonne linearmente indipendenti tali che . ${\ Displaystyle \ max \ mathbf {c} ^ {\ mathrm {T} } \ mathbf {x} }$${\displaystyle A\mathbf {x} =\mathbf {b}}$${\displaystyle A}$${\displaystyle \mathbf {b}}$${\displaystyle A}$${\displaystyle \mathbf {x}}$${\displaystyle \mathbf {x}}$${\displaystyle A\mathbf {x} =\mathbf {b}}$${\displaystyle \mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]}$${\displaystyle \mathbf {x}}$${\displaystyle B}$${\displaystyle A}$${\displaystyle B\mathbf {x} _{0}=\mathbf {b}}$

Poiché le colonne di sono linearmente indipendenti ed è quadrata, è non singolare, e quindi per ipotesi, è unimodulare e quindi . Inoltre, essendo non singolare, è invertibile e quindi . Per definizione, . Qui denota l' adiuvato di ed è integrale perché è integrale. Perciò, ${\displaystyle B}$${\displaystyle B}$${\displaystyle B}$${\displaystyle B}$${\displaystyle \det(B)=\pm 1}$${\displaystyle B}$${\displaystyle \mathbf {x} _{0}=B^{-1}\mathbf {b} }$${\displaystyle B^{-1}={\frac {B^{adj}}{\det(B)}}=\pm B^{adj}}$${\displaystyle B^{agg.}}$${\displaystyle B}$${\displaystyle B}$

${\displaystyle {\begin{aligned}&\Rightarrow B^{-1}=\pm B^{adj}{\text{ è integrale.}}\\&\Rightarrow x_{0}=B^{-1 }b{\text{ è integrale.}}\\&\Rightarrow {\text{Ogni soluzione ammissibile di base è integrale.}}\end{allineato}}}$

Quindi, se la matrice di un ILP è totalmente unimodulare, anziché utilizzare un algoritmo ILP, è possibile utilizzare il metodo del simplesso per risolvere il rilassamento LP e la soluzione sarà intera. ${\displaystyle A}$

Algoritmi esatti

Quando la matrice non è totalmente unimodulare, ci sono una varietà di algoritmi che possono essere usati per risolvere esattamente programmi lineari interi. Una classe di algoritmi sono i metodi del piano di taglio che funzionano risolvendo il rilassamento LP e quindi aggiungendo vincoli lineari che guidano la soluzione verso l'essere intero senza escludere alcun punto intero ammissibile. ${\displaystyle A}$

Un'altra classe di algoritmi sono le varianti del metodo branch and bound . Ad esempio, il metodo branch and cut che combina i metodi branch and bound e il piano di taglio. Gli algoritmi branch and bound presentano una serie di vantaggi rispetto agli algoritmi che utilizzano solo piani di taglio. Un vantaggio è che gli algoritmi possono essere terminati in anticipo e finché è stata trovata almeno una soluzione integrale, può essere restituita una soluzione fattibile, anche se non necessariamente ottimale. Inoltre, le soluzioni dei rilassamenti LP possono essere utilizzate per fornire una stima del caso peggiore di quanto sia lontana dall'ottimalità la soluzione restituita. Infine, i metodi branch and bound possono essere utilizzati per restituire più soluzioni ottimali.

Algoritmi esatti per un piccolo numero di variabili

Supponiamo è un m -by- n matrice numero intero ed è un m intero vettore -da-1. Ci concentriamo sul problema di fattibilità, che consiste nel decidere se esiste un vettore n -per-1 che soddisfi . ${\displaystyle A}$${\displaystyle \mathbf {b}}$${\displaystyle \mathbf {x}}$${\displaystyle A\mathbf {x} \leq \mathbf {b}}$

Sia V il massimo valore assoluto dei coefficienti in e . Se n (il numero di variabili) è una costante fissa, allora il problema di fattibilità può essere risolto nel polinomio temporale in m e log V . Questo è banale per il caso n =1. Il caso n = 2 è stato risolto nel 1981 da Herbert Scarf . Il caso generale è stato risolto nel 1983 da Hendrik Lenstra , combinando le idee di Laszlo Lovasz e Peter van Emde Boas . ${\displaystyle A}$${\displaystyle \mathbf {b}}$

Nel caso speciale di 0-1 ILP, l'algoritmo di Lenstra è equivalente all'enumerazione completa: il numero di tutte le possibili soluzioni è fissato (2 ⁿ ), e la verifica della fattibilità di ciascuna soluzione può essere eseguita in tempo poly( m , log V ) . Nel caso generale, dove ogni variabile può essere un intero arbitrario, l'enumerazione completa è impossibile. Qui, l'algoritmo di Lenstra utilizza idee da Geometria dei numeri . Trasforma il problema originale in uno equivalente con la seguente proprietà: o l'esistenza di una soluzione è ovvia, oppure il valore di (la variabile n -esima) appartiene a un intervallo la cui lunghezza è limitata da una funzione di n . In quest'ultimo caso, il problema si riduce a un numero limitato di problemi di dimensione inferiore. ${\displaystyle \mathbf {x}}$${\displaystyle x_{n}}$

L'algoritmo di Lenstra implica che ILP è risolvibile in tempo polinomiale anche nel caso duale, in cui n è variabile ma m (il numero di vincoli) è costante.

L'algoritmo di Lenstra è stato successivamente migliorato da Kannan, Frank e Tardos. Il runtime migliorato è , dove è il numero di bit di input, che è in . ${\displaystyle n^{2.5n}\cdot \ell}$${\displaystyle \ell}$${\displaystyle {\text{poli}}(m,\log {V})}$

Metodi euristici

Poiché la programmazione lineare intera è NP-difficile , molte istanze del problema sono intrattabili e quindi è necessario utilizzare metodi euristici. Ad esempio, la ricerca tabu può essere utilizzata per cercare soluzioni agli ILP. Per utilizzare la ricerca tabu per risolvere gli ILP, gli spostamenti possono essere definiti come l'incremento o il decremento di una variabile vincolata da un numero intero di una soluzione ammissibile, mantenendo costanti tutte le altre variabili vincolate da un numero intero. Le variabili non ristrette vengono quindi risolte per. La memoria a breve termine può consistere in soluzioni precedentemente provate mentre la memoria a medio termine può consistere in valori per le variabili vincolate da interi che hanno portato a valori oggettivi elevati (assumendo che l'ILP sia un problema di massimizzazione). Infine, la memoria a lungo termine può guidare la ricerca verso valori interi che non sono stati precedentemente provati.

Altri metodi euristici che possono essere applicati agli ILP includono

• Arrampicata in collina
• Ricottura simulata
• Ottimizzazione della ricerca reattiva
• Ottimizzazione della colonia di formiche
• Reti neurali Hopfieldfield

Ci sono anche una varietà di altre euristiche specifiche del problema, come l' euristica k-opt per il problema del commesso viaggiatore. Uno svantaggio dei metodi euristici è che se non riescono a trovare una soluzione, non è possibile determinare se è perché non esiste una soluzione fattibile o se l'algoritmo semplicemente non è stato in grado di trovarne una. Inoltre, di solito è impossibile quantificare quanto sia vicina all'ottimale una soluzione restituita da questi metodi.

Programmazione di numeri interi scarsi

Capita spesso che la matrice che definisce il programma intero sia sparsa . In particolare, ciò si verifica quando la matrice ha una struttura a blocchi, come avviene in molte applicazioni. La scarsità della matrice può essere misurata come segue. Il grafico di ha vertici corrispondenti alle colonne di e due colonne formano un bordo se ha una riga in cui entrambe le colonne hanno voci diverse da zero. Equivalentemente, i vertici corrispondono a variabili e due variabili formano un arco se condividono una disuguaglianza. La misura della scarsità di è il minimo tra la profondità dell'albero del grafico di e la profondità dell'albero del grafico della trasposta di . Sia la misura numerica di definita come il massimo valore assoluto di qualsiasi voce di . Sia il numero di variabili del programma intero. Quindi è stato dimostrato nel 2018 che la programmazione intera può essere risolta in un tempo trattabile fortemente polinomiale e a parametro fisso parametrizzato da e . Cioè, per alcune funzioni calcolabili e alcune costanti , la programmazione intera può essere risolta nel tempo . In particolare, il tempo è indipendente dal membro destro e dalla funzione obiettivo . Inoltre, contrariamente al risultato classico di Lenstra, dove il numero di variabili è un parametro, qui il numero di variabili è una parte variabile dell'input. ${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$ ${\displaystyle d}$${\displaystyle A}$${\displaystyle A}$${\displaystyle A}$${\displaystyle a}$${\displaystyle A}$${\displaystyle A}$${\displaystyle n}$${\displaystyle a}$${\displaystyle d}$${\displaystyle f}$${\displaystyle k}$${\displaystyle f(a,d)n^{k}}$${\displaystyle b}$${\displaystyle c}$${\displaystyle n}$${\displaystyle n}$

Guarda anche

• Minimi quadrati vincolati

Riferimenti

Ulteriori letture

• George L. Nemhauser ; Laurence A. Wolsey (1988). Ottimizzazione intera e combinatoria . Wiley. ISBN 978-0-471-82819-8.
• Alexander Schrijver (1998). Teoria della programmazione lineare e intera . John Wiley e figli. ISBN 978-0-471-98232-6.
• Laurence A. Wolsey (1998). Programmazione intera . Wiley. ISBN 978-0-471-28366-9.
• Dimitris Bertsimas; Robert Weismantel (2005). Ottimizzazione su numeri interi . Idee dinamiche. ISBN 978-0-9759146-2-5.
• John K. Karlof (2006). Programmazione intera: teoria e pratica . CRC Press. ISBN 978-0-8493-1914-3.
• H.Paul Williams (2009). Logica e programmazione intera . Springer. ISBN 978-0-387-92279-9.
• Michael Junger; Thomas M. Liebling; Denis Naddef; George Nemhauser ; William R. Pulleyblank ; Gerhard Reinelt; Giovanni Rinaldi; Laurence A. Wolsey, eds. (2009). 50 anni di programmazione intera 1958-2008: dai primi anni allo stato dell'arte . Springer. ISBN 978-3-540-68274-5.
• Der San Chen; Robert G. Batson; Yu Dang (2010). Programmazione intera applicata: modellazione e soluzione . John Wiley e figli. ISBN 978-0-470-37306-4.
• Gerard Sierksma; Yori Zwol (2015). Ottimizzazione lineare e intera: teoria e pratica . CRC Press. ISBN 978-1-498-71016-9.

link esterno

• Un tutorial sulla programmazione intera
• Programmazione intera di conferenza e ottimizzazione combinatoria, IPCO
• Il laboratorio di ottimizzazione combinatoria di Aussois