Ganzzahlige Optimierung

Ganzzahlige Optimierung Definition

Die ganzzahlige Optimierung ist eine Optimierung mit einer Besonderheit: alle Variablen oder zumindest einige Variablen (man sagt dann: gemischt-ganzzahlige Optimierung) müssen ganzzahlig sein.

Das ist bei vielen realen Problemen so: Es gibt einen, zwei, drei usw. Container – nicht 3,6175 Container. Ebenso bei Stückgut: Autos, Uhren, Computer usw., die Lösung muss ganzzahlig sein, um umsetzbar zu sein.

Die ganzzahlige Optimierung kann linear oder nichtlinear sein, i.d.R. geht es um die ganzzahlige lineare Optimierung.

Eine naheliegende Idee wäre, eine "normale" lineare Optimierung vorzunehmen und das gefundene Ergebnis dann auf- oder abzurunden – leider führt dies nicht verlässlich zur optimalen Lösung.

Mögliche Lösungsmethoden für ganzzahlige Optimierungsprobleme: