Suppose I am solving the generalized assignment problem, so that I am given matrices $U$ and $W$ and a vector $c$ (all three of which have, say, positive entries), and I want to solve $$\text{minimize}_{x_{ij}}\sum_{i,j}u_{ij}x_{ij}s.t.$$ subject to the constraints that $$\sum_{j}w_{ij}x_{ij}\leq c_{i}\text{ for all }i$$ and $$\sum_{i}x_{ij}=1\text{ for all }j$$ with the requirement that $x_{ij}\in\{0,1\}$. This problem is known to be NP-hard. Now, let's suppose that we just happen to get lucky, and there exists a solution $x^{*}$ to the linear programming relaxation of the above integer program that has all entries equal to $0$ or $1$. Is it easy to find this nice solution, given that the solution to the LP relaxation may not be unique?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
This is trivial. A solution to the problem is precisely a solution to the linear programming relaxation that happens to have all entries 0 or 1. If there was an easy (i.e. polynomial-time) way to find the "nice solution" when it exists, this would lead to a polynomial-time decision procedure: try the easy way to find the "nice solution", and if unsuccessful conclude that the problem has no solution. If $P \ne NP$, this can't exist.
answered Sep 18, 2014 at 21:01