0
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.