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.


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.