Celobrojno programiranje

Celobrojno programiranje je problem matematičke optimizacije ili izvodljivost programa u kojem sve ili neke promenljive su ograničene da budu celobrojne. U mnogim sredinama termin se odnosi na celobrojno linerano programiranje (CLP), u kojem objektna funkcija i ograničenja (osim celobrojnog ograničenja) su linearni.

Celobrojno programiranje je NP-problem. Poseban slučaj je jedan od Karpovih 21 kompletnih problema, tj. 0-1 celobrojno linearno programiranje, u kome su nepoznate binarni brojevi, a ograničenja moraju biti zadovoljena,

Kananočka i standardna forma za CLP

Celobrojno programiranje u kanoničkoj formi je predstavljeno kao:

${\begin{aligned}&{\text{maximize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\\&{\text{and}}&&\mathbf {x} \in \mathbb {Z} ^{n},\end{aligned}}$,

i CLP u standardnoj formi je predstavljen kao

${\begin{aligned}&{\text{maximize}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} +\mathbf {s} =\mathbf {b} ,\\&&&\mathbf {s} \geq \mathbf {0} ,\\&{\text{and}}&&\mathbf {x} \in \mathbb {Z} ^{n},\end{aligned}}$

gde su $\mathbf {c} ,\mathbf {b}$ vektori i $A$ matrica, koja ima celobrojne vrednosti. Primetiti da je slično linearnom programiranju, CLP koji nije u standardnoj formi se može prevesti u standardnu formu eliminisanjem nejednakosti uvođenjem slabe promenjive ($\mathbf {s}$) i zamenom promenjivih koje nisu znakom ograničene sa razlikom dveju promenjivih ograničenih znakom.

Primer

IP polytope with LP relaxation

Graf sa desne strane pokazuje problem.

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

Izvodljive celobrojne tačke prikazane su crvenom, a crvene isprekidane linije prikazuju njihovz konveksnu ljusku, koja je najmanji poliedar koji sadrži sve ove tačke. Plave linije zajedno sa koordinatama iksa definiše poliedar LP relaksacije, koja je data nejednakošću bez celovitog ograničenja. Cilj optimizacije je pomeriti crnu isprekidanu liniju što više nagore, dok dodiruje poliedar. Optimalna rešenja celobrojnog problema su tačke $(1,2)$ i $(2,2)$ koje obe imaju stvarnu vrednosti 2. Jedinstveni optimum relaksacije je $(1.8,2.8)$ sa stvarnim vrednostima 2.8. Primetiti da ako je rešenje zaokruženo na najbliži ceo broj, nije izvodljivo za CLP.

Dokaz NP-problema

Sledi smanjenje sa minimalnog čvora prekrivača na celobrojno programiranje koje će koristiti kao dokaz za NP-problem.

Neka $G=(V,E)$ bude neorijentisani graf. Definisati linearni program na sledeći način:

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

S obzirom na ograničenja $y_{v}$ na 0 ili 1, bilo koje izvodljivo rešenje celobrojnog programiranja je podskup čvorova. Prvo ograničenje upućuje da je makar jedna krajnja tačka svake grane uključena u podskup. Zbog toga rešenje opisuje prekrivača čvora. Pored toga dati neki čvor pokrivača C, $y_{v}$ može biti 1 za bilo koje $v\in C$ i do 0 za bilo koje $v\not \in C$ pa nam daje izvodljivo rešenje za celobrojno programiranje. Tako možemo zaključiti da ako se smanji suma $y_{v}$ takođe ćemo naći minimum čvora prekrivača.

Varijante

Mešano celobrojno linearno programiranje (MCLP) uključuje probleme u kojima samo neke promenjive , $x_{i}$, ograničene da budu celobrojne, dok je drugim dozvoljeno da budu necelobrojne.

0-1 linearno programiranje uključuje probleme u kojima promenjive mogu biti 0 ili 1. Primetiti da bilo koja zaokružena celobrojna promenjiva može biti prikazana kao kombinacija binarnih promenjivih. Na primer, data celobrojna promenjiva, $0\leq x\leq U$, može biti izražena koristeći $\lfloor \log _{2}U\rfloor +1$ binarnih promenjivih:

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

Primeri problema koji se mogu formulisati kao CLP

Veliki broj problema se može formulisati kao CLP. Tu spadaju

• Problem trgovačkog putnika
• Pokrivač čvorova i drugi Problem pokrivanja
• SAT problem

Pošto je krajnja verzija celobrojno linearnog programiranja u NP (rešenja se mogu naći u polinomijalnom vremenu) i tu su NP-potpuni problemi koji se mogu polinomijalno smanjiti na CLP, poslednja verzija celobrojnog linearnog programiranja je NP-kompletni problem.

Aplikacije

Postoje dva glavna razloga za korišćenje celobrojnih konstanti prilikom modeliranja problema kao linearnog programa:

1. Celobrojne promenjive predstavljaju kolićine koje mogu biti samo celi brojevi. Na primer, ne moguće je napraviti 3.7 automobila.
2. Celobrojne vrednosti predstavnjaju odluke pa treba da imaju samo rešenja sa vrednošću 0 ili 1 .

Ova razmatranja se često javljaju u praksi, i zbog toga celobrojno linearno programiranje može da se koristi u mnogim oblastima aplikacija, od kojih su neki ukratko opisani u nastavku.

Proizvodno planiranje

Mešano celobrojno programiranje ima razne aplikacije u industrijskoj proizvodnji, uključujući posao-kupovine modelovanja. Jedan važan primer se dešava u poljoprivrednom proizvodnom planiranju koje uključuje određivanje proizvodnje prinosa za nekoliko useva koje mogu da dele izvore (na primer, zemlju, rad, kapital, semenje, đubrivo, itd). Moguć cilj je maksimalizovati ukupnu proizvodnju, bez prekoračenja raspoloživih resursa. U nekim slučajevima, ovo se može izraziti u smislu linearnog programiranja, ali promenjive moraju da budu celobrojne.

Planiranje

Ovi problemi uključuju servisiranje i raspoređivanje vozila u saobraćajnim mrežama. Na primer, problem može da uključi dodeljivanje autobusa ili podzemnih železnica na pojedinim pravcima tako da satnica bude ispunjena, i takođe da ih opremi sa vozačima. Ovde binarne promenjive odluke pokazuju da li je autobus ili metro dobio rutu vožnje i da li je vozač dobio određeni voz ili metro.

Telekomunikacione mreže

Cilj ovih problema je osmisliti i instalirati mrežu linija tako da unapred definisani uslovi komunikacije budu ispunjeni i ukupan trošak mreže bude minimalan. Ovo zahteva optimizaciju i topologije mreže zajedno sa postavljanjem kapaciteta različitih linija. U mnogim slučajevima, kapaciteti su ograničeni da budu celobrojne veličine. Obično postoje, u zavisnosti od tehnologije koja se koristi, dodatne restrikcije koje mogu biti modelovanje kao linearne nejednakosti sa celobrojnim vrednostima ili binarnim promenjivima.

Mobilne mreže

Zadatak planiranja frekvencije u mobilnoj GSM mreži uključuje raspodelu dostupnih frekvencija kroz antenu tako da korisnik može da se usluži, i da je interferencija svedena na minimum između antena. Ovaj problem može biti formulisan kao celobrojno linearno programiranje u kojem binarne promenjive pokazuju da li je frekvencija dodeljena.

Algoritmi

Naivan način za rešenje CLP je jednostavno brisanje ograničenja da je x integral, rešenje odgovarajućeg LP (koje se zove LP relaksacija CLP), i zatim zaokružiti unos rešenja na LP relaksaciju. Ali, ne samo da ovo rešenje možda neće biti optimalno, možda čak niće biti ni izvodljivo, to ono što može narušiti neka ograničenja.

Korišćenje ukupne nemodularnosti

Dok u većini rešenja LP neće biti zasigurno optimalno, ako CLP ima oblik $\max \mathbf {c} ^{\mathrm {T} }\mathbf {x}$ takvu da $A\mathbf {x} =\mathbf {b}$ gde $A,\mathbf {b} ,$ i $\mathbf {c}$ imaju sve celobrojne ulaze i $A$ je skroz unimodularan, onda svako onsovno izvodljivo rešenje je integral. Shodno tome, rešenje dobijeno simpleks algoritmom će sigurno biti integral. Da bi dokazali da svako izvodljivo rešenje je integral, neka $\mathbf {x}$ bude proizvoljno osnovno i izvodljivo rešenje. Pošto $\mathbf {x}$ je izvodljivo, znamo da $A\mathbf {x} =\mathbf {b}$. Neka $\mathbf {x} _{0}=[x_{n_{1}},x_{n_{2}},\cdots ,x_{n_{j}}]$ bude element koji odgovara bazi kolona za osnovna rešenja $\mathbf {x}$. Po definiciji baze , postoji neki koren podmatrice $B$ od $A$ sa linearnom nezavisnošću kolone takve da $B\mathbf {x} _{0}=\mathbf {b}$.

Pošto kolone $B$ su linearno nezavisne i $B$ je koren, $B$ je nevažan, i zato po pretpostavci, $B$ je unimodularno i $\det(B)=\pm 1$. Takođe, pošto je $B$ nevažna, invertibilna je i zato $\mathbf {x} _{0}=B^{-1}\mathbf {b}$. Po definiciji, $B^{-1}={\frac {B^{adj}}{\det(B)}}=\pm B^{adj}$. Primetite da $B^{adj}$ označava adjugovanu matricu $B$ i integral je zato što je $B$ integral. Zbog toga,

${\begin{aligned}&\Rightarrow B^{-1}=\pm B^{adj}{\text{ is integral.}}\\&\Rightarrow x_{0}=B^{-1}b{\text{ is integral.}}\\&\Rightarrow {\text{Every basic feasible solution is integral.}}\end{aligned}}$

Prema tome, ako je matrica $A$ CLP-a skroz unimodularna, ona će umesto korišćenja CLP algoritma koristiti simpleks algoritam da bi se rešila LP relaksacija, a da bi rešenje bilo celobrojno.

Tačni algoritmi

Kada matrica $A$ nije skroz unimodularna, postoje raznovrsni algoritmi koji se mogu iskoristiti da se tačno reši celobrojno linearno prograrmiranje. Jedna grupa algoritama je metoda sečenja aviona koja radi tako što reši LP relaksaciju i onda dodaje lenaerna ograničenja, koja vode rešenja napred, tako da budu celobrojna i bez izuzimanja bilo koje izvodljive tačke.

Druga grupa algoritama su varijante metode separacija i evaluacija. Na primer, metod grana i rez koji koristi metod separacije i evaluacije i metodu sečenja aviona. Metod separacije i evaluacije ima neke prednosti u odnosu na algoritme koji samo koriste metodu sečenja aviona. Jedna od prednosti je da se algoritam može završiti ranije i sve dok ne bude bar jedno vidljivo integral rešenje pronađeno, iako nije neophodno da bude optimalno, rešenje treba da se vrati. Dalje, metoda separacije i evaluacije mogu se koristiti da vrate više optimalnih rešenja.

Lenstra je 1983 pokazao da, kada je broj promenjivih fiksiran, celobrojno programiranje se može rešiti u polinomijalnom vremenu.

Heuristički metodi

Pošto je celobrojno linearno programiranja NP-teško, mnogi primeri problema su složeni i zbog toga neke heurističke metode moraju da se koriste. Na primer, tabu pretraga se može koristiti za nalaženje rešenja za CLP. Da bi se koristio tabu pretraga za rešavanje CLP-a, kretanja mogu biti definisana kao inkrementiranje ili dekrementiranje celobrojno ograničene promenjive izvodljivog rešenja, dok bi ostale celobrojno ograničene promenjive bile konstantne. Neograničene promenjive su onda rešene. Kratkoročna memorija se može sastojati od prethodnih probanih rešenja dok srednjoročna memorija se može sastojati od vrednosti za celobrojno ograničene promenjive koje su rezultirale visoko objektivnim vrednostima (pod pretpostavkom da je CLP problem maksimizacije). Na kraju, dugoročna memorija može voditi do pretrage celobrojnih vrednosti, koja nisu prethodno probana.

Druge heurističke metode koje mogu primeniti CLP

• Planinarenje
• Simulirano žarenje
• Reaktivna pretraga optimizacije
• Mravlji algoritam
• "Hopfield" neuralne mreže

Takođe postoji veliki broj drugih specifičnih heurističkih problema, kao na primer problem trggovačkog putnika. Primetite da mane heurističkih metoda jesu to da ako ne nađu rešenje, onda se ne može znati da li je to zato što nema izvodljivog rešenja ili zato što algoritam ne može da pronađe rešenje. Dalje, obično je nemoguće da se izračuna koliko je blizu optimalnog rešenja, rešenje koje je dobijenom ovom metodom.

Literatura

• George L. Nemhauser; Wolsey, Laurence A. (1988). Integer and combinatorial optimization. Wiley. ISBN 978-0-471-82819-8. 
• Schrijver, Alexander (1998). Theory of linear and integer programming. John Wiley and Sons. ISBN 978-0-471-98232-6. 
• Wolsey, Laurence A. (1998). Integer programming. Wiley. ISBN 978-0-471-28366-9. 
• Bertsimas, Dimitris; Weismantel, Robert (2005). Optimization over integers. Dynamic Ideas. ISBN 978-0-9759146-2-5. 
• Karlof, John K. (2006). Integer programming: theory and practice. CRC Press. ISBN 978-0-8493-1914-3. 
• H. Paul Williams (2009). Logic and Integer Programming. Springer. ISBN 978-0-387-92279-9. 
• Michael Jünger; Thomas M. Liebling; Denis Naddef; George Nemhauser; William R. Pulleyblank; Gerhard Reinelt; Giovanni Rinaldi; Laurence A. Wolsey, ur. (2009). 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art. Springer. ISBN 978-3-540-68274-5. 
• Der-San Chen; Batson, Robert G.; Dang, Yu (2010). Applied Integer Programming: Modeling and Solution. John Wiley and Sons. ISBN 978-0-470-37306-4. 

Spoljašnje veze

• A Tutorial on Integer Programming
• Integer Programming and Combinatorial Optimization, IPCO
• The Aussois Combinatorial Optimization Workshop