I modeled an ILP where I have a set of outfits and a set of friends with , all these friends should take one outfit with the lowest effort , considering the fact that these outfits differ in size, body form, and adjustments. The solution should be like this:
with the next constraints:
The relaxation to LP would be to put:
Now, considering the fact that we don't have an integrality gap in this problem and for every fractional LP-solution, there exists an integral feasible solution with the same cost, how can we give give a polynomial-time algorithm that, from any given optimal LP-solution, computes such an optimal integer assignment.