Heltalsoptimering

Heltalsoptimering (HO; eng. integer programming, IP) — är en gren inom matematisk optimering där man studerar problem i vilka några eller alla variabler måste anta enbart heltalsvärden.

Det mest välstuderade specialfallet är heltalslinjär programmering (HLP; eng. integer linear programming, ILP), där målfunktionen och bivillkoren är linjära. Till skillnad från linjär programmering, där variablerna kan anta godtyckliga reella värden, gör heltalsvillkoret HO-problem avsevärt svårare att lösa.

Heltalsoptimering har bred tillämpning inom ekonomi, logistik, produktionsplanering och andra områden där variablerna till sin natur är diskreta (exempelvis antal producerade enheter eller antal anställda).

Definition och terminologi

Det allmänna problemet inom heltalslinjär programmering kan formuleras på följande sätt:

Hitta vektorn $x$ som:

maximerar (eller minimerar) $c^{T}x$

med bivillkoren:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{Z}}^n$ (alla komponenter i vektorn $x$ är heltal)

där $x$ är variabelvektorn, $c$ och $b$ är vektorer, och $A$ är en koefficientsmatris.

Beroende på kraven på variablerna skiljer man på följande typer av problem:

• Rent heltals­programmering: alla variabler måste vara heltal.
• Blandad heltalsprogrammering (eng. mixed-integer programming, MIP): endast en del av variablerna måste vara heltal.
• Boolesk (0-1) programmering: variablerna antar enbart värdena 0 eller 1, vilket möjliggör modellering av logiska ja/nej-beslut.

Centrala egenskaper och komplexitet

Beräkningskomplexitet

Problemet med heltalslinjär programmering är i det allmänna fallet NP-svårt. Det innebär att det inte finns något känt algoritm som kan hitta en exakt optimal lösning för ett godtyckligt HO-problem på polynomiell tid. Komplexiteten beror på problemets kombinatoriska natur, eftersom antalet möjliga heltalslösningar kan växa exponentiellt med antalet variabler.

Samband med linjär programmering (LP-relaxation)

För varje HO-problem kan man formulera dess linjära relaxation — ett linjärprogrammeringsproblem (LP) där heltalsvillkoret för variablerna tas bort. Lösningen av LP-relaxationen har två viktiga egenskaper:

1. Den kan hittas avsevärt snabbare (på polynomiell tid).
2. Det optimala värdet av målfunktionen för LP-relaxationen ger en uppskattning (övre gräns vid maximering och undre gräns vid minimering) för det optimala värdet av det ursprungliga heltalsproblemet.

Dock leder enkel avrundning av den bråktalslösning som LP-relaxationen ger till närmaste heltal i allmänhet inte till en optimal eller ens tillåten lösning av heltalsproblemet.

Egenskapen total unimodularitet

Det finns en viktig klass av HLP-problem som löses lika enkelt som deras LP-relaxationer. Det gäller problem där bivillkorsmatrisen $A$ är totalt unimodulär (det vill säga att determinanten av varje kvadratisk undermatris är 0, +1 eller −1). Om matrisen $A$ är totalt unimodulär och vektorn $b$ är heltalsvärd, kommer alla hörn i polyedern av tillåtna lösningar för LP-relaxationen automatiskt att vara heltalsvärda. Följaktligen kommer lösningen som simplex­metoden finner att vara heltalsvärd. Exempel på sådana problem är transportproblemet och tilldelningsproblemet.

Lösningsmetoder

För att lösa allmänna HO-problem som saknar egenskapen total unimodularitet har exakta metoder baserade på idén om implicit uppräkning utvecklats.

• Branch and Bound-metoden (eng. Branch and Bound) — den primära exakta metoden, baserad på systematisk uppdelning av mängden tillåtna lösningar i delmängder (förgrening) och bortsållning av de delmängder som uppenbarligen inte innehåller den optimala lösningen. LP-relaxation används för att bedöma delmängdernas potential.

• Snittsplansmetoden (Gomorys metod; eng. Cutting Plane Method) — ett iterativt tillvägagångssätt som successivt lägger till nya linjära bivillkor ("snitt") till problemet. Dessa snitt "skär bort" bråktalslösningar från LP-relaxationen utan att beröra någon tillåten heltalslösning, och approximerar därigenom gradvis det tillåtna området för LP-relaxationen mot det konvexa höljet av heltalslösningarna.

Moderna lösare använder i regel hybridalgoritmer, såsom Branch and Cut-metoden (eng. Branch and Cut), som kombinerar fördelarna med båda tillvägagångssätten.

Exempel och tillämpningsområden

Heltalsoptimering möjliggör modellering av många klassiska problem inom kombinatorisk optimering.

• Ryggsäcksproblemet: ett klassiskt 0-1-programmeringsproblem där man ska välja en uppsättning föremål med maximalt totalt värde utan att överskrida en begränsning på den totala vikten.
• Handelsresandeproblemet: problemet att hitta den kortaste rutten som passerar genom en given uppsättning städer. Det kan formuleras som ett heltalsprogrammeringsproblem där variablerna anger om kanter i grafen inkluderas i den slutliga rutten.

Tack vare sin flexibilitet är HO ett av de mest efterfrågade verktygen inom operations research och tillämpas inom sådana områden som:

• Logistik och hantering av leveranskedjor: optimering av transportrutter, lokalisering av lager, lagerhantering.
• Produktionsplanering: utformning av produktionsscheman, resursfördelning, kapacitetsutnyttjande.
• Finans och ekonomi: sammansättning av investeringsportföljer, kapitalbudgetering.
• Telekommunikation och energi: nätverksdesign, planering av kraftverks­drift.

Se även

• Linjär programmering
• Branch and Bound-metoden

Noter

</references>