ein im folgenden näher beschriebenes Schnittebenenverfahren zur Behandlung ganzzahliger linearer Optimierungsprobleme.

Man betrachte das Problem min c^T · x unter den Nebenbedingungen \begin{eqnarray}A\,\cdot \,x=b,\,\,x\,\ge \,0.\end{eqnarray}

Dabei seien alle Dateneinträge in A, b und c ganzzahlig (oder rational). Das Optimum wird bezüglich ganzzahliger Vektoren x ∈ ℤⁿ gesucht. Zunächst löst man mit der Simplexmethode das Optimierungsproblem ohne Berücksichtigung der Forde-rung nach Ganzzahligkeit der Lösung. I. allg. wird eine Lösung \(\bar{x}\) die Ganzzahligkeit nicht erfüllen. Deswegen wird eine weitere Nebenbedingung, ein sogenannter Gomory-Schnitt, hinzugefügt.

Sei B die zugehörige Matrix einer zulässigen Basis für \(\bar{x}\). Jede Basisvariable x_i, i ∈ I, läßt sich (nach Multiplikation von A·x = b mit B⁻¹) als Funktion in den Nicht-Basisvariablen x_j, j ∈ J, schreiben, etwa \begin{eqnarray}{x}_{i}=\frac{{s}_{i}}{D}\,+\,\frac{1}{D}\,\cdot \,\displaystyle \sum _{j\in J}{t}_{ij}\,\cdot \,{x}_{j}\,.\end{eqnarray}

Dabei sind D := | det(B)| und die s_i, t_ij ganzzahlig. Die Basislösung entsteht durch Wahl x_j := 0 gemäß \({x}_{i}=\frac{{s}_{i}}{D}\). Nach Voraussetzung ist hier ein x_i nicht ganzzahlig (sonst wäre das gesamte Problem gelöst).

Es wird nun nach einem zulässigen Punkt gesucht, bei dem die Komponente x_i ganzzahlig wird. Die obige funktionale Abhängigkeit liefert zunächst \begin{eqnarray}{s}_{i}=\displaystyle \sum {t}_{ij}\,\cdot \,{x}_{j}\,\,\mathrm{mod}\,D\,.\end{eqnarray}

Definiert man zu λ ∈ ℤ den Wert |λ|_D als Repräsentant modulo D von λ in {0, 1,…,D − 1}, so folgt die Lösbarkeit der Gleichung \begin{eqnarray}\displaystyle \sum _{j\in J}{|{t}_{ij}|}_{D}\,\cdot \,{x}_{j}={|{s}_{i}|}_{D}\,+\,k\,\cdot \,D\end{eqnarray} mit k ∈ ℕ₀ (da x ≥ 0 und |s_i|_D + k · D ≥ 0 gelten muß). Man fügt nun als Nebenbedingung die Ungleichung \begin{eqnarray}\displaystyle \sum _{j\in J}{|{t}_{ij}|}_{D}\,\cdot \,{x}_{j}\,\ge \,{|{s}_{i}|}_{D}\end{eqnarray} hinzu, und wiederholt das Vorgehen für das neue System. Geeignete Variationen des Verfahrens garantieren die Endlichkeit.