I have an exercise that tells me that, given a problem P (of which now I omit the description) there is no integrality gap between LP and ILP formulation of this problem, and for every fractional LP-solution, there exists an integral feasible solution with the same cost. Then I have to design a poly-time algorithm that from any given optimal LP-solution, computes such an optimal integer assignment.
The fact that there is integrality gap what does it mean in this case? I mean, if I design an approximation-algorithm to compute an optimal integer assignment from a given optimal LP-solution, I will get a solution with object value like something * Optimal value of LP problem . Isn't this in contrast with the fact that there's no IG? It should mean that the optimal value of LP and ILP should be the same, no?
Please, clarify my doubts.
EDIT: Michele is very interested in fashion and owns a whole bunch of nice outfits, collectively forming the set O. A set F of his friends all want to borrow one of Michele’s outfits to go to a wedding. This should be doable, since |F| ≤ |O|. However, due to different restrictions like size, body form, or adjustements that have to be made to an outfit to really look wedding-appropriate, there will be some extra effort w(f, o) ≥ 0 required when any friend f wants to wear outfit o. Of course, Michele would like to keep the overall effort to a minimum. a) Model the problem as an integer linear program, and relax this to a corresponding LP. b) Usually, the optimal solution to a problem’s LP-relaxation is better than that of the original ILP. The factor by which both can differ is called the integrality gap. For Michele’s problem, there is no such gap and for every fractional LP-solution, there exists an integral feasible solution with the same cost. Give a polynomial-time algorithm that, from any given optimal LP-solution, computes such an optimal integer assignmen