Ich habe mein Problem (Tabellenlayout-Algorithmus) auf das folgende Problem reduziert:

Stellen Sie sich vor, ich habe N Variablen X1, X2, ..., XN. Ich habe auch einige (unbestimmte) Ungleichungen, wie:

X1 > = 2
x2 + X3 > = 13
usw.

Jede Ungleichung ist eine Summe aus einer oder mehreren Variablen und wird immer mit dem Operator> = mit einer Konstanten verglichen. Ich kann nicht im Voraus sagen, wie viele Ungleichungen ich jedes Mal haben werde, aber alle Variablen müssen nicht negativ sein, das ist also schon eine für jede Variable.

Wie kann man dieses System so lösen, dass die Werte der Variablen so klein wie möglich sind?

Hinzugefügt: Lesen Sie den Wikipedia-Artikel und stellen Sie fest, dass ich vergessen habe zu erwähnen, dass die Variablen Ganzzahlen sein müssen. Schätze, das macht es NP-schwer, nicht wahr?