Programare cu numere întregi

O problemă de programare cu numere întregi este o problemă de optimizare matematică sau de satisfacție în care unele sau toate variabilele trebuie să fie numere întregi [1] . Adesea, termenul se referă la programarea liniară întregi (ILP), în care funcția obiectiv și constrângerile (cu excepția cerinței întregului) sunt liniare .

Programarea cu numere întregi este o problemă NP-hard . Un caz special, programarea liniară cu numere întregi 0-1, în care variabilele iau valorile 0 sau 1, este una dintre cele 21 de probleme NP-complete ale lui Karp .

Tipuri canonice și standard de CLP

Problema programării liniare întregi în forma canonică este exprimată ca [2]

maximiza	$\mathbf {c} ^{\mathrm {T} }\mathbf {x}$
in conditii	$A\mathbf {x} \leq \mathbf {b}$
	$\mathbf {x} \geq \mathbf {0}$
și	$\mathbf {x} \in \mathbb {Z} ^{n)$ ,

și în formă standard

maximiza	$\mathbf {c} ^{\mathrm {T} }\mathbf {x}$
in conditii	$A\mathbf {x} +\mathbf {s} =\mathbf {b}$
	$\mathbf {s} \geq \mathbf {0}$
și	$\mathbf {x} \in \mathbb {Z} ^{n)$

unde sunt vectori și este o matrice, toate elementele fiind numere întregi. Rețineți că, ca și în cazul programării liniare, o problemă ILP care nu este în formă standard poate fi redusă la forma standard prin eliminarea inegalităților prin introducerea de variabile suplimentare și artificiale și înlocuirea variabilelor care nu sunt supuse constrângerii de non-negativitate cu două variabile. $\mathbf {c} ,\mathbf {b}$ $A$

Exemplu

Figura din dreapta arată următoarea sarcină.

{\begin{aligned}\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{aliniat}}

Punctele întregi valide sunt afișate cu roșu, iar liniile punctate roșii arată corpul convex al acestor puncte, care este cel mai mic poligon care conține toate aceste puncte. Liniile albastre, împreună cu axele de coordonate, definesc poligonul de atenuare liniară, care este dat de inegalități fără cerința întregului. Scopul optimizării este de a muta linia punctată neagră astfel încât să fie cât mai sus posibil, dar să atingă poligonul. Soluțiile optime ale problemei întregi sunt punctele și , la care funcția obiectiv ia valoarea 2. Singura soluție la problema slăbită (liniară) este punctul , unde funcția obiectiv ia valoarea 2.8. Rețineți că dacă rotunjim soluția unei probleme de programare liniară la cel mai apropiat număr întreg, soluția va fi invalidă pentru ILP. $(1,2)$ $(2,2)$ $(1.8,2.8)$

Dovada durității NP

Următorul argument este o reducere a problemei de minimizare a acoperirii vârfurilor la o problemă de programare cu numere întregi, care demonstrează duritatea NP.

Fie un grafic nedirecționat. Definim o problemă de programare liniară după cum urmează: $G=(V,E)$

{\begin{aliniat}\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{aligned}}

Având în vedere cerința ca acestea să ia valorile 0 sau 1, orice soluție fezabilă pentru programarea întregilor este un subset de vârfuri. Prima constrângere implică faptul că cel puțin un capăt al fiecărei muchii este inclus în submulțime. Astfel, soluția oferă o acoperire de vârf. De asemenea, având în vedere un vârf de acoperire C, putem atribui o valoare de 1 pentru orice și 0 pentru orice , ceea ce ne oferă o soluție validă pentru problema de programare a întregilor. Din aceasta putem concluziona că la minimizarea sumei , obținem și acoperirea minimă a vârfurilor [3] . $y_{v}$ $y_{v}$ $v\în C$ $v\nu \în C$ $y_{v}$

Opțiuni

În programarea liniară cu numere întregi mixte (MILP), doar unele dintre variabile trebuie să fie întregi, în timp ce restul variabilelor pot fi non-întregi. $x_{i}$

În programarea booleană, variabilele trebuie să ia valorile 0 sau 1. Rețineți că orice variabilă întreagă mărginită poate fi exprimată ca o combinație de variabile booleene [4] . De exemplu, dacă există o variabilă întreagă , aceasta poate fi exprimată în termeni de variabile booleene: $0\leq x\leq U$ $\lfloor \log _{2}U\rfloor +1$

x=x_{1}+2x_{2}+4x_{3}+\ldots +2^{\lfloor \log _{2}U\rfloor }x_{\lfloor \log _{2}U\ rfloor +1}.

Aplicații

Există două motive principale pentru utilizarea variabilelor întregi la modelarea problemelor de programare liniară:

Variabilele întregi reprezintă cantități care pot fi numai numere întregi. De exemplu, nu se poate construi 3,7 mașini.
Variabilele întregi reprezintă decizii care iau valorile 0 sau 1.

Aceste convenții sunt comune în practică și, prin urmare, programarea liniară întregă poate fi utilizată în multe domenii, dintre care unele sunt discutate pe scurt mai jos.

Planificarea producției

Programarea cu numere întregi mixte are multe aplicații în producție, inclusiv simulări de planificare. Un exemplu apare în planificarea producției în agricultură pentru a determina producția de produse care pot avea resurse comune (cum ar fi pământ, forță de muncă, costuri, semințe, îngrășăminte etc.). Un posibil obiectiv de optimizare ar putea fi maximizarea veniturilor fără a depăși limitele resurselor disponibile. În unele cazuri, problema poate fi exprimată ca o problemă de programare liniară, dar variabilele trebuie să fie numere întregi.

Planificare

În aceste sarcini, este necesar să se asigure întreținerea și orarul rețelei de transport. De exemplu, sarcina poate fi aranjarea autobuzelor sau trenurilor de-a lungul rutelor pentru a respecta programul, precum și furnizarea de șoferi pentru materialul rulant. Aici, variabilele booleene (adică, luând valoarea 0 sau 1) determină dacă un autobuz sau un tren este alocat unei rute și dacă un șofer este alocat unui anumit autobuz/tren.

Rețele de date

Scopul acestei sarcini este de a construi o rețea de date astfel încât să ofere cerințe predefinite pentru costul minim [5] . Această sarcină necesită optimizarea atât a topologiei rețelei, cât și a lățimii de bandă a elementelor de rețea. În multe cazuri, debitul este exprimat în cantități discrete, rezultând variabile întregi. De obicei, se aplică alte constrângeri specifice tehnologiei, care pot fi modelate ca variabile întregi sau booleene.

Rețele celulare

Sarcina de planificare a frecvenței în rețelele mobile GSM necesită distribuirea frecvențelor admisibile între antene pentru a asigura comunicarea și a minimiza interferența între antene [6] . Această problemă poate fi formulată ca o problemă de programare liniară în care variabilele booleene reflectă dacă o anumită frecvență este atribuită unei anumite antene.

Algoritmi

Modul naiv de a rezolva problema ILP este pur și simplu ignorarea constrângerii întregi pe variabilele x , rezolvarea problemei LP corespunzătoare (care se numește relaxarea liniară a constrângerilor problemei ILP) și apoi rotunjirea componentelor soluției problemei rezultate. Cu toate acestea, soluția rezultată poate nu numai că nu este optimă, ci poate fi chiar inacceptabilă, adică unele restricții pot fi încălcate.

Folosind unimodularitatea completă

Deși, în cazul general, integralitatea soluției problemei slăbite nu este garantată, dacă ILP are forma în condițiile , unde și are numere întregi ca elemente și este complet unimodulară , atunci orice soluție de bază fezabilă va fi întreagă. Prin urmare, soluția dată de metoda simplex va fi cu siguranță număr întreg [7] . Pentru a arăta că orice soluție de bază a unei astfel de probleme este întreagă, să fie o soluție arbitrară admisibilă. Din moment ce este admisibil, știm că . Fie elementele corespunzătoare coloanelor de bază ale soluției de bază . Prin definiția unei baze, există o submatrice pătrată a unei matrice cu coloane liniar independente astfel încât . $\max \mathbf {c} ^{\mathrm {T} }\mathbf {x}$ $A\mathbf {x} =\mathbf {b}$ $A,\mathbf {b}$ ${\mathbf {c}}$ $A$ $\mathbf {x}$ $\mathbf {x}$ $A\mathbf {x} =\mathbf {b}$ $\mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]$ $\mathbf {x}$ $B$ $A$ $B\mathbf {x} _{0}=\mathbf {b}$

Deoarece coloanele sunt liniar independente și matricea este pătrată, matricea este nesingulară și, prin urmare, în ipoteza că este unimodulară . Deoarece nu este singulară, matricea este inversabilă și, prin urmare, . Prin definiție, . Aici înseamnă matricea de unire pentru și este întreg pentru că este întreg. În acest fel, $B$ $B$ $B$ $B$ $\det(B)=\pm 1$ $B$ $\mathbf {x} _{0}=B^{-1}\mathbf {b}$ $B^{-1}={\frac {B^{adj}}{\det(B)))=\pm B^{adj}$ $B^{adj)$ $B$ $B$

\Rightarrow B^{-1}=\pm B^{adj)

întreg

\Rightarrow x_{0}=B^{-1}b

întreg

\Sageata dreapta

Orice soluție de bază admisibilă este un număr întreg.

Astfel, dacă matricea ILP este complet unimodulară, în loc de a rezolva problema ILP, se poate folosi o relaxare liniară a problemei, care va da o soluție întreagă. $A$

Algoritmi exacti

Dacă matricea nu este complet unimodulară, există o serie de algoritmi care rezolvă exact problema de programare liniară întregă. Una dintre clasele unor astfel de algoritmi este metodele planului de tăiere (metodele Gomori), care funcționează prin rezolvarea unei probleme liniare slăbite cu adăugarea ulterioară a constrângerilor liniare care elimină soluția non-întregică a problemei fără a tăia soluțiile fezabile întregi. $A$

O altă clasă de algoritmi sunt variantele metodei ramificate și legate . De exemplu, metoda ramificării și tăierii , care combină metoda ramificației și legăturii cu metodele planului de tăiere. Metodele ramificate și legate au o serie de avantaje față de algoritmii care folosesc doar planuri de tăiere. Unul dintre avantaje este că algoritmul poate fi terminat mai devreme, de îndată ce se găsește cel puțin o soluție întregă validă, deși nu optimă. În plus, rezolvarea unei probleme liniare relaxate poate fi folosită pentru a estima cât de departe este de cea optimă. În cele din urmă, metodele ramificate și legate pot fi utilizate pentru a obține mai multe soluții optime.

Lenstra în 1983 a arătat [8] că, în cazul unui număr fix de variabile, o soluție fezabilă pentru o problemă de programare cu numere întregi poate fi găsită în timp polinomial.

Metode euristice

Deoarece problemele de programare liniară întregi sunt NP-hard , multe probleme sunt dificil de rezolvat, așa că sunt aplicate metode euristice. De exemplu, o căutare tabu [9] poate fi folosită . Pentru a utiliza căutarea tabu pentru a rezolva problema ILP, un pas de algoritm poate fi definit ca creșterea sau decrementarea unei variabile întregi, lăsând celelalte variabile întregi neschimbate. Apoi se găsește o soluție pentru variabilele cărora nu este impusă constrângerea întregului. Memoria pe termen scurt poate fi folosită pentru a stoca încercările anterioare, în timp ce memoria pe termen lung poate consta din valori ale variabilelor întregi pentru care se obțin valori mai mari ale funcției obiective (presupunând o problemă de maximizare). În cele din urmă, memoria pe termen lung poate fi folosită pentru a căuta valori întregi care nu au fost încă testate.

Alte euristici care pot fi aplicate pentru a rezolva ILP

Urcarea pe o suprafață convexă
Algoritm de recoacere simulat
Optimizare pasivă pentru motoarele de căutare
Algoritmul furnicilor
Rețeaua neuronală Hopfield

Există, de asemenea, alte euristici specifice sarcinii, cum ar fi euristica k-opt pentru problema vânzătorului ambulant. Rețineți că dezavantajul metodelor euristice este că, în caz de eșec în găsirea unei soluții, metoda nu determină dacă acest lucru s-a întâmplat din cauza lipsei unei soluții valide sau pentru că algoritmul nu a reușit să o găsească. În plus, de obicei este imposibil să se determine cât de aproape de soluția optimă obținută prin această metodă.

Note

↑ Karmanov, 1986 , p. 11-12.
↑ Papadimitriou, Steiglitz, 1998 .
↑ Erickson .
↑ Williams, HP Logic și programare cu numere întregi (nedefinită) . - 2009. - V. 130. - (Seria Internațională în Cercetare Operațională și Știința Managementului). - ISBN 978-0-387-92280-5 .
↑ Borndörfer, R.; Grötschel, M. Proiectarea rețelelor de telecomunicații prin programare cu numere întregi (2012). (nedefinit)
^ Sharma, Deepak Frequency Planning (2010). (nedefinit)
↑ Deci, de exemplu, problema transportului poate fi considerată ca o problemă de programare liniară, iar metoda potențialelor pentru rezolvarea acestei probleme este, de fapt, o metodă simplex. Soluția de bază a metodei simplex corespunde arborelui din metoda potențialului, iar matricea corespunzătoare are întotdeauna un determinant de 1. Astfel, cu date inițiale întregi, soluția problemei de transport prin metoda simplex (sau metoda potențialului, care este echivalent) va obține întotdeauna o soluție întreagă.
↑ Lenstra, 1983 .
↑ Glover, 1989 , p. 4–32.

Literatură

CH Papadimitriou, K. Steiglitz. Optimizare combinatorie: algoritmi si complexitate. - Mineola, NY: Dover, 1998. - ISBN 0486402584 .
Erickson, J. Reducerea programării întregi (2015). Arhivat din original pe 18 mai 2015. (nedefinit)
HP Williams. Programare logica si intregi. - 2009. - V. 130. - (Seria Internațională în Cercetare Operațională și Știința Managementului). - ISBN 978-0-387-92280-5 .
HW Lenstra. Programare cu numere întregi cu un număr fix de variabile // Matematica cercetării operaționale. - 1983. - Noiembrie ( vol. 8 , numărul 8 ).
F. Glover. Căutare tabu-Partea a II-a // Jurnalul ORSA de calcul. - 1989. - Vol. 1 , numărul. 3 . - S. 4-32 . - doi : 10.1287/ijoc.2.1.4 .

Lectură pentru lecturi suplimentare

Karmanov VG Programare matematică. — M .: Nauka , 1986. — 288 p.
Balinski ML Integer Programming: Metode, utilizări, calcule // Management Science. - 1965. - Vol. 12, nr.3. - P. 253-313. - doi : 10.1287/mnsc.12.3.253 .
George L. Nemhauser, Laurence A. Wolsey. Optimizare intreg si combinatorie. - Wiley, 1988. - ISBN 978-0-471-82819-8 .
Alexander Schrijver. Teoria programării liniare și întregi. - John Wiley and Sons, 1998. - ISBN 978-0-471-98232-6 .
Laurence A. Wolsey. Programare cu numere întregi. - Wiley, 1998. - ISBN 978-0-471-28366-9 .
Dimitris Bertsimas, Robert Weismantel. Optimizare peste numere întregi. - Idei dinamice, 2005. - ISBN 978-0-9759146-2-5 .
John K. Karlof. Programare cu numere întregi: teorie și practică. - CRC Press, 2006. - ISBN 978-0-8493-1914-3 .
H. Paul Williams. Programare logica si intregi. - Springer, 2009. - ISBN 978-0-387-92279-9 .
50 de ani de programare cu numere întregi 1958-2008: de la primii ani la stadiul tehnicii / Michael Jünger, Thomas M. Liebling, Denis Naddef, George Nemhauser, William R. Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, Laurence A Wolsey. - Springer, 2009. - ISBN 978-3-540-68274-5 .
Der-San Chen, Robert G. Batson, Yu Dang. Programare aplicată cu numere întregi: modelare și soluții. - John Wiley and Sons, 2010. - ISBN 978-0-470-37306-4 .

Link -uri

Metode de optimizare
Unidimensional	metoda secțiunii de aur Dihotomie Metoda parabolelor Căutare în grilă Metoda de căutare uniformă a blocurilor Metoda Fibonacci Căutare ternară metoda Piyavsky Metoda Strongin
Comanda zero	metoda Gauss Metoda Nelder-Mead Metoda Hook-Jeeves metoda Rosenbrock metoda Powell
Prima comanda	coborâre în gradient Metoda Zeutendijk Coordonarea coborârii Metoda gradientului conjugat Metode cvasi-newtoniene Algoritmul Levenberg-Marquardt
a doua comanda	metoda lui Newton Metoda Newton-Raphson Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastic	Metoda Monte Carlo Recoacere simulată Algoritmi evolutivi evolutie diferentiala Algoritmul furnicilor Metoda roiului de particule Algoritmul coloniilor de albine Metoda de mers aleatoriu
Metode de programare liniară	Metoda simplex algoritmul lui Gomori Metoda elipsoidă Metoda potențială
Metode de programare neliniară	Programare secvenţială pătratică