page_title: Integer programming
section_title: Example
hierarchical_section_title: Integer programming / Example
context_page_description: An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, in which the objective function and the constraints are linear.
  Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems.
  If some decision variables are not discrete the problem is known as a mixed-integer programming problem.
context_section_description: The plot on the right shows the following problem.
  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 dotted line as far upward while still touching the polyhedron. The optimal solutions of the integer problem are the points  and  which both have an objective value of 2. The unique optimum of the relaxation is  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.
caption: IP polytope with LP relaxation