Heltalsprogrammering - Integer programming

Et heltalsprogrammeringsproblem er et matematisk optimerings- eller gennemførlighedsprogram , hvor nogle eller alle variabler er begrænset til at være heltal . I mange indstillinger henviser udtrykket til heltal lineær programmering (ILP), hvor den objektive funktion og begrænsningerne (bortset fra heltalets begrænsninger) er lineære .

Heltalsprogrammering er NP-komplet . Især det specielle tilfælde med 0-1 heltal lineær programmering, hvor ukendte er binære, og kun begrænsningerne skal være opfyldt, er et af Karps 21 NP-komplette problemer .

Hvis nogle beslutningsvariabler ikke er diskrete, kaldes problemet et blandet-heltal programmeringsproblem .

Kanonisk og standardformular til ILP'er

I heltal lineær programmering adskiller kanonisk form sig fra standardform . Et heltal lineært program i kanonisk form udtrykkes således (bemærk at det er vektoren der skal afgøres): ${\ displaystyle \ mathbf {x}}$

${\ displaystyle {\ begin {align} & {\ 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 {justeret}}}$

og en ILP i standardform udtrykkes som

${\ displaystyle {\ begin {align} & {\ text {maximize}} && \ mathbf {c} ^ {\ mathrm {T}} \ mathbf {x} \\ & {\ text {subject to}} && A \ mathbf {x} + \ mathbf {s} = \ mathbf {b}, \\ &&& \ mathbf {s} \ geq \ mathbf {0}, \\ &&& \ mathbf {x} \ geq \ mathbf {0}, \\ & {\ tekst {og}} && \ mathbf {x} \ i \ mathbb {Z} ^ {n}, \ end {justeret}}}$

hvor er vektorer og er en matrix, hvor alle poster er heltal. Som med lineære programmer kan ILP'er, der ikke er i standardform, konverteres til standardform ved at eliminere uligheder, indføre slapvariabler ( ) og erstatte variabler, der ikke er tegnbegrænset, med forskellen på to tegnbegrænsede variabler ${\ displaystyle \ mathbf {c}, \ mathbf {b}}$${\ displaystyle A}$${\ displaystyle \ mathbf {s}}$

Eksempel

Plottet til højre viser følgende problem.

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

De mulige heltalspunkter vises i rødt, og de røde stiplede linjer angiver deres konvekse skrog, som er den mindste konvekse polyhedron, der indeholder alle disse punkter. De blå linjer sammen med koordinatakserne definerer polyhedronet i LP-afslapningen, hvilket er givet af ulighederne uden integritetsbegrænsning. Målet med optimeringen er at flytte den sorte stiplede linje så langt opad, mens du stadig berører polyhedronen. De optimale løsninger på heltalsproblemet er de punkter, og som begge har en objektiv værdi på 2. Det unikke optimale ved afslapning er med en objektiv værdi på 2,8. Hvis løsningen af ​​afslapningen afrundes til de nærmeste heltal, er det ikke muligt for ILP. ${\ displaystyle (1,2)}$${\ displaystyle (2,2)}$${\ displaystyle (1.8,2.8)}$

Bevis for NP-hårdhed

Følgende er en reduktion fra minimum toppunktdækning til heltalsprogrammering, der vil tjene som bevis for NP-hårdhed.

Lad være en ustyret graf. Definer et lineært program som følger: ${\ displaystyle G = (V, E)}$

${\ displaystyle {\ begin {justeret} \ min \ sum _ {v \ i V} y_ {v} \\ y_ {v} + y_ {u} & \ geq 1 && \ forall uv \ i E \\ y_ {v } & \ geq 0 && \ forall v \ i V \\ y_ {v} & \ i \ mathbb {Z} && \ forall v \ i V \ end {justeret}}}$

Da begrænsningerne begrænser sig til enten 0 eller 1, er enhver mulig løsning på heltalsprogrammet en delmængde af hjørner. Den første begrænsning indebærer, at mindst et slutpunkt for hver kant er inkluderet i denne delmængde. Derfor beskriver løsningen et toppunktdæksel. Derudover givet nogle topdæksel C, kan indstilles til 1 for enhver og til 0 for enhver, hvilket giver os en mulig løsning på heltalsprogrammet. Således kan vi konkludere, at hvis vi minimerer summen af, har vi også fundet det minimale toppunktdæksel. ${\ displaystyle y_ {v}}$${\ displaystyle y_ {v}}$${\ displaystyle v \ i C}$${\ displaystyle v \ not \ in C}$${\ displaystyle y_ {v}}$

Varianter

Mixet-heltal lineær programmering ( MILP ) involverer problemer, hvor kun nogle af variablerne er begrænset til at være heltal, mens andre variabler får lov til at være ikke-heltal. ${\ displaystyle x_ {i}}$

Nul-en lineær programmering (eller binært heltalsprogrammering ) involverer problemer, hvor variablerne er begrænset til enten at være 0 eller 1. Enhver afgrænset heltalvariabel kan udtrykkes som en kombination af binære variabler. For eksempel, givet en heltalsvariabel , kan variablen udtrykkes ved hjælp af binære variabler: ${\ displaystyle 0 \ leq x \ leq U}$${\ displaystyle \ lfloor \ log _ {2} U \ rfloor +1}$

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

Ansøgninger

Der er to hovedårsager til at bruge heltalsvariabler, når man modellerer problemer som et lineært program:

1. Heltalsvariablerne repræsenterer størrelser, der kun kan være heltal. For eksempel er det ikke muligt at bygge 3,7 biler.
2. Heltalsvariablerne repræsenterer beslutninger (f.eks. Om de skal inkludere en kant i en graf ) og bør derfor kun tage værdien 0 eller 1.

Disse overvejelser forekommer ofte i praksis, og derfor kan heltal lineær programmering bruges i mange anvendelsesområder, hvoraf nogle kort beskrives nedenfor.

Produktions planlægning

Programmering med blandet heltal har mange anvendelser i industrielle produktioner, herunder modellering af job-shop. Et vigtigt eksempel sker i planlægningen af landbrugsproduktionen, hvor man bestemmer produktionsudbyttet for flere afgrøder, der kan dele ressourcer (f.eks. Jord, arbejdskraft, kapital, frø, gødning osv.) Et muligt mål er at maksimere den samlede produktion uden at overskride de tilgængelige ressourcer. I nogle tilfælde kan dette udtrykkes som et lineært program, men variablerne skal begrænses til at være heltal.

Planlægning

Disse problemer involverer service og køretidsplanlægning i transportnetværk. For eksempel kan et problem indebære at tildele busser eller undergrundsbaner til individuelle ruter, så en køreplan kan overholdes, og også at udstyre dem med chauffører. Her angiver binære beslutningsvariabler, om en bus eller metro er tildelt en rute, og om en driver er tildelt et bestemt tog eller metro. Nul-én programmeringsteknikken er med succes anvendt til at løse et projektudvælgelsesproblem, hvor projekter er gensidigt eksklusive og / eller teknologisk indbyrdes afhængige. Det bruges i et specielt tilfælde af heltalsprogrammering, hvor alle beslutningsvariabler er heltal. Det kan antage værdierne enten som nul eller en.

Territorial opdeling

Territorial opdeling eller distriktsproblemer består i at opdele en geografisk region i distrikter for at planlægge nogle operationer under overvejelse af forskellige kriterier eller begrænsninger. Nogle krav til dette problem er: sammenhæng, kompakthed, balance eller ligevægt, respekt for naturlige grænser og socioøkonomisk homogenitet. Nogle applikationer til denne type problemer inkluderer: politisk distrikt, skoledistrikt, sundhedsvæsen og distriktsaffaldshåndtering.

Telekommunikationsnetværk

Målet med disse problemer er at designe et netværk af linjer, der skal installeres, så et foruddefineret sæt kommunikationskrav er opfyldt, og de samlede omkostninger ved netværket er minimale. Dette kræver optimering af både topologien i netværket sammen med indstilling af kapaciteten for de forskellige linjer. I mange tilfælde er kapaciteterne begrænset til at være heltalsmængder. Normalt er der, afhængigt af den anvendte teknologi, yderligere begrænsninger, der kan modelleres som lineære uligheder med heltal eller binære variabler.

Mobilnetværk

Opgaven med frekvensplanlægning i GSM- mobilnetværk involverer distribution af tilgængelige frekvenser på tværs af antennerne, så brugerne kan betjenes, og interferens minimeres mellem antennerne. Dette problem kan formuleres som et heltal lineært program, hvor binære variabler angiver, om en frekvens er tildelt en antenne.

Andre applikationer

• Matchning af pengestrømme
• Optimering af energisystemet
• UAV vejledning

Algoritmer

Den naive måde at løse en ILP på er simpelthen at fjerne begrænsningen om, at x er heltal, løse den tilsvarende LP (kaldet LP-afslapning af ILP) og derefter afrunde indgange af løsningen til LP-afslapning. Men ikke kun kan denne løsning ikke være optimal, den er måske ikke engang mulig; det vil sige, at det overtræder en vis begrænsning.

Brug af total unimodularitet

Mens løsningen til LP-afslapning generelt ikke garanteres at være integreret, er ILP i form sådan, at hvor og har alle heltalsposter og er totalt uimodulær , så er enhver grundlæggende mulig løsning integreret. Derfor er den løsning, der returneres af simplex-algoritmen , garanteret at være integreret. Lad være en vilkårlig grundlæggende mulig løsning for at vise, at enhver grundlæggende mulig løsning er integreret . Da det er muligt, ved vi det . Lad være de elementer, der svarer til grundkolonnerne for den grundlæggende løsning . Per definition af et grundlag, der er en vis firkantet delmatrix af med lineært uafhængige søjler, således at . ${\ displaystyle \ max \ mathbf {c} ^ {\ mathrm {T}} \ mathbf {x}}$${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$${\ displaystyle A}$${\ displaystyle \ mathbf {b}}$${\ displaystyle A}$${\ displaystyle \ mathbf {x}}$${\ displaystyle \ mathbf {x}}$${\ displaystyle A \ mathbf {x} = \ mathbf {b}}$${\ displaystyle \ mathbf {x} _ {0} = [x_ {n_ {1}}, x_ {n_ {2}}, \ cdots, x_ {n_ {j}}]}$${\ displaystyle \ mathbf {x}}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B \ mathbf {x} _ {0} = \ mathbf {b}}$

Eftersom søjlerne af er lineært uafhængige og er kvadratisk, er non-singul, og derfor af antagelse, er unimodul og så . Da det ikke er ensformigt, er det også vendbart og derfor . Per definition . Her betegner adjugatet af og er integreret, fordi det er integreret. Derfor, ${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle \ det (B) = \ pm 1}$${\ displaystyle B}$${\ displaystyle \ mathbf {x} _ {0} = B ^ {- 1} \ mathbf {b}}$${\ displaystyle B ^ {- 1} = {\ frac {B ^ {adj}} {\ det (B)}} = \ pm B ^ {adj}}$${\ displaystyle B ^ {adj}}$${\ displaystyle B}$${\ displaystyle B}$

${\ displaystyle {\ begin {align} & \ Rightarrow B ^ {- 1} = \ pm B ^ {adj} {\ text {er integreret.}} \\ & \ Rightarrow x_ {0} = B ^ {- 1 } b {\ text {er integreret.}} \\ & \ Rightarrow {\ text {Hver ​​grundlæggende mulige løsning er integreret.}} \ end {justeret}}}$

Således, hvis matrixen til en ILP er totalt unimodulær i stedet for at bruge en ILP-algoritme, kan simplex-metoden bruges til at løse LP-afslapningen, og opløsningen vil være heltal. ${\ displaystyle A}$

Præcise algoritmer

Når matrixen ikke er helt unimodulær, er der en række algoritmer, der kan bruges til at løse heltals lineære programmer nøjagtigt. En klasse af algoritmer er at skære planmetoder, der fungerer ved at løse LP-afslapningen og derefter tilføje lineære begrænsninger, der driver løsningen mod at være heltal uden at ekskludere mulige heltal mulige punkter. ${\ displaystyle A}$

En anden klasse af algoritmer er varianter af forgrenings- og bundmetoden . For eksempel forgrenings- og skæremetoden, der kombinerer både forgrenings- og bund- og skæreplanmetoder. Forgrenede og bundne algoritmer har en række fordele i forhold til algoritmer, der kun bruger skæreplan. En fordel er, at algoritmerne kan afsluttes tidligt, og så længe der er fundet mindst en integreret løsning, kan en mulig, men ikke nødvendigvis optimal løsning, returneres. Løsningerne til LP-afslapninger kan endvidere bruges til at give et værst tænkeligt skøn over, hvor langt fra optimalitet den returnerede løsning er. Endelig kan filial- og bundmetoder bruges til at returnere flere optimale løsninger.

Præcise algoritmer for et lille antal variabler

Antag at er en m -by- n heltalmatrix og er en m -by-1 heltal vektor. Vi fokuserer på gennemførlighedsproblemet, som er at afgøre, om der findes en n -by-1-vektor, der tilfredsstiller . ${\ displaystyle A}$${\ displaystyle \ mathbf {b}}$${\ displaystyle \ mathbf {x}}$${\ displaystyle A \ mathbf {x} \ leq \ mathbf {b}}$

Lad V være den maksimale absolutte værdi af koefficienterne i og . Hvis n (antallet af variabler) er en fast konstant, så det er muligt problem kan løses i tid polynomium i m og log V . Dette er trivielt for sagen n = 1. Sagen n = 2 blev løst i 1981 af Herbert Scarf . Den generelle sag blev løst i 1983 af Hendrik Lenstra , der kombinerede ideer af Laszlo Lovasz og Peter van Emde Boas . ${\ displaystyle A}$${\ displaystyle \ mathbf {b}}$

I det specielle tilfælde 0-1 ILP svarer Lenstras algoritme til fuldstændig optælling: antallet af alle mulige løsninger er fast (2 ⁿ ), og kontrol af gennemførligheden af ​​hver løsning kan ske i tid poly ( m , log V ) . I det generelle tilfælde, hvor hver variabel kan være et vilkårligt heltal, er fuldstændig optælling umulig. Her bruger Lenstras algoritme ideer fra talgeometri . Det omdanner det oprindelige problem til en ækvivalent med følgende egenskab: enten er eksistensen af ​​en løsning åbenbar, eller værdien af ( n- th-variablen) hører til et interval, hvis længde er afgrænset af en funktion af n . I sidstnævnte tilfælde reduceres problemet til et begrænset antal lavere dimensionelle problemer. ${\ displaystyle \ mathbf {x}}$${\ displaystyle x_ {n}}$

Lenstras algoritme indebærer, at ILP er polynomisk tidsopløselig også i det dobbelte tilfælde, hvor n er varierende, men m (antallet af begrænsninger) er konstant.

Lenstras algoritme blev efterfølgende forbedret af Kannan og Frank og Tardos. Den forbedrede driftstid er , hvor er antallet af inputbits, der er i . ${\ displaystyle n ^ {2.5n} \ cdot \ ell}$${\ displaystyle \ ell}$${\ displaystyle {\ text {poly}} (m, \ log {V})}$

Heuristiske metoder

Da heltal lineær programmering er NP-hård , er mange problemforekomster umulige, og derfor skal heuristiske metoder bruges i stedet. For eksempel kan tabussøgning bruges til at søge efter løsninger på ILP'er. For at bruge tabu-søgning til at løse ILP'er kan bevægelser defineres som at øge eller mindske en heltalsbegrænset variabel i en mulig løsning, mens alle andre heltal-begrænsede variabler holdes konstant. De ubegrænsede variabler løses derefter for. Korttidshukommelse kan bestå af tidligere prøvede løsninger, mens mellemlang hukommelse kan bestå af værdier for de heltalsbegrænsede variabler, der har resulteret i høje objektive værdier (forudsat at ILP er et maksimeringsproblem). Endelig kan langvarig hukommelse styre søgningen mod heltalsværdier, der ikke tidligere er blevet prøvet.

Andre heuristiske metoder, der kan anvendes på ILP'er, inkluderer

• Bjergbestigning
• Simuleret udglødning
• Reaktiv søgningoptimering
• Ant koloni optimering
• Hopfield neurale netværk

Der er også en række andre problemspecifikke heuristikker, som f.eks. K-opt-heuristikken til det rejsende sælgerproblem. En ulempe ved heuristiske metoder er, at hvis de ikke finder en løsning, kan det ikke afgøres, om det er, fordi der ikke er nogen mulig løsning, eller om algoritmen simpelthen ikke kunne finde en. Desuden er det normalt umuligt at kvantificere, hvor tæt på optimal en løsning, der returneres ved disse metoder, er.

Sparse heltalsprogrammering

Det er ofte tilfældet, at matrixen, der definerer heltalsprogrammet, er sparsom . Dette sker især, når matrixen har en blokstruktur, hvilket er tilfældet i mange applikationer. Matrixens sparsitet kan måles som følger. Den graf af har knudepunkter svarer til søjler af , og to kolonner danner en kant, hvis har en række, hvor begge kolonner har nonzero firmaer. Tilsvarende svarer hjørnerne til variabler, og to variabler danner en kant, hvis de deler en ulighed. Den sparsity foranstaltning af er den mindste mellem træ-dybden af grafen for og træ-dybden af grafen for transponerede . Lad være det numeriske mål for defineret som den maksimale absolutte værdi for enhver indtastning af . Lad være antallet af variabler i heltalsprogrammet. Derefter blev det vist i 2018, at heltalsprogrammering kan løses i stærkt polynomisk og fastparameter, der kan spores, parametreret af og . Det vil sige, for en eller anden beregningsfunktion og en konstant , kan heltalsprogrammering løses i tide . Især er tiden uafhængig af højre side og den objektive funktion . I modsætning til det klassiske resultat af Lenstra, hvor antallet af variabler er en parameter, er antallet af variabler her en variabel del af input. ${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle A}$ ${\ displaystyle d}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle a}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle n}$${\ displaystyle a}$${\ displaystyle d}$${\ displaystyle f}$${\ displaystyle k}$${\ displaystyle f (a, d) n ^ {k}}$${\ displaystyle b}$${\ displaystyle c}$${\ displaystyle n}$${\ displaystyle n}$

Se også

• Begrænsede mindste firkanter

Referencer

Yderligere læsning

• George L. Nemhauser ; Laurence A. Wolsey (1988). Heltal og kombinatorisk optimering . Wiley. ISBN 978-0-471-82819-8.
• Alexander Schrijver (1998). Teori om lineær og heltal programmering . John Wiley og sønner. ISBN 978-0-471-98232-6.
• Laurence A. Wolsey (1998). Heltals programmering . Wiley. ISBN 978-0-471-28366-9.
• Dimitris Bertsimas; Robert Weismantel (2005). Optimering over heltal . Dynamiske ideer. ISBN 978-0-9759146-2-5.
• John K. Karlof (2006). Heltalsprogrammering: teori og praksis . CRC Tryk. ISBN 978-0-8493-1914-3.
• H. Paul Williams (2009). Logik og heltal programmering . 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, red. (2009). 50 år med heltalsprogrammering 1958-2008: Fra de tidlige år til det nyeste . Springer. ISBN 978-3-540-68274-5.
• Der-San Chen; Robert G. Batson; Yu Dang (2010). Anvendt heltalsprogrammering: Modellering og løsning . John Wiley og sønner. ISBN 978-0-470-37306-4.
• Gerard Sierksma; Yori Zwols (2015). Lineær og heltal optimering: Teori og praksis . CRC Tryk. ISBN 978-1-498-71016-9.

eksterne links

• En tutorial om heltalsprogrammering
• Konferenceintegreret programmering og kombinatorisk optimering, IPCO
• Aussois Combinatorial Optimization Workshop