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,
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
Anvendelser inkluderer logistikk og transport, produksjonsplanlegging, nettverksdesign, energisystemer og kapitalbudsjett. Heltallsprogrammering er en viktig del av