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?



Generalized assignment problem with no integrality gap
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.


