MILPongelmissa

MILPongelmissa viitataan sekalaisten ja lineaaristen ohjelmien (MILP) luokkaan kuuluviin ongelmiin. Näissä päätösvektori x koostuu sekä kokonaislukumuuttujista että continuoista. Tyypillinen muoto on minimointi tai maksimointi: minimoidaan c^T x, ja rajoitteet ovat lineaarisia: Ax ≤ b sekä mahdollisesti x ≥ 0. Lisäksi osa muuttujista on kokonaislukuja: x_j ∈ Z for j in I, missä I on kokonaislukumuuttujien indeksi. Monet rajoitteet voivat olla sekä variational että kapasiteettipohjaisia.

MILP-ongelmat ovat NP-hard-luokan ongelmia, ja niiden ratkaisu voi vaatia vakavia laskentaresursseja suurissa tapauksissa. Ratkaisussa käytetään pääasiassa relaxointeja ja hakumenetelmiä, kuten branch-and-bound (haara- ja rajahaku) sekä usein myös leikkauspäivityksiä (branch-and-cut). Relaxointi ratkaistaan lineaariseksi ohjelmaksi, jonka ratkaisu ohjaa kokonaislukujen arvoa ja jolla voidaan tuottaa alarajoja tai ylärajoja. Heuristiset menetelmät sekä decompositio- ja matriisiratkaisujen tekniikat voivat nopeuttaa käytännön ratkaisuja suurissa sovelluksissa.

MILP-muotoja sovelletaan laajasti tuotannon ja kapasiteetin suunnitteluun, aikataulutukseen, logistiikkaan, verkko- ja energiainfrastruktuuriin sekä sijoituspäätöksiin. Tunnettuja ratkaisuohjelmistoja ovat CPLEX, Gurobi ja GLPK, sekä erilaiset avoimet työkalut kuten PuLP tai CBC. Tehokas muotoilu ja hyvänsen skaalautuvuuden varmistaminen ovat olennaisia tekijöitä käytännön sovelluksissa.