die Lösungstheorie von Optimierungsproblemen der im folgenden beschriebenen Gestalt.

Gegeben ist eine endliche Menge A ={1, …, n} sowie eine Familie {A_i, 1 ≤ i ≤ s} von Teilmengen von A. Eine Zielfunktion f ordnet jeder dieser Mengen A_i einen Funktionswert f(A_i) zu, der optimiert werden soll. Typische kombinatorische Optimierungsprobleme treten z. B. bei der ganzzahligen Optimierung oder in der Graphentheorie auf.