heltallsprogrammer

Heltallsprogrammering er en gren av optimering som behandler beslutninger hvor noen eller alle variabler må være heltall. I den klassiske innrammingen maksimerer eller minimerer man et lineært mål c^T x under lineære restriksjoner Ax ≤ b, med integritetskrav på variablene: x ∈ Z^n eller x ∈ {0,1}^n for binære beslutninger. Når alle variabler er heltall kalles problemet heltallsprogrammering, mens det i tilfeller der bare noen variabler er heltall kalles det blandet heltallsprogrammering (MILP). Heltallsproblemer oppfører seg ofte annerledes enn ren lineær programmering og kan være betydelig vanskeligere å løse i praksis.

Problemløsing i heltallsprogrammering er generelt NP-hard og ofte stor. En vanlig tilnærming er å løse LP-relaksasjonen, der integritetskravene slås av, for å få en bound og en veiledning for hele problemet. Kjennskap til matriseegenskaper som total unimodularity kan gjøre at LP-løsningen er integral, noe som gjør problemet lettere å løse med LP-løsere. Ofte må man imidlertid bruke mer avanserte metoder for å finne heltallsløsninger.

De viktigste metodene inkluderer gren-og-bound (branch-and-bound) og gren-og-kutt (branch-and-cut), som kombinerer søk i beslutningstrær med kuttemetoder (cutting planes). I tillegg brukes heuristikker og metaheuristikker for raskt å finne gode, om enn ikke nødvendigvis optimale, løsninger. Mange problemformuleringer kan også løses av standard MILP-løsere ved bruk av verktøy som Gurobi og CPLEX, eller åpne løsere som GLPK og SCIP.

Anvendelser inkluderer logistikk og transport, produksjonsplanlegging, nettverksdesign, energisystemer og kapitalbudsjett. Heltallsprogrammering er en viktig del av operasjonsforskning og industriell beslutningsstøtte, særlig i problemer der valg er diskrete eller av kritisk betydning.