Ganzzahlige lineare Optimierung

Die ganzzahlige lineare Optimierung (auch ganzzahlige Optimierung) ist ein Teilgebiet der angewandten Mathematik. Wie die lineare Optimierung beschäftigt sie sich mit der Optimierung linearer Zielfunktionen über einer Menge, die durch lineare Gleichungen und Ungleichungen eingeschränkt ist. Der Unterschied liegt darin, dass in der ganzzahligen Optimierung einige oder alle Variablen nur ganzzahlige Werte annehmen dürfen und nicht beliebige reelle Werte wie in der linearen Optimierung. Die ganzzahlige Optimierung lässt sich geometrisch als Optimierung über einem konvexen Polyeder (einem höherdimensionalen Vieleck) auffassen und ist damit ein Spezialfall der konvexen Optimierung. Im Unterschied zur linearen Programmierung ist allerdings das zugrundeliegende Polyeder meist nicht genau bekannt, was das Problem aus komplexitätstheoretischer Sicht NP-schwer macht.