# Implications of Integral linear program

Let $(P)$ an Integer Linear Program, where we aim to find $x\in \{0,1\}^n$ maximizing a linear function $f:\mathbb{R}^n\rightarrow\mathbb{R}$ under some linear constraints $Ax\le b$

Let $(P^*)$ be its relaxation, which means that the constraint $x\in \{0,1\}^n$ is replaced by $x\in [0,1]^n$.

Then, suppose that we know that $$\max_{x\in \{0,1\}^n} \left\{f(x), Ax\le b\right\} = \max_{x\in [0,1]^n} \left\{f(x), Ax\le b\right\}$$

Is it possible, given an optimal solution $y^*\in[0,1]^n$ of $(P^*)$ (that we have found with simplex algorithm for instance), to find an optimal solution $y\in\{0,1\}^n$ of $(P)$ (i.e. such that $f(y)=f(y^*)$ and $Ay\le b$), say in polynomial time ? Or is there any concrete conter-example ?

• What do you mean with "the value of these two programs match"? – orlp May 26 '18 at 0:39

In general, this is not possible unless P=NP. So, it is unlikely that such a method exists.

Many NP-hard problems can be modeled as an integer program, we take 3SAT for an example. Suppose we are given a 3SAT instance with clauses $$C_i$$ and variables $$v$$. For each clause, denote the variables that appear positive by $$C_i^+$$ and the variables that appear negative by $$C_i^-$$. Now, consider the following integer program $$P$$:

\begin{align} \max 1 \quad \text{s.t.} \quad & \sum_{v\in C_i^+} x_v + \sum_{v\in C_i^-} (1-x_v) \geq 1 \text{ for all } i\\ & x_v \in \{0,1\} \text{ for all } v \end{align}

Note that $$P$$ has a feasible solution if and only if our 3SAT instance is satisfiable. (a solution to $$P$$ corresponds to a satisfying assignment of the 3SAT instance) This solution is then 'optimal' as well, as all feasible solutions of $$P$$ have the same cost. This means that also the relaxation $$P^*$$ must have the same cost if $$P$$ is feasible. So, we will assume that the given 3SAT instance is satisfiable, so that the costs of $$P$$ and $$P^*$$ are equal.

Now, suppose we have some method to find a solution for $$P$$ from a solution $$y\in [0,1]^d$$ for $$P^*$$. As $$P^*$$ is a normal linear program, we can find such a solution $$y$$ in polynomial time, by using e.g. the ellipsoid method. Then, our method gives us a solution for $$P$$ in polynomial time. But this solution gives a satisfying assignment for our initial 3SAT problem, which means we can find a satisfying assignment to 3SAT problems in polynomial time. As finding a satisfying assignment for 3SAT is NP-hard (even if we know the instance has a satisfying assignment), this means that P=NP

I suppose that intuitively, what is going on here is that knowing the value of a solution to an integer program does not tell you a lot about the specific variable assignment. In a way, this is because the 'complexity' of a linear program lies mostly in its constraints, rather than the goal function.

Bare in mind that the simplex algorithm will always find an optimal solution that is a vertex of the polytope defined by $A x \leq b$. Hence if none of the vertices of the polytope are integral then it cannot find the integral solution.

For example, consider maximising $x + y$ subject to the constraints that $x + y \leq 4$, $y - x \leq 1$ and $x - y \leq 1$ as shown in the figure below. Then the optimal solution of this as an integral linear programming problem is $(2, 2)$ however the solution found by the simplex method for the relaxed problem will either be $(1.5, 2.5)$ or $(2.5, 1.5)$.

Note however that this situation can only occur if the relaxed version of the problem has more than one optimal solution. If the relaxed version has a unique optimum $y^*$ then thanks the equality that you have supposed $y^*$ will be integral and so the optimum solution to the integral problem.

• Although it is indeed true that the relaxed solution vector $y$ often isn't integral, this doesn't mean that there is no algorithm to construct an integral solution from such a vector. – Discrete lizard May 27 '18 at 12:55
• I don't see how this answers the question. The question is looking for a way to find a solution in polynomial time. The simplex algorithm is not a polynomial-time algorithm: it can take exponential time. So, suggesting to use the simplex algorithm doesn't meet the requirements in the question. – D.W. May 27 '18 at 14:29