heltallsprogrammeringer

Heltallsprogrammeringar är en gren inom matematisk optimering där beslutvariablerna åtminstone delvis måste anta heltalsvärden. Vanliga fall är heltalsprogrammering där samtliga variabler är heltal, och blandat heltalsprogrammering där vissa variabler är heltal och andra är kontinuerliga (MILP, mixed-integer linear programming).

Formulering och grundläggande begrepp: En typisk modell är att maximera eller minimera en målfunktion c^T x under linjära begränsningar Ax ≤ b, där x är en vektor av beslutvariabler som i allmänhet måste vara heltal. I fallet x ≥ 0 gäller icke-negativt heltalsvärden. I många tillämpningar används 0-1-variabler där varje x_i endast kan anta värdet 0 eller 1.

Vanliga problemtyper och tillämpningar: Heltalsprogrammering används för problemlösning inom logistik, ruttplanering, schemaläggning, produktionsplanering, nätverksdesign och finansiel beslut. Exempel inkluderar knapsack-problem, set-covering, facility location och olika typer av planeringsproblem där beslut kräver tydliga ja/nej- eller antalval.

Lösningsmetoder och komplexitet: Heltalsprogrammering är generellt NP-hård, och antalet möjliga lösningar växer explosivt med problemstorleken. Exakta metoder bygger ofta på LP-relaxation följt av gren- och bounding-tekniker eller gren- och skärningsmetoder (branch-and-bound/branch-and-cut) samt skärnings-planet-tekniker. Specialiserade dekompositionsmetoder som Benders kan vara användbara för vissa strukturer. Praktiska lösningar uppnås vanligtvis med MILP-solvern som CPLEX, Gurobi eller CBC, ofta kombinerade med heuristiker för vad-om-lösningar.

Historia och betydelse: Intentionen att formellt hantera heltal i optimering nådde framgång på 1950–tal och 1960–tal, med utveckling av metoder som Gomorys skärningsplaner som förbättrade lösningarna av heltalsproblem. Heltallsprogrammeringar har sedan dess blivit en central teknik inom operationell forskning och beslutsstöd.