Forschung in der Arbeitsgruppe für Algorithmen und Komplexität

Bei Ganzzahligen Linearen Programmen (ILPs) ist die Aufgabe, einen Vektor x zu finden, der eine lineare Zielfunktion maximiert und eine Menge an linearen Bedingungen (gegeben durch eine Matrix A und rechte Seite b) erfüllt. Diese sehr allgemeine Form ermöglicht es, unzählige Optimierungsprobleme – darunter unter Anderem auch Scheduling- und Packungsprobleme – zu modellieren. Ein Algorithmus zum Lösen von ILPs kann daher auch zum Lösen vieler anderer Probleme genutzt werden. Da dieses Problem ebenfalls NP-schwer ist, betrachtet man vor allem ILPs mit entweder

• wenigen Variablen (d. h. der gesuchte Vektor x hat nur wenige Einträge),
• wenigen Bedingungen und kleinen Einträgen in der Matrix A oder
• einer Matrix A, die besondere Strukturen aufweist.