Kokonaislukuohjelmointi

Kokonaislukuohjelmointiongelma on matemaattinen optimointi- tai tyydyttävyysongelma , jossa joidenkin tai kaikkien muuttujien on oltava kokonaislukuja [1] . Usein termillä tarkoitetaan lineaarista kokonaislukuohjelmointia (ILP), jossa tavoitefunktio ja rajoitukset (kokonaislukuvaatimusta lukuun ottamatta) ovat lineaarisia .

Kokonaislukuohjelmointi on NP-kova ongelma . Erikoistapaus, 0-1 kokonaisluku lineaarinen ohjelmointi, jossa muuttujat ottavat arvot 0 tai 1, on yksi Karpin 21 NP-täydestä tehtävästä .

Kanoniset ja vakiotyypit CLP

Kokonaislukulineaarisen ohjelmoinnin ongelma kanonisessa muodossa ilmaistaan [2]

maksimoida	$\mathbf {c} ^{\mathrm {T} }\mathbf {x}$
olosuhteissa	$A\mathbf {x} \leq \mathbf {b}$
	$\mathbf {x} \geq \mathbf {0}$
ja	${\displaystyle \mathbf {x} \in \mathbb {Z} ^{n))$ ,

ja vakiomuodossa

maksimoida	$\mathbf {c} ^{\mathrm {T} }\mathbf {x}$
olosuhteissa	$A\mathbf {x} +\mathbf {s} =\mathbf {b}$
	$\mathbf {s} \geq \mathbf {0}$
ja	${\displaystyle \mathbf {x} \in \mathbb {Z} ^{n))$

missä ovat vektorit ja on matriisi, jonka kaikki elementit ovat kokonaislukuja. Huomaa, että kuten lineaarisen ohjelmoinnin tapauksessa, ILP-ongelma, joka ei ole vakiomuodossa, voidaan pelkistää vakiomuotoon poistamalla epätasa-arvot ottamalla käyttöön lisämuuttujia ja keinotekoisia muuttujia ja korvaamalla muuttujat, jotka eivät ole ei-negatiivisuusrajoituksen alaisia, kahdella. muuttujia. $\mathbf {c} ,\mathbf {b}$ $A$

Esimerkki

Oikealla oleva kuva esittää seuraavan tehtävän.

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

Kelvolliset kokonaislukupisteet näytetään punaisella ja punaiset katkoviivat osoittavat näiden pisteiden kuperaa runkoa, joka on pienin monikulmio, joka sisältää kaikki nämä pisteet. Siniset viivat yhdessä koordinaattiakselien kanssa määrittelevät lineaarisen vaimennuspolygonin, joka saadaan epäyhtälöillä ilman kokonaislukuvaatimusta. Optimoinnin tavoitteena on siirtää mustaa katkoviivaa niin, että se on mahdollisimman korkealla, mutta koskettaa monikulmiota. Optimaaliset ratkaisut kokonaislukutehtävälle ovat pisteet ja , joissa tavoitefunktio saa arvon 2. Ainoa ratkaisu heikennettyyn (lineaariseen) ongelmaan on piste , jossa tavoitefunktio saa arvon 2.8. Huomaa, että jos pyöristetään lineaarisen ohjelmointitehtävän ratkaisu lähimpään kokonaislukuun, ratkaisu ei kelpaa ILP:lle. ${\näyttötyyli (1,2)}$ ${\näyttötyyli (2,2)}$ $(1.8,2.8)$

Todistus NP-kovuudesta

Seuraava argumentti on kärjen peitteen minimointiongelman pelkistys kokonaislukuohjelmointitehtäväksi, joka todistaa NP-kovuuden.

Antaa olla suuntaamaton kaavio. Määrittelemme lineaarisen ohjelmoinnin ongelman seuraavasti: $G=(V,E)$

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

Ottaen huomioon vaatimuksen, että ne ottavat arvot 0 tai 1, mikä tahansa toteuttamiskelpoinen ratkaisu kokonaislukuohjelmointiin on kärkien osajoukko. Ensimmäinen rajoitus tarkoittaa, että vähintään yksi kunkin reunan pää sisältyy osajoukkoon. Siten ratkaisu antaa huippupisteen peiton. Lisäksi, kun annetaan kärjen peite C, voimme antaa arvon 1 mille tahansa ja 0 mille tahansa , mikä antaa meille kelvollisen ratkaisun kokonaislukuohjelmointiongelmaan. Tästä voidaan päätellä, että minimoimalla summa saadaan myös minimipistepeite [3] . $y_{v}$ $y_{v}$ $v\in C$ $v\not \in C$ $y_{v}$

Vaihtoehdot

MILP :ssä ( Mixed Integer Linear Programming ) vain joidenkin muuttujien on oltava kokonaislukuja, kun taas muut muuttujat voivat olla ei-kokonaislukuja. $x_{i}$

Boolen ohjelmoinnissa muuttujien on saatava arvot 0 tai 1. Huomaa, että mikä tahansa rajoitettu kokonaislukumuuttuja voidaan ilmaista loogisten muuttujien yhdistelmänä [4] . Jos esimerkiksi on olemassa kokonaislukumuuttuja , se voidaan ilmaista loogisina muuttujina: $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}.

Sovellukset

Kokonaislukumuuttujien käyttämiselle lineaaristen ohjelmointiongelmien mallintamiseen on kaksi pääasiallista syytä:

Kokonaislukumuuttujat edustavat määriä, jotka voivat olla vain kokonaislukuja. Esimerkiksi 3,7 autoa ei ole mahdollista rakentaa.
Kokonaislukumuuttujat edustavat päätöksiä, jotka ottavat arvot 0 tai 1.

Nämä käytännöt ovat yleisiä, joten lineaarista kokonaislukuohjelmointia voidaan käyttää monilla alueilla, joista joitain käsitellään lyhyesti alla.

Tuotannon suunnittelu

Sekakokonaislukuohjelmoinnilla on monia sovelluksia valmistuksessa, mukaan lukien aikataulusimulaatiot. Yksi esimerkki esiintyy maatalouden tuotannon suunnittelussa sellaisten tuotteiden tuotoksen määrittämiseksi, joilla voi olla yhteisiä resursseja (kuten maa, työvoima, kustannukset, siemenet, lannoitteet jne.). Mahdollinen optimointitavoite voisi olla tulojen maksimointi ylittämättä käytettävissä olevien resurssien rajoja. Joissakin tapauksissa ongelma voidaan ilmaista lineaarisena ohjelmointitehtävänä, mutta muuttujien on oltava kokonaislukuja.

Suunnittelu

Näissä tehtävissä on tarpeen varmistaa liikenneverkon ylläpito ja aikataulu. Tehtävänä voi olla esimerkiksi linja-autojen tai junien järjestäminen reiteille aikataulun noudattamiseksi sekä kuljettajien hankkiminen liikkuvalle kalustolle. Tässä loogiset muuttujat (eli ottamalla arvon 0 tai 1) määrittävät, onko linja-auto tai juna määrätty reitille ja onko kuljettaja määrätty tietylle linja-autolle/junalle.

Tietoverkot

Tämän tehtävän tarkoituksena on rakentaa tietoverkko siten, että se tarjoaa ennalta määritellyt vaatimukset vähimmäiskustannuksille [5] . Tämä tehtävä edellyttää sekä verkkotopologian että verkkoelementtien kaistanleveyden optimointia. Monissa tapauksissa suoritusteho ilmaistaan diskreeteinä määrinä, mikä johtaa kokonaislukumuuttujiin. Yleensä sovelletaan muita tekniikkakohtaisia rajoituksia, jotka voidaan mallintaa kokonaisluku- tai Boolen muuttujina.

Matkapuhelinverkot

Taajuussuunnittelun tehtävä GSM -matkaviestinverkoissa edellyttää sallittujen taajuuksien jakamista antennien kesken tiedonsiirron varmistamiseksi ja antennien välisten häiriöiden minimoimiseksi [6] . Tämä ongelma voidaan muotoilla lineaariseksi ohjelmointiongelmaksi, jossa loogiset muuttujat heijastavat sitä, onko tietty taajuus osoitettu tietylle antennille.

Algoritmit

Naiivi tapa ratkaista ILP-tehtävä on yksinkertaisesti jättää huomioimatta muuttujien x kokonaislukurajoitus , ratkaista vastaava LP-tehtävä (jota kutsutaan ILP-tehtävän rajoitusten lineaariseksi relaksaatioksi ) ja pyöristää sitten tuloksena olevan ongelman ratkaisukomponentit. Tuloksena oleva ratkaisu ei kuitenkaan välttämättä ole vain ei-optimaalinen, se voi olla jopa mahdoton hyväksyä, toisin sanoen joitain rajoituksia voidaan rikota.

Käyttämällä täydellistä unimodulaarisuutta

Vaikka yleisessä tapauksessa heikennetyn ongelman ratkaisun eheyttä ei taata, jos ILP:llä on muoto ehdoissa , jossa ja sen elementteinä on kokonaislukuja ja se on täysin unimodulaarinen , niin mikä tahansa perusratkaisu on kokonaisluku. Siten simpleksimenetelmän antama ratkaisu on varmasti kokonaisluku [7] . Osoittaaksesi, että mikä tahansa tällaisen ongelman perusratkaisu on kokonaisluku, anna olla mielivaltainen hyväksyttävä ratkaisu. Koska se on hyväksyttävä, tiedämme sen . Olkoon perusratkaisun perussarakkeita vastaavat alkiot . Perusteen määritelmän mukaan matriisissa on jokin neliöosamatriisi , jossa on lineaarisesti riippumattomia sarakkeita siten, että . $\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}$

Koska sarakkeet ovat lineaarisesti riippumattomia ja matriisi on neliö, matriisi on ei-singulaarinen, ja siksi olettaen, että se on unimodulaarinen , . Koska se ei ole yksittäinen, matriisi on käännettävä, ja siksi . Määritelmän mukaan . Tässä tarkoittaa liittomatriisia for ja se on kokonaisluku, koska se on kokonaisluku. Tällä tavalla, $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}$ ${\displaystyle B^{adj))$ $B$ $B$

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

kokonaisluku

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

kokonaisluku

\Nuoli oikealle

Mikä tahansa hyväksyttävä perusratkaisu on kokonaisluku.

Siten, jos ILP-matriisi on täysin unimodulaarinen, ILP-ongelman ratkaisemisen sijaan voidaan käyttää ongelman lineaarista relaksaatiota, joka antaa kokonaislukuratkaisun. $A$

Tarkat algoritmit

Jos matriisi ei ole täysin unimodulaarinen, on olemassa useita algoritmeja, jotka ratkaisevat kokonaislukulineaarisen ohjelmointiongelman tarkasti. Yksi tällaisten algoritmien luokista on leikkaustasomenetelmät (Gomori-menetelmät), jotka toimivat ratkaisemalla heikentyneen lineaarisen ongelman, johon myöhemmin lisätään lineaarisia rajoitteita, jotka katkaisevat tehtävän ei-kokonaislukuratkaisun leikkaamatta kokonaislukuja mahdollisia ratkaisuja. $A$

Toinen algoritmien luokka ovat haara- ja sidomenetelmän variantit . Esimerkiksi haara ja leikkaa -menetelmä , joka yhdistää haara-ja-sido -menetelmän leikkaustasomenetelmiin. Haara- ja sidotuilla menetelmillä on useita etuja verrattuna algoritmeihin, jotka käyttävät vain leikkaustasoja. Yksi eduista on se, että algoritmi voidaan lopettaa aikaisin heti, kun ainakin yksi kelvollinen kokonaislukuratkaisu löytyy, vaikkakaan ei optimaalinen. Lisäksi relaksoidun lineaarisen ongelman ratkaisemisen avulla voidaan arvioida, kuinka kaukana optimaalinen ongelma on. Lopuksi haaroittuneita ja sidottuja menetelmiä voidaan käyttää useiden optimaalisten ratkaisujen saamiseksi.

Lenstra vuonna 1983 osoitti [8] , että kun kyseessä on kiinteä määrä muuttujia, toteutettavissa oleva ratkaisu kokonaislukuohjelmointiongelmaan voidaan löytää polynomiajassa.

Heuristiset menetelmät

Koska lineaarisen kokonaislukuohjelmoinnin ongelmat ovat NP-kovia , monia ongelmia on vaikea ratkaista, joten heuristisia menetelmiä käytetään. Esimerkiksi tabuhakua [9] voidaan käyttää . Tabuhaun käyttämiseksi ILP-ongelman ratkaisemiseksi algoritmivaihe voidaan määritellä kokonaislukumuuttujan lisäämiseksi tai vähentämiseksi samalla kun muut kokonaislukumuuttujat jätetään ennalleen. Sitten löydetään ratkaisu muuttujille, joille ei aseteta kokonaislukurajoitusta. Lyhytaikaista muistia voidaan käyttää aiempien yritysten tallentamiseen, kun taas pidemmän aikavälin muisti voi koostua kokonaislukumuuttujien arvoista, joille saadaan suurempia tavoitefunktioarvoja (olettaen maksimointiongelmasta). Lopuksi pitkäkestoisen muistin avulla voidaan etsiä kokonaislukuarvoja, joita ei ole vielä testattu.

Muita heuristiikkaa, joita voidaan soveltaa ILP:n ratkaisemiseen

On myös joitain muita tehtäväkohtaisia heuristioita, kuten k-opt-heuristiikka matkustavan myyjän ongelmalle. Huomaa, että heurististen menetelmien haittana on, että jos ratkaisun löytäminen epäonnistuu, menetelmä ei määritä, tapahtuiko tämä kelvollisen ratkaisun puuttumisen vuoksi vai siksi, että algoritmi ei löytänyt sitä. Lisäksi on yleensä mahdotonta määrittää, kuinka lähellä tällä menetelmällä saatua optimaalista ratkaisua.

Muistiinpanot

↑ Karmanov, 1986 , s. 11-12.
↑ Papadimitriou, Steiglitz, 1998 .
↑ Erickson .
↑ Williams, HP Logic ja kokonaislukuohjelmointi (epämääräinen) . - 2009. - V. 130. - (International Series in Operations Research & Management Science). - ISBN 978-0-387-92280-5 .
↑ Borndörfer, R.; Grötschel, M. Tietoliikenneverkkojen suunnittelu kokonaislukuohjelmoinnilla (2012). (määrätön)
↑ Sharma, Deepak Frequency Planning (2010). (määrätön)
↑ Joten esimerkiksi kuljetusongelmaa voidaan pitää lineaarisena ohjelmointitehtävänä ja potentiaalien menetelmä tämän ongelman ratkaisemiseksi on itse asiassa simpleksimenetelmä. Simplex-menetelmän perusratkaisu vastaa potentiaalimenetelmän puuta ja vastaavan matriisin determinantti on aina 1. Kokonaislukualkutiedoilla kuljetusongelman ratkaisu simpleksimenetelmällä (tai potentiaalimenetelmällä, joka on ekvivalentti) saa aina kokonaislukuratkaisun.
↑ Lenstra, 1983 .
↑ Glover, 1989 , s. 4–32.

Kirjallisuus

CH Papadimitriou, K. Steiglitz. Kombinatorinen optimointi: algoritmit ja monimutkaisuus. - Mineola, NY: Dover, 1998. - ISBN 0486402584 .
Erickson, J. Integer Programming Reduction (2015). Arkistoitu alkuperäisestä 18. toukokuuta 2015. (määrätön)
HP Williams. Logiikka ja kokonaislukuohjelmointi. - 2009. - V. 130. - (International Series in Operations Research & Management Science). - ISBN 978-0-387-92280-5 .
HW Lenstra. Kokonaislukuohjelmointi kiinteällä määrällä muuttujia // Operaatiotutkimuksen matematiikka. - 1983. - marraskuu ( osa 8 , numero 8 ).
F. Glover. Tabuhaku-Osa II // ORSA-lehti tietojenkäsittelystä. - 1989. - Osa 1 , numero. 3 . - S. 4-32 . - doi : 10.1287/ijoc.2.1.4 .

Lue lisää lukemista varten

Karmanov VG Matemaattinen ohjelmointi. — M .: Nauka , 1986. — 288 s.
Balinski ML Integer Programming: Methods, Uses, Computations // Management Science. - 1965. - Voi. 12, nro 3. - s. 253-313. - doi : 10.1287/mnsc.12.3.253 .
George L. Nemhauser, Laurence A. Wolsey. Kokonaisluku- ja kombinatorinen optimointi. - Wiley, 1988. - ISBN 978-0-471-82819-8 .
Alexander Schrijver. Lineaarisen ja kokonaislukuohjelmoinnin teoria. - John Wiley and Sons, 1998. - ISBN 978-0-471-98232-6 .
Laurence A. Wolsey. Kokonaislukuohjelmointi. - Wiley, 1998. - ISBN 978-0-471-28366-9 .
Dimitris Bertsimas, Robert Weismantel. Optimointi kokonaislukujen yli. - Dynamic Ideas, 2005. - ISBN 978-0-9759146-2-5 .
John K. Karlof. Kokonaislukuohjelmointi: teoria ja käytäntö. - CRC Press, 2006. - ISBN 978-0-8493-1914-3 .
H. Paul Williams. Logiikka ja kokonaislukuohjelmointi. - Springer, 2009. - ISBN 978-0-387-92279-9 .
50 vuotta kokonaislukuohjelmointia 1958-2008: Varhaisista vuosista huipputekniikkaan / 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. Sovellettu kokonaislukuohjelmointi: mallinnus ja ratkaisu. - John Wiley and Sons, 2010. - ISBN 978-0-470-37306-4 .

Linkit

Optimointimenetelmät _
Yksiulotteinen	kultaisen leikkauksen menetelmä Dikotomia Paraabeli menetelmä Verkkohaku Yhtenäinen lohkohakumenetelmä Fibonaccin menetelmä Kolminkertainen haku Piyavsky menetelmä Vahva menetelmä
Nolla järjestys	Gaussin menetelmä Nelder-Meadin menetelmä Hook-Jeeves -menetelmä Rosenbrockin menetelmä Powellin menetelmä
Ensimmäinen tilaus	gradienttilasku Zeutendijkin menetelmä Koordinaattilasku Konjugaattigradienttimenetelmä Kvasi-Newtonilaiset menetelmät Levenberg-Marquardt-algoritmi
toinen tilaus	Newtonin menetelmä Newton-Raphsonin menetelmä Broyden-Fletcher-Goldfarb-Shanno-algoritmi (BFGS)
Stokastinen	Monte Carlon menetelmä Simuloitu hehkutus Evoluutioalgoritmit differentiaalinen evoluutio Ant algoritmi Hiukkasparvimenetelmä Mehiläisyhdyskunnan algoritmi Satunnainen kävelymenetelmä
Lineaariset ohjelmointimenetelmät _	Yksinkertainen menetelmä Gomorin algoritmi Ellipsoidi menetelmä Potentiaalinen menetelmä
Epälineaariset ohjelmointimenetelmät	Jaksottainen neliöllinen ohjelmointi