Integer programming: Difference between revisions

Content deleted Content added
Linked to projection into simplex
Tags: Visual edit Mobile edit Mobile web edit
MrGumballs (talk | contribs)
Link suggestions feature: 2 links added.
Line 50:
\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]]
 
==Proof of NP-hardness==
Line 112:
===Using total unimodularity===
 
While in general the solution to LP relaxation will not be guaranteed to be integral, if the ILP has the form <math>\max\mathbf{c}^\mathrm{T} \mathbf{x}</math> such that <math>A\mathbf{x} = \mathbf{b}</math> where <math>A</math> and <math>\mathbf{b}</math> have all integer entries and <math>A</math> is [[unimodular matrix#Total unimodularity|totally unimodular]], then every [[basic feasible solution]] is integral. Consequently, the solution returned by the [[simplex algorithm]] is guaranteed to be integral. To show that every basic feasible solution is integral, let <math>\mathbf{x}</math> be an arbitrary basic feasible solution . Since <math>\mathbf{x}</math> is feasible,
we know that <math>A\mathbf{x}=\mathbf{b}</math>. Let <math>\mathbf{x}_0=[x_{n_1},x_{n_2},\cdots,x_{n_j}]</math> be the elements corresponding to the basis columns for the basic solution <math>\mathbf{x}</math>. By definition of a basis, there is some square submatrix <math>B</math> of
<math>A</math> with linearly independent columns such that <math>B\mathbf{x}_0=\mathbf{b}</math>.