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  og , ,  og  være helholdvis rationale matricer og vektorer og lad  og  være rationale tal. Da er et generelt blandet heltasprogram givet ved:

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

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  omskrives ved hjælp af  binære variable:

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  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

Noter 

Matematik