kokonaislukiohjelmoinnin

Kokonaislukiohjelmointi (integer programming, IP) on optimoinnin ala, jossa päätösmuuttujat rajoitetaan ottamaan kokonaisluku- tai binääriarvoja. Tyypillisesti tavoitteena on minimoida tai maksimoida lineaarinen tavoite c^T x, ja ratkaisut sijaitsevat soveliaiden lineaaristen rajoitteiden sisällä.

Yleisessä muodossa ongelma esitetään usein seuraavasti: minimoidaan tai maksimisoidaan c^T x, s.t. Ax ≤ b, x ∈ Z^n, x ≥ 0. Ratkaisuja voi olla useita tai ne voivat olla ainutlaatuisia, ja osa muuttujista voi olla kokonaislukuja, osa binäärisiä (0/1). Kun sekä integer- että continuum-muuttujia esiintyy, kyseessä on sekamixed-integer programming (MIP).

Kokonaislukiohjepäteot tunnetaan laajasti osana tehollisinta lineaarista ohjelmointia (MILP) ja niiden ratkaisuun käytetään erilaisia menetelmiä, kuten branch-and-bound, branch-and-cut sekä LP-relakointia. Lisäksi käytetään leikkausmenetelmiä, Lagrangian-relaxaatiota, heuristiikkoja ja dekompositioratkaisuja suurten ongelmien hallintaan. Monimutkaisuuden vuoksi käytännön ratkaisut painottuvat heuristiikkaan ja tehokkaaseen laskentaan, vaikka teoreettisesti IP-ongelmat ovat yleisesti NP-hard.

Sovellukset kattavat monia aloja, kuten tuotannon suunnittelu, aikataulutus, logistiikka ja verkko-optimointi. Esimerkkejä ovat reitin- ja sijoitteluongelmat, henkilöstö- ja koneaikataulut sekä toimitusketjujen optimaalinen koordinaatio.

Historia ulottuu 1950- ja 1960-luvuille, jolloin kehitettiin varhaisia katkaisu- ja haaritusmenetelmiä sekä MILP-linjauksen ratkaisuja. Nykyisin kokonaislukiohjepäteot ovat keskeisiä sekä teoreettisesti että käytännössä monimutkaisissa päätöksentekoprosesseissa.