0
$\begingroup$

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.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.