Die meisten Ergebnisse beziehen sich auf rationale Eingabedaten. Eines der wesentlichen Probleme bei der Lösung derartiger Aufgaben ist das Fehlen eines befriedigenden Dualitätssatzes; für den üblichen Dualitätssatz der linearen Optimierung führt die Forderung nach Ganzzahligkeit der Variablen i. a. zu einer positiven Dualitätslücke. Als algorithmische Konsequenz dieses Sachverhalts sind ganzzahlige lineare Optimierungsprobleme vermutlich schwieriger zu lösen als lineare Optimierungsprobleme ohne zusätzliche Forderung an die Ganzzahligkeit der Variablen. So ist das Entscheidungsproblem: „Gegeben ein System A · x ≤ b mit A ∈ ℚ^m×n, b ∈ ℚ^m; gibt es eine Lösung \(\bar{x}\in \mathbb{Z}^{n}\)“ NP-vollständig (im Gegensatz zur Suche einer Lösung in ℚⁿ, die in Polynomzeit ausführbar ist). Eine Ausnahme bildet die Teilmenge ganzzahliger linearer Optimierungsprobleme, bei denen alle Eingabedaten ganzzahlig sind und die Matrix A unimodular ist (d. h. für alle quadratischen Untermatrizen von A hat die Determinante einen Wert in {−1, 0, 1}). Diese Probleme haben immer ganzzahlige Lösungen, welche auch effizient gefunden werden können (bzgl. des Modells der Turingmaschine). Wichtige Lösungsverfahren für ganzzahlige lineare Probleme sind Schnittebenenverfahren wie dasjenige von Gomory.

Man vergleiche auch den Artikel Ganzzahlige Optimierung.

[1] Schrijver, A.: Theory of linear and integer programming. John Wiley and Sons, 1986.