Heltalsprogrammering

Et heltalsprogram eller heltalsprogrammerings-problem er et matematisk optimeringsproblem hvor alle variablene kræves at være heltallige. Hvis kun nogle af variablene kræves at være heltallige (dvs. resten er kontinuerte) haves et såkaldt blandet heltalsprogram. Ofte når der tales om heltalsprogrammer (og blandede heltalsprogrammer) antages det, at både begrænsningerne og objektfunktionen er lineære, hvilket vil sige, at man har et lineært heltalsprogram.

Generelle heltalsprogrammer er NP-hårde. Det specielle tilfælde hvor alle heltalsvariable skal være enten 0 eller 1 og hvor problemet er lineært er blandt Karps 21 NP-komplette problemer. Man børe notere sig, at et heltalsprogram er et særtilfælde af et blandet heltalsprogram hvor antallet af kontinuerte variable er nul. Det vil sige, at blandede heltalsprogrammer er en generalisering af heltalsprogrammer, og derfor mindst lige så svære at løse.

Lineære blandede heltalsprogrammer

I dette afsnit er fokus på blandede heltalsprogrammer. Et generelt blandet heltalsprogram kan opskrives på følgende vis:
Lad $A$ og $B$, $c$, $h$ og $b$ være helholdvis rationale matricer og vektorer og lad $l_{j},\ u_{j},\ d_{i}$ og $h_{i}$ være rationale tal. Da er et generelt blandet heltasprogram givet ved:

${\begin{aligned}\max &\ c^{T}x+h^{t}y\\{\text{s.t.:}}&\ Ax+By\leq b\\&l_{j}\leq x_{j}\leq u_{j},\quad \forall j\\&d_{i}\leq y_{i}\leq h_{i},\quad \forall i\\&y_{i}\in \mathbb {Z} ,\quad x_{i}\in \mathbb {R} \end{aligned}}$

Som med lineære programmer, kan man opskrive dette problem i standard from ved at tilføje slack variable

${\begin{aligned}\max &\ c^{T}x+h^{t}y\\{\text{s.t.:}}&\ Ax+By+s=b\\&l_{j}\leq x_{j}\leq u_{j},\quad \forall j\\&d_{i}\leq y_{i}\leq h_{i},\quad \forall i\\&s_{k}\geq 0,\quad \forall k\\&y_{i}\in \mathbb {Z} ,\quad x_{i}\in \mathbb {R} \end{aligned}}$

Disse to optimeringsproblemer er matematisk ækvivalente og har samme optimale løsningsværdi.

Konvertering til 0-1 programmerings problem

Man kan her notere sig, at ethvert begrænset blandet heltsprogram kan omskrives til et blandet 0-1 program. Det vil sige, at de variable som skal være heltallige alle er binære. For eksempel kan en heltalsvariabel $0\leq y\leq h$ omskrives ved hjælp af $\log _{2}(h)+1$ binære variable:

$y=y_{1}+2y_{2}+4y_{3}+\cdots +2^{\log _{2}(h)}y_{\log _{2}(h)+1}$

Det vil sige, at ethvert begrænset blandet heltalsprogram er et specialtilfælde af et blandet 0-1 program, hvorfor et blandet 0-1 også er NP-komplet. Faktisk behøver man ikke gøre sig antagelsen om begrænsethed, men det gør matematikken noget nemmere (for flere detaljer henvises til "Nemhauser & Wolsey")

Man kan notere sig, at (næsten) alle praktisk forekomne optimeringsproblemer er begrænsede i den forstand, at der vil være en øvre og en nedre grænse for alle variable. Hvis for eksempel en variabel $x$ angiver forbruget af en given råvare, da vil der være en (måske meget stor) øvre grænse for hvor meget af denne råvare man kan forbruge.

Løsningsmetoder for blandede heltalsprogrammer

Blandede heltalsprogrammer er et særdeles velstuderet område inden for både operationsanalyse, datalogi og matematik. En lang række algoritmer og metoder er derfor udviklet. Nedenfor er listet en række af de mest benyttede eksakte metoder:

• Snitplansmetoden (cutting plane method)
• Branch and bound
• Branch and price
• Dynamisk programmering
• Constraint programming

Det er dog ikke alle blandede heltalsprogrammer hvor det er praktisk muligt at finde en optimal løsning, grundet for eksempel begrænset tid eller hukommelse. I stedet benytter man sig således ofte af heuristikker til at finde en løsning, som er bedst mulig. Nedenfor er listet nogle af de mest kendte heuristikker og meta-heuristikker:

• Greedy metoder
• Local search metoder
• Simulated annealing
• Variable neighbourhood search
• Genetic and evolutionary algorithms