Skip to content
All apps

Ganzzahlig ist anders: LP gegen IP

About this app

Warum ganzzahlige Programme nicht durch Runden der LP-Lösung entstehen: links das Gebiet mit Gitterpunkten, LP-Optimum an der Ecke und ganzzahligem Optimum weit davon, gerundete Nachbarn unzulässig oder schlecht, ganzzahlige Hülle mit der Fläche, die Schnittebenen wegschneiden. Rechts der Optimalwert über der rechten Seite b: Die LP-Gerade steigt mit dem Schattenpreis, das IP springt als Treppe. Fünf Schritte, drei Folienbeispiele, Maßstab ×1 bis ×10.

With explain mode: an AI tutor walks you through the app, points out what matters in the scene and answers your questions.

The idea

A linear program has a convex polygon as its feasible region; an optimum lies at a corner, and the simplex method only searches corners. If the variables must be integer, only the lattice points in the region remain. The integer optimum is then in general not a corner and not necessarily next to the LP optimum. Rounding the LP solution can be infeasible or end far from the optimum. The value of the LP relaxation is only a bound, and there are no shadow prices in the integer case.

What the app shows

On the left the region of a problem with two variables: the LP relaxation as an area, the lattice points, the LP optimum as a star and the integer optimum as a circle, plus the objective line. Five steps lead from the continuous solution via the lattice and the rounded neighbours to the integer hull, whose corners are integer; the area between relaxation and hull is hatched. On the right the optimal value over the right-hand side of a constraint: for the LP a line whose slope is the shadow price, for the IP a staircase. All values are computed exactly as fractions.

Try it yourself

In the base example the LP optimum is (9/4, 15/4) with F = 41¼, the integer one (0, 5) with F = 40; rounding reaches at most 39. Drag the right-hand side b: the LP optimum glides, the integer one jumps from (2, 3) via (4, 2), (1, 4) and (3, 3) to (0, 5). The two rounding pitfalls from the slides are separate examples. With scale ×10 the gap shrinks from 3.1% to 0.4%, and the objective arrow can be turned.

Frequently asked questions

Why can you not simply round the LP solution?
The rounded solution can violate constraints: if the LP optimum (3/2, 2) sits at a tip of the region, (1, 2) and (2, 2) are both infeasible. If it is feasible, it can be much worse than the optimum, for example 7 instead of 10, because the integer optimum lies somewhere else entirely.
What is the LP relaxation of an integer program?
The same problem without the integrality condition. Every integer solution is also feasible for the relaxation, so its optimal value is an upper bound for a maximisation. If the solution of the relaxation happens to be integer, it is also optimal for the integer problem.
Why are there no shadow prices in integer programming?
The optimal value does not change continuously with a right-hand side but jumps: one more unit sometimes brings nothing and sometimes a large gain. So there is no fixed slope that could be read as the price of a resource. What-if questions are answered by solving the problem again.
What does the integer hull in the app show?
The smallest convex polygon around all feasible lattice points. An LP over this hull would have the integer optimum as a corner. The hatched area between relaxation and hull contains no lattice point; cutting planes in branch and cut cut it away.

Subject: Operations research

More from Operations research

A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps