Heltalsprogrammering

Ett heltalsprogrammeringsproblem är ett matematiskt optimerings- eller tillfredsställelseproblem där några eller alla variablerna måste vara heltal [1] . Ofta hänvisar termen till heltalslinjär programmering (ILP), där objektivfunktionen och begränsningarna (förutom heltalskravet) är linjära .

Heltalsprogrammering är ett NP-hårt problem . Ett specialfall, 0-1 heltals linjär programmering, där variabler tar värdena 0 eller 1, är ett av Karps 21 NP-kompletta problem .

Kanoniska och standardtyper av CLP

Problemet med heltalslinjär programmering i kanonisk form uttrycks som [2]

maximera	$\mathbf {c} ^{\mathrm {T} }\mathbf {x}$
under förhållanden	$A\mathbf {x} \leq \mathbf {b}$
	$\mathbf {x} \geq \mathbf {0}$
och	${\displaystyle \mathbf {x} \in \mathbb {Z} ^{n))$ ,

och i standardform

maximera	$\mathbf {c} ^{\mathrm {T} }\mathbf {x}$
under förhållanden	$A\mathbf {x} +\mathbf {s} =\mathbf {b}$
	$\mathbf {s} \geq \mathbf {0}$
och	${\displaystyle \mathbf {x} \in \mathbb {Z} ^{n))$

där är vektorer och är en matris, vars alla element är heltal. Observera att, som i fallet med linjär programmering, kan ett ILP-problem som inte är i standardform reduceras till standardform genom att eliminera ojämlikheter genom att införa ytterligare och artificiella variabler och ersätta variabler som inte är föremål för icke-negativitetsbegränsningen med två variabler. $\mathbf {c} ,\mathbf {b}$ $A$

Exempel

Bilden till höger visar följande uppgift.

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

De giltiga heltalspunkterna visas i rött och de röda streckade linjerna visar det konvexa skrovet för dessa punkter, vilket är den minsta polygonen som innehåller alla dessa punkter. De blå linjerna, tillsammans med koordinataxlarna, definierar den linjära dämpningspolygonen, som ges av olikheter utan heltalskrav. Optimeringsmålet är att flytta den svarta streckade linjen så att den är så hög som möjligt, men rör vid polygonen. De optimala lösningarna på heltalsproblemet är punkterna och , där objektivfunktionen tar värdet 2. Den enda lösningen på det försvagade (linjära) problemet är punkten , där objektivfunktionen tar värdet 2,8. Observera att om vi avrundar lösningen av ett linjärt programmeringsproblem till närmaste heltal, kommer lösningen att vara ogiltig för ILP. $(1,2)$ $(2,2)$ $(1.8,2.8)$

Bevis på NP-hårdhet

Följande argument är en reduktion av problemet med minimering av vertextäckning till ett heltalsprogrammeringsproblem, vilket bevisar NP-hårdhet.

Låt vara en oriktad graf. Vi definierar ett linjärt programmeringsproblem enligt följande: $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}}

Med tanke på kravet att de tar värdena 0 eller 1, är varje möjlig lösning för heltalsprogrammering en delmängd av hörn. Den första begränsningen innebär att minst en ände av varje kant ingår i delmängden. Således ger lösningen en vertextäckning. Dessutom, givet ett vertextäcke C, kan vi tilldela värdet 1 för någon och 0 för någon , vilket ger oss en giltig lösning på heltalsprogrammeringsproblemet. Av detta kan vi dra slutsatsen att när vi minimerar summan får vi också det minsta vertextäcket [3] . ${\displaystyle y_{v))$ ${\displaystyle y_{v))$ $v\in C$ $v\not \in C$ ${\displaystyle y_{v))$

Alternativ

I Mixed Integer Linear Programming (MILP) behöver bara några av variablerna vara heltal, medan resten av variablerna kan vara icke-heltal. $x_{i}$

I boolesk programmering måste variabler anta värdena 0 eller 1. Observera att alla gränsade heltalsvariabler kan uttryckas som en kombination av booleska variabler [4] . Till exempel, om det finns en heltalsvariabel kan den uttryckas i termer av booleska variabler: $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}.

Applikationer

Det finns två huvudskäl till att använda heltalsvariabler vid modellering av linjära programmeringsproblem:

Heltalsvariabler representerar kvantiteter som bara kan vara heltal. Det går till exempel inte att bygga 3,7 bilar.
Heltalsvariabler representerar beslut som tar värdena 0 eller 1.

Dessa konventioner är vanliga i praktiken, och därför kan heltalslinjär programmering användas inom många områden, av vilka några diskuteras kort nedan.

Produktionsplanering

Blandad heltalsprogrammering har många tillämpningar inom tillverkning, inklusive schemaläggningssimuleringar. Ett exempel förekommer i produktionsplanering inom jordbruket för att bestämma produktionen av produkter som kan ha gemensamma resurser (som mark, arbetskraft, kostnader, utsäde, gödningsmedel, etc.). Ett möjligt optimeringsmål kan vara att maximera intäkterna utan att gå över gränserna för tillgängliga resurser. I vissa fall kan problemet uttryckas som ett linjärt programmeringsproblem, men variablerna måste vara heltal.

Planering

I dessa uppgifter är det nödvändigt att säkerställa underhållet och tidsplanen för transportnätet. Uppdraget kan till exempel vara att ordna bussar eller tåg längs sträckor för att följa tidtabellen, samt tillhandahålla förare till den rullande materielen. Här avgör booleska variabler (dvs med värdet 0 eller 1) om en buss eller tåg är tilldelad en rutt, och om en förare tilldelas en viss buss/tåg.

Datanätverk

Syftet med denna uppgift är att bygga ett datanätverk för att tillhandahålla fördefinierade krav på minimikostnaden [5] . Denna uppgift kräver optimering av både nätverkstopologin och bandbredden för nätverkselementen. I många fall uttrycks genomströmningen i diskreta kvantiteter, vilket resulterar i heltalsvariabler. Vanligtvis gäller andra teknikspecifika begränsningar, som kan modelleras som heltalsvariabler eller booleska variabler.

Mobilnätverk

Uppgiften med frekvensplanering i GSM -mobilnät kräver fördelning av tillåtna frekvenser mellan antenner för att säkerställa kommunikation och minimera interferens mellan antenner [6] . Detta problem kan formuleras som ett linjärt programmeringsproblem där booleska variabler reflekterar om en viss frekvens är tilldelad en viss antenn.

Algoritmer

Det naiva sättet att lösa ILP-problemet är att helt enkelt ignorera heltalsbegränsningen på variablerna x , lösa motsvarande LP-problem (vilket kallas linjär relaxation av ILP-problemrestriktionerna) och sedan avrunda lösningskomponenterna i det resulterande problemet. Den resulterande lösningen kanske inte bara är icke-optimal, den kan till och med vara oacceptabel, det vill säga vissa begränsningar kan överträdas.

Använder full unimodularitet

Även om, i det allmänna fallet, integriteten för lösningen av det försvagade problemet inte garanteras, om ILP har formen under villkoren , där och har heltal som element och är helt unimodulär , så kommer varje grundläggande genomförbar lösning att vara heltal. Därför kommer lösningen som ges av simplexmetoden säkerligen att vara heltal [7] . För att visa att varje grundläggande lösning av ett sådant problem är heltal, låt vara en godtycklig tillåten lösning. Eftersom det är tillåtet vet vi att . Låt vara de element som motsvarar de grundläggande kolumnerna i den grundläggande lösningen . Enligt definitionen av en bas finns det någon kvadratisk submatris av en matris med linjärt oberoende kolumner så att . $\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}$

Eftersom kolumnerna är linjärt oberoende och matrisen är kvadratisk, är matrisen icke-singular, och därför, under antagandet att den är unimodulär , . Eftersom den inte är singular är matrisen inverterbar och därför . Per definition ,. Här betyder unionsmatrisen för och den är heltal eftersom den är heltal. På det här sättet, $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))

heltal

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

heltal

\Höger pil

Alla grundläggande tillåtna lösningar är heltal.

Således, om ILP-matrisen är helt unimodulär, istället för att lösa ILP-problemet, kan man använda en linjär avslappning av problemet, vilket ger en heltalslösning. $A$

Exakta algoritmer

Om matrisen inte är helt unimodulär finns det ett antal algoritmer som löser heltalslinjärprogrammeringsproblemet exakt. En av klasserna av sådana algoritmer är skärplansmetoder (Gomori-metoder), som fungerar genom att lösa ett försvagat linjärt problem med efterföljande tillägg av linjära begränsningar som skär av den icke-heltalslösningen av problemet utan att skära av de heltalslösningar som är möjliga. $A$

En annan klass av algoritmer är varianter av branch and bound- metoden . Till exempel gren-och-klipp-metoden , som kombinerar gren-och-bund-metoden med skärplansmetoder. Förgrenings- och bundna metoder har ett antal fördelar jämfört med algoritmer som endast använder klippplan. En av fördelarna är att algoritmen kan avslutas tidigt, så snart minst en giltig heltalslösning hittats, dock inte optimal. Dessutom kan lösa ett avslappnat linjärt problem användas för att uppskatta hur långt borta från det optimala. Slutligen kan gren- och bundna metoder användas för att få flera optimala lösningar.

Lenstra 1983 visade [8] att i fallet med ett fast antal variabler kan en genomförbar lösning på ett heltalsprogrammeringsproblem hittas i polynomtid.

Heuristiska metoder

Eftersom heltalslinjära programmeringsproblem är NP-hårda är många problem svåra att lösa, så heuristiska metoder tillämpas. Till exempel kan en tabusökning [9] användas . För att använda tabusökning för att lösa ILP-problemet kan ett algoritmsteg definieras som att öka eller minska en heltalsvariabel samtidigt som de andra heltalsvariablerna lämnas oförändrade. Sedan hittas en lösning för variabler som heltalsbegränsningen inte är pålagd. Korttidsminnet kan användas för att lagra tidigare försök, medan långtidsminnet kan bestå av värden av heltalsvariabler för vilka större objektiva funktionsvärden erhålls (förutsatt ett maximeringsproblem). Slutligen kan långtidsminne användas för att slå upp heltalsvärden som ännu inte har testats.

Andra heuristik som kan användas för att lösa ILP

Det finns också några andra uppgiftsspecifika heuristiker, som k-opt-heuristiken för resandeförsäljarproblemet. Observera att nackdelen med heuristiska metoder är att om det inte går att hitta en lösning avgör metoden inte om detta hände på grund av avsaknaden av en giltig lösning, eller för att algoritmen inte kunde hitta den. Vidare är det vanligtvis omöjligt att avgöra hur nära den optimala lösningen som erhålls med denna metod.

Anteckningar

↑ Karmanov, 1986 , sid. 11-12.
↑ Papadimitriou, Steiglitz, 1998 .
↑ Erickson .
↑ Williams, HP Logik och heltalsprogrammering (obestämd) . - 2009. - V. 130. - (International Series in Operations Research & Management Science). - ISBN 978-0-387-92280-5 .
↑ Borndörfer, R.; Grötschel, M. Designa telekommunikationsnätverk genom heltalsprogrammering (2012). (obestämd)
↑ Sharma, Deepak Frequency Planning (2010). (obestämd)
↑ Så till exempel kan transportproblemet betraktas som ett linjärt programmeringsproblem och metoden för potentialer för att lösa detta problem är i själva verket en simplexmetod. Simplexmetodens grundläggande lösning motsvarar trädet i potentialmetoden, och motsvarande matris har alltid en determinant på 1. Således, med heltals initiala data, lösningen av transportproblemet med simplexmetoden (eller potentialmetoden, vilket är likvärdigt) kommer alltid att få en heltalslösning.
↑ Lenstra, 1983 .
↑ Glover, 1989 , sid. 4–32.

Litteratur

CH Papadimitriou, K. Steiglitz. Kombinatorisk optimering: algoritmer och komplexitet. - Mineola, NY: Dover, 1998. - ISBN 0486402584 .
Erickson, J. Heltalsprogrammeringsminskning (2015). Arkiverad från originalet den 18 maj 2015. (obestämd)
HP Williams. Logik och heltalsprogrammering. - 2009. - V. 130. - (International Series in Operations Research & Management Science). - ISBN 978-0-387-92280-5 .
HW Lenstra. Heltalsprogrammering med ett fast antal variabler // Operationsforsknings matematik. - 1983. - November ( vol. 8 , nummer 8 ).
F. Glover. Tabu-sökning-Del II // ORSA Journal on computing. - 1989. - Vol. 1 , nummer. 3 . - S. 4-32 . - doi : 10.1287/ijoc.2.1.4 .

Läsning för vidare läsning

Karmanov VG Matematisk programmering. — M .: Nauka , 1986. — 288 sid.
Balinski ML Heltalsprogrammering: Metoder, användningar, beräkningar // Management Science. - 1965. - Vol. 12, nr 3. - S. 253-313. - doi : 10.1287/mnsc.12.3.253 .
George L. Nemhauser, Laurence A. Wolsey. Heltals- och kombinatorisk optimering. - Wiley, 1988. - ISBN 978-0-471-82819-8 .
Alexander Schrijver. Teori för linjär- och heltalsprogrammering. - John Wiley and Sons, 1998. - ISBN 978-0-471-98232-6 .
Laurence A. Wolsey. Heltalsprogrammering. - Wiley, 1998. - ISBN 978-0-471-28366-9 .
Dimitris Bertsimas, Robert Weismantel. Optimering över heltal. - Dynamiska idéer, 2005. - ISBN 978-0-9759146-2-5 .
John K. Karlof. Heltalsprogrammering: teori och praktik. - CRC Press, 2006. - ISBN 978-0-8493-1914-3 .
H. Paul Williams. Logik och heltalsprogrammering. - Springer, 2009. - ISBN 978-0-387-92279-9 .
50 år av heltalsprogrammering 1958-2008: Från de tidiga åren till det senaste / 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. Tillämpad heltalsprogrammering: modellering och lösning. - John Wiley and Sons, 2010. - ISBN 978-0-470-37306-4 .

Länkar

Optimeringsmetoder _
En-dimensionell	gyllene snittmetoden Dikotomi Parabolmetoden Rutnätssökning Enhetlig blocksökningsmetod Fibonacci-metoden Ternär sökning Piyavsky-metoden Strongin metod
Noll ordning	Gauss metod Nelder-Mead metod Hook-Jeeves metod Rosenbrock-metoden Powell metod
Första beställning	lutning nedstigning Zeutendijk-metoden Koordinera nedstigning Konjugerad gradientmetod Kvasi-newtonska metoder Levenberg-Marquardts algoritm
andra beställning	Newtons metod Newton-Raphson-metoden Broyden-Fletcher-Goldfarb-Shanno-algoritm (BFGS)
Stokastisk	Monte Carlo metoden Simulerad glödgning Evolutionära algoritmer differentiell evolution Myralgoritm Partikelsvärmmetod Algoritm för bikoloni Random walk-metod
Linjära programmeringsmetoder _	Enkel metod Gomoris algoritm Ellipsoid metod Potentiell metod
Icke -linjära programmeringsmetoder	Sekventiell kvadratisk programmering