Editing Integer programming (section)

==Example==
[[File:IP polytope with LP relaxation.svg|350px|thumb|IP polytope with LP relaxation]]
The plot on the right shows the following problem.

:<math> \begin{align}
\underset{x,y \in \mathbb{Z}}{\text{maximize}} \quad & y \\
\text{subject to} \quad &-x +y \leq 1  \\
            &3x + 2y \leq 12 \\
            &2x + 3y \leq 12 \\
            & x,y \ge 0
\end{align} </math>

The feasible integer points are shown in red, and the red dashed lines indicate their [[convex hull]], which is the smallest convex polyhedron that contains all of these points. The blue lines together with the coordinate axes define the polyhedron of the LP relaxation, which is given by the inequalities without the integrality constraint. The goal of the optimization is to move the black dashed line as far upward while still touching the polyhedron. The optimal solutions of the integer problem are the points <math>(1,2)</math> and <math>(2,2)</math> that both have an objective value of 2. The unique optimum of the relaxation is <math>(1.8,2.8)</math> with objective value of 2.8. If the solution of the relaxation is rounded to the nearest integers, it is not feasible for the ILP. [[Simplex#Projection onto the standard simplex|See projection into simplex]]