2
$\begingroup$

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 ?

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

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.

$\endgroup$
0
$\begingroup$

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)$.

enter image description here

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Discrete lizard May 27 '18 at 12:55
  • 1
    $\begingroup$ 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. $\endgroup$ – D.W. May 27 '18 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.