Integer programozás

Az egészszámú programozási probléma egy matematikai optimalizálási vagy kielégítési probléma , amelyben a változók egy részének vagy mindegyikének egész számnak kell lennie [1] . A kifejezés gyakran az egészszámú lineáris programozásra (ILP) utal, amelyben a célfüggvény és a megszorítások (az egész számra vonatkozó követelmény kivételével) lineárisak .

Az egész számok programozása NP-nehéz probléma . Egy speciális eset, a 0-1 integer lineáris programozás, amelyben a változók 0 vagy 1 értéket vesznek fel, Karp 21 NP-teljes feladatának egyike .

A CLP kanonikus és szabványos típusai

Az egész számú lineáris programozás problémáját kanonikus formában a következőképpen fejezzük ki: [2]

maximalizálni	$\mathbf {c} ^{\mathrm {T} }\mathbf {x}$
feltételek mellett	$A\mathbf {x} \leq \mathbf {b}$
	$\mathbf {x} \geq \mathbf {0}$
és	${\displaystyle \mathbf {x} \in \mathbb {Z} ^{n))$ ,

és szabványos formában

maximalizálni	$\mathbf {c} ^{\mathrm {T} }\mathbf {x}$
feltételek mellett	$A\mathbf {x} +\mathbf {s} =\mathbf {b}$
	$\mathbf {s} \geq \mathbf {0}$
és	${\displaystyle \mathbf {x} \in \mathbb {Z} ^{n))$

ahol vektorok és egy mátrix, amelynek minden eleme egész szám. Vegye figyelembe, hogy a lineáris programozáshoz hasonlóan a nem szabványos formájú ILP-probléma standard formára redukálható az egyenlőtlenségek kiküszöbölésével további és mesterséges változók bevezetésével, és a nem negativitási megkötés alá nem tartozó változók kettővel való helyettesítésével. változók. $\mathbf {c} ,\mathbf {b}$ $A$

Példa

A jobb oldali ábra a következő feladatot mutatja.

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

Az érvényes egész pontokat pirossal, a piros szaggatott vonalak pedig a pontok konvex héját mutatják, amely a legkisebb sokszög, amely ezeket a pontokat tartalmazza. A kék vonalak a koordinátatengelyekkel együtt meghatározzák a lineáris csillapítási sokszöget, amelyet egész szám követelmény nélküli egyenlőtlenségek adnak meg. Az optimalizálás célja a fekete pontozott vonal mozgatása, hogy az a lehető legmagasabban legyen, de érintse a sokszöget. Az egész feladat optimális megoldása a és pont , ahol a célfüggvény 2 értéket vesz fel. A gyengített (lineáris) probléma egyetlen megoldása az a pont , ahol a célfüggvény a 2,8 értéket veszi fel. Figyeljük meg, hogy ha egy lineáris programozási feladat megoldását a legközelebbi egész számra kerekítjük, a megoldás érvénytelen lesz az ILP-re. ${\megjelenítési stílus (1,2)}$ $(2,2)$ $(1.8,2.8)$

Az NP-keménység bizonyítása

A következő érv a csúcsfedő - minimalizálási probléma egészszámú programozási problémává való redukálása, ami bizonyítja az NP-keménységet.

Legyen egy irányítatlan gráf. A lineáris programozási problémát a következőképpen határozzuk meg: $G=(V,E)$

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

Tekintettel arra a követelményre, hogy 0 vagy 1 értéket vegyenek fel, az egész programozás bármely megvalósítható megoldása a csúcsok részhalmaza. Az első megkötés azt jelenti, hogy minden élnek legalább egy vége benne van az alhalmazban. Így a megoldás csúcslefedettséget ad. Továbbá, ha adott egy C csúcsfedő, tetszőlegeshez 1-et, tetszőlegeshez 0-t rendelhetünk , ami érvényes megoldást ad az egész szám programozási problémára. Ebből arra következtethetünk, hogy az összeg minimalizálásakor megkapjuk a minimális csúcsfedőt is [3] . $y_{v}$ $y_{v}$ $v\in C$ $v\not \in C$ $y_{v}$

Opciók

A Mixed Integer Linear Programming (MILP) esetén csak néhány változónak kell egésznek lennie, míg a többi változó lehet nem egész. $x_{i}$

A logikai programozásban a változóknak 0 vagy 1 értéket kell venniük. Vegye figyelembe, hogy bármely korlátos egész változó kifejezhető logikai változók kombinációjaként [4] . Például, ha van egy egész változó , akkor azt logikai változókkal fejezhetjük ki : $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}.

Alkalmazások

Két fő oka van az egész változók használatának lineáris programozási problémák modellezésekor:

Az egész változók olyan mennyiségeket jelölnek, amelyek csak egész számok lehetnek. Például nem lehet 3,7-es autót építeni.
Az egész változók olyan döntéseket jelölnek, amelyek 0 vagy 1 értéket vesznek fel.

Ezek a konvenciók gyakoriak a gyakorlatban, így az egész számú lineáris programozás számos területen használható, amelyek közül néhányat az alábbiakban röviden tárgyalunk.

Gyártástervezés

A vegyes egészszámú programozásnak számos alkalmazása van a gyártásban, beleértve az ütemezési szimulációkat is. Az egyik példa a mezőgazdasági termeléstervezésben fordul elő, hogy meghatározzák az olyan termékek kibocsátását, amelyek közös erőforrásokkal rendelkeznek (például föld, munkaerő, költségek, vetőmagok, műtrágyák stb.). Egy lehetséges optimalizálási cél lehet a bevétel maximalizálása anélkül, hogy túllépnénk a rendelkezésre álló erőforrások korlátait. Egyes esetekben a probléma kifejezhető lineáris programozási feladatként, de a változóknak egész számoknak kell lenniük.

Tervezés

Ezekben a feladatokban biztosítani kell a közlekedési hálózat karbantartását, ütemezését. A feladat lehet például buszok vagy vonatok útvonalak rendezése a menetrend betartása érdekében, valamint a járművezetők biztosítása. Itt logikai változók (azaz a 0 vagy az 1 érték felvétele) határozzák meg, hogy egy busz vagy vonat hozzá van-e rendelve egy útvonalhoz, és hogy egy vezető hozzá van-e rendelve egy adott buszhoz/vonathoz.

Adathálózatok

Ennek a feladatnak az a célja, hogy olyan adathálózatot építsünk ki, amely a minimális költségre előre meghatározott követelményeket biztosít [5] . Ez a feladat mind a hálózati topológia, mind a hálózati elemek sávszélességének optimalizálását igényli. Sok esetben az áteresztőképességet diszkrét mennyiségben fejezik ki, ami egész változókat eredményez. Általában más technológia-specifikus megszorítások érvényesek, amelyek egész vagy logikai változókként modellezhetők.

Mobilhálózatok

A GSM mobilhálózatokban a frekvenciatervezés feladata a megengedhető frekvenciák antennák közötti elosztását teszi szükségessé a kommunikáció biztosítása és az antennák közötti interferencia minimalizálása érdekében [6] . Ez a probléma lineáris programozási problémaként fogalmazható meg, amelyben a logikai változók azt tükrözik, hogy egy adott frekvencia hozzá van-e rendelve egy adott antennához.

Algoritmusok

Az ILP-probléma megoldásának naiv módja az, hogy egyszerűen figyelmen kívül hagyjuk az x változókra vonatkozó egész számok megkötését, megoldjuk a megfelelő LP-problémát (amit az ILP-probléma kényszereinek lineáris relaxációjának nevezünk ), majd kerekítjük a kapott probléma megoldási összetevőit. Az így létrejövő megoldás azonban nemcsak hogy nem optimális, de akár elfogadhatatlan is lehet, vagyis bizonyos korlátozások megsértésére is sor kerülhet.

A teljes unimodularitás használata

Bár általános esetben a gyengített probléma megoldásának integritása nem garantált, ha az ILP a feltételek mellett a , ahol és egész számokat tartalmaz, és teljesen unimoduláris , akkor bármely alapvető megvalósítható megoldás egész szám lesz. Ezért a szimplex módszerrel adott megoldás minden bizonnyal egész szám lesz [7] . Annak kimutatására, hogy egy ilyen probléma bármely alapvető megoldása egész szám, legyen tetszőleges elfogadható megoldás. Mivel ez elfogadható, tudjuk, hogy . Legyenek az alapmegoldás alaposzlopainak megfelelő elemek . A bázis definíciója szerint van egy olyan mátrix négyzetes részmátrixa, amelynek lineárisan független oszlopai vannak úgy, hogy . $\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}$

Mivel az oszlopok lineárisan függetlenek, és a mátrix négyzet alakú, a mátrix nem szinguláris, ezért az unimoduláris feltevés szerint . Mivel nem szinguláris, a mátrix invertálható, ezért . Értelemszerűen . Itt a for unió mátrixát jelenti , és egész szám, mert egész szám. Ily módon $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))

egész szám

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

egész szám

\Jobb nyíl

Minden alapvető elfogadható megoldás egész szám.

Így, ha az ILP mátrix teljesen unimoduláris, akkor az ILP probléma megoldása helyett a probléma lineáris relaxációját használhatjuk, amely egész megoldást ad. $A$

Pontos algoritmusok

Ha a mátrix nem teljesen unimoduláris, számos algoritmus létezik, amelyek pontosan megoldják az egész lineáris programozási problémát. Az ilyen algoritmusok egyik osztálya a vágósík -módszerek (Gomori-módszerek), amelyek egy gyengített lineáris probléma megoldásán dolgoznak olyan lineáris kényszerek hozzáadásával, amelyek levágják a probléma nem egész számú megoldását anélkül, hogy levágnák az egész megvalósítható megoldásokat. $A$

Az algoritmusok másik osztálya az elágazó és kötött módszer változatai . Például az elágazás és vágás módszer , amely az elágazás és kötés módszert kombinálja a vágási sík módszerekkel. Az elágazó és kötött módszerek számos előnnyel rendelkeznek a csak vágósíkokat használó algoritmusokkal szemben. Ennek egyik előnye, hogy az algoritmus korán leállítható, amint legalább egy érvényes egész megoldást találunk, bár nem optimális. Ezenkívül egy laza lineáris probléma megoldásával megbecsülhető, hogy milyen messze van az optimálistól. Végül az elágazó és kötött módszerek segítségével többféle optimális megoldást kaphatunk.

Lenstra 1983-ban kimutatta [8] , hogy fix számú változó esetén polinomiális időben is lehetséges megoldást találni egy egészszámú programozási feladatra.

Heurisztikus módszerek

Mivel az egész lineáris programozási feladatok NP-nehézek , sok problémát nehéz megoldani, ezért heurisztikus módszereket alkalmaznak. Például egy tabu keresés [9] használható . A tabukeresés használatához az ILP-probléma megoldására, az algoritmus lépései úgy definiálhatók, hogy egy egész szám változót növelünk vagy csökkentünk, miközben a többi egész változót változatlanul hagyjuk. Ezután megoldást találunk azokra a változókra, amelyekre nincs kényszerítve egész szám. A rövid távú memória a korábbi próbálkozások tárolására használható, míg a hosszabb távú memória egész változók értékéből állhat, amelyekre nagyobb célfüggvény értékeket kapunk (maximalizálási problémát feltételezve). Végül a hosszú távú memória felhasználható olyan egész értékek megkeresésére, amelyeket még nem teszteltek.

Egyéb heurisztika, amely alkalmazható az ILP megoldására

Vannak más feladatspecifikus heurisztika is, például a k-opt heurisztika az utazó eladó problémájára. Megjegyezzük, hogy a heurisztikus módszerek hátránya, hogy a megoldás sikertelensége esetén a módszer nem határozza meg, hogy ez érvényes megoldás hiánya miatt történt-e, vagy azért, mert az algoritmus nem tudta megtalálni. Továbbá általában lehetetlen meghatározni, hogy milyen közel áll az ezzel a módszerrel elért optimális megoldáshoz.

Jegyzetek

↑ Karmanov, 1986 , p. 11-12.
↑ Papadimitriou, Steiglitz, 1998 .
↑ Erickson .
↑ Williams, HP Logic és integer programozás (határozatlan) . - 2009. - V. 130. - (International Series in Operations Research & Management Science). - ISBN 978-0-387-92280-5 .
↑ Borndörfer, R.; Grötschel, M. Telekommunikációs hálózatok tervezése egészszámú programozással (2012). (határozatlan)
↑ Sharma, Deepak Frequency Planning (2010). (határozatlan)
↑ Tehát például a szállítási probléma felfogható lineáris programozási feladatnak, és a potenciálok megoldására szolgáló módszer valójában szimplex módszer. A szimplex módszer alapmegoldása a potenciálmódszerben lévő fának felel meg, és a megfelelő mátrix mindig 1-es determinánssal rendelkezik. Így egész számú kiindulási adatokkal a transzport probléma megoldása szimplex módszerrel (vagy potenciálmódszerrel, ami ekvivalens) mindig egész számú megoldást kap.
↑ Lenstra, 1983 .
↑ Glover, 1989 , p. 4–32.

Irodalom

CH Papadimitriou, K. Steiglitz. Kombinatorikus optimalizálás: algoritmusok és komplexitás. - Mineola, NY: Dover, 1998. - ISBN 0486402584 .
Erickson, J. Integer Programming Reduction (2015). Archiválva az eredetiből 2015. május 18-án. (határozatlan)
HP Williams. Logikai és egészszámú programozás. - 2009. - V. 130. - (International Series in Operations Research & Management Science). - ISBN 978-0-387-92280-5 .
HW Lenstra. Egészszámú programozás fix számú változóval // Műveletek kutatásának matematikája. - 1983. - november ( 8. köt. 8. szám ) .
F. Glover. Tabu keresés-II. rész // ORSA Journal on computing. - 1989. - 1. évf. , szám. 3 . - S. 4-32 . - doi : 10.1287/ijoc.2.1.4 .

Olvasás további olvasáshoz

Karmanov VG Matematikai programozás. — M .: Nauka , 1986. — 288 p.
Balinski ML egészszámú programozás: módszerek, felhasználások, számítások // Vezetéstudomány. - 1965. - 1. évf. 12, 3. sz. - P. 253-313. - doi : 10.1287/mnsc.12.3.253 .
George L. Nemhauser, Laurence A. Wolsey. Egész és kombinatorikus optimalizálás. - Wiley, 1988. - ISBN 978-0-471-82819-8 .
Alexander Schrijver. Lineáris és egész programozás elmélete. - John Wiley and Sons, 1998. - ISBN 978-0-471-98232-6 .
Laurence A. Wolsey. Integer programozás. - Wiley, 1998. - ISBN 978-0-471-28366-9 .
Dimitris Bertsimas, Robert Weismantel. Optimalizálás egész számok felett. - Dinamikus ötletek, 2005. - ISBN 978-0-9759146-2-5 .
John K. Karlof. Egészszámú programozás: elmélet és gyakorlat. - CRC Press, 2006. - ISBN 978-0-8493-1914-3 .
H. Paul Williams. Logikai és egészszámú programozás. - Springer, 2009. - ISBN 978-0-387-92279-9 .
Az egész szám programozás 50 éve 1958-2008: A korai évektől a legkorszerűbbekig / 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. Alkalmazott egészszámú programozás: modellezés és megoldás. - John Wiley and Sons, 2010. - ISBN 978-0-470-37306-4 .

Linkek

Optimalizálási módszerek
Egydimenziós	aranymetszet módszer Kettősség Parabola módszer Rács keresés Egységes blokkkeresési módszer Fibonacci módszer Háromszoros keresés Piyavsky módszer Strongin módszer
Nulla sorrend	Gauss módszer Nelder-Mead módszer Hook-Jeeves módszer Rosenbrock módszer Powell-módszer
Első rendelés	gradiens süllyedés Zeutendijk módszer Koordináta süllyedés Konjugált gradiens módszer Kvázi-Newtoni módszerek Levenberg-Marquardt algoritmus
másodrendű	Newton módszere Newton-Raphson módszer Broyden-Fletcher-Goldfarb-Shanno algoritmus (BFGS)
Sztochasztikus	Monte Carlo módszer Szimulált lágyítás Evolúciós algoritmusok differenciális evolúció Hangya algoritmus Részecskeraj módszer Méhtelep algoritmus Véletlenszerű séta módszer
Lineáris programozási módszerek	Simplex módszer Gomori algoritmusa Ellipszoid módszer Potenciális módszer
Nemlineáris programozási módszerek	Szekvenciális kvadratikus programozás