MILPsökning

MILPsökning är processen att hitta den optimala lösningen för blandade heltalslinjära programmeringsproblem, där målfunktionen och begränsningarna är linjära och vissa variabler är begränsade till heltal. Ett vanligt formuleringsalternativ är min c^T x under Ax ≤ b, där x ∈ R^n och x_i ∈ Z för en uppsättning index I. Sådana problem uppstår ofta i logistik, produktion och schemaläggning, men även i energisystem, nätverksdesign och finans.

Problemet är generellt NP-hårt eftersom det representerar ett omfattande kombinationellt sökområde. Exakta lösningar uppnås vanligtvis med globala optimeringsmetoder som bygger ett sökträd där varje nod löser en LP-relaxation och successivt introducerar integritetskrav i trädet. Målet är att bygga upp övre och nedre bounds samtidigt som sökrymden minskar, tills optimalitet uppnås eller tidsgräns nås.

Kärnteknikerna inkluderar LP-relaxationer för boundar, branch-and-bound där beslut tas om vilka variabler som ska delas, och branch-and-cut som kompletteras med cutting planes som Gomory-snitt och lift-and-project-tekniker. Heuristiker används för att snabbt hitta giltiga lösningar och förbättra primal-lösningar. Vidare används decompositionsmetoder som Dantzig-Wolfe och Benders när problem uppvisar tydlig struktur och separerbarhet.

Praktiska aspekter innefattar presolve och preprocess som minskar storleken och komplexiteten, bound-tightening, fixering av variabler och hantering av symmetrier. Moderna MILP-sökare kombinerar flera tekniker i en integrerad lösningsfilosofi och stöder modelleringsspråk som JuMP, AMPL eller GAMS.

Användningsområden täcker många branscher, inklusive försörjningskedja, produktion och schemaläggning, energi och nätverk, transport och finans. Trots starka framsteg finns inga generella polynomtidiga algoritmer för MILPsökning; praktisk prestanda bygger på kraftfull algoritmisk integration och god problemstruktur.