3 ms·
Unfortunately, I can't show a picture here, but I like one example in the introduction of Wolsey's book, "Integer Programming." It provides a short example of
by kxyvr 5y ago
Unfortunately, I can't show a picture here, but I like one example in the introduction of Wolsey's book, "Integer Programming." It provides a short example of why rounding the answer from a continuous (LP) relaxation of an integer programming problem is not sufficient or even close to the integer optimal solution.
Consider the integer program
max 1.00 x1 + 0.64 x2
50 x1 + 31 x2 <= 250
3x1 - 2x2 >= -4
x1, x2 >=0 and integer
As we can see from Figure 1.1, the linear programming solution (376/193,950/193) is a long way from the optimal integer solution (5,0).
Personally, I like this example because it demonstrates that we need to be careful when working with integer optimization problems. It's not that rounding sometimes doesn't work. Hell, we use continuous algorithms like simplex when solving for integer solutions using things like branch and bound. However, it's not the same and depending on the application it can be dangerous to assume so. This also has implications for things like machine learning because they do use optimization algorithms to find their solutions and they often are based on continuous formulations used to give discrete results. It might work, but we should be really careful when it matters most.
- jamessb 5y agoImage of this example: https://imgur.com/a/Mjo1c0j https://imgur.com/a/Mjo1c0j
- wenc 5y agoJust chiming in here... I don't know that I would consider this counter-intuitive. Most introductory MIP textbooks make it amply clear that that IP and LP relaxations wouldn't be the same in general (except in special cases like when the constraint matrix is totally unimodular). Even so, sometimes LP relaxations with rounding can produce "good enough" answers if an IP solution is intractable in a reasonable time. Consider the Wolsey example; the optimal integer objective is 5.0, and the LP relaxation (376/193,950/193) objective is an optimistic 5.10, whereas the closest rounded LP relaxation (2,4) objective is 4.56. Even though the x may be in a completely different area than the integer optimal solution, it still manages to achieve roughly the same objective. So depending on the application, the rounded LP relaxation may just be good enough, especially in iterative processes (like control) where you just need to take baby steps toward a larger objective. It's not optimal, but it's not terrible.