5 ms·

Cvx solves a relaxed problem trivially in matlab and then you can heuristically round to integer. http://stanford.edu/class/ee364b/lectures.html http://stanford

Cvx solves a relaxed problem trivially in matlab and then you can heuristically round to integer. http://stanford.edu/class/ee364b/lectures.html http://stanford.edu/class/ee364b/lectures.html Under L1 convex cardinality

ulucs 7y ago
If I may quote from the Integer Programming chapter in Vohra's book, "Before proceeding you should convince yourself that no ‘simple’ scheme based on solving the underlying linear program and rounding the resulting solution can find the optimal integer solution."
- LolWolf 7y ago
  Depends on the problem (in max-flow, min-cut the trivial rounding scheme gets you the optimal point immediately :). Kidding aside, generally this is very true, but for a surprising number of practical problems, the LP relaxation and some redundant constraints will often have zero integrality gap. (In many other problems, you’re hosed, so there’s also that.) EDIT: For context, this is how LDPCs are decoded in robust cases. https://people.eecs.berkeley.edu/~wainwrig/Papers/FelWaiKar05.pdf https://people.eecs.berkeley.edu/~wainwrig/Papers/FelWaiKar0...
  - kxyvr 7y ago
    I suppose that we could also state that solving with a totally unimodular matrix also absolves us from going through the trouble of going through branch and bound, but that's a pretty niche case. I guess I react strongly whenever I hear this kind of sentiment because the result of rounding the continuous solution can be arbitrarily bad, but now we have a false sense of confidence that we did some kind of optimization, when we really didn't. My experience has been that rounding continuous solutions to integer gives some pretty interesting and incredibly bad solutions. For posterity's sake, Wolsey has a good example of how things can go poorly in the introduction of the book Integer Programming: max 1 x1 + 0.64 x2 st 50 x1 + 31 x2 <= 250 3 x1 - 2 x2 >= -4 x1, x2 >=0 x1, x2 integer The linear programming solution is (376/193,950/193), which is approximately (1.9482,4.9223). The integer optimal solution is (5,0), which is far away. I'll also contend that the integer programming solvers nowadays are really good. If we can get away with rounding the solution, then the the solver will find the solution in only a few iterations because it often does precisely that in order to go through the branch, bound, and cut algorithm. The difference is that a good solver can get a certificate of optimality when it finds the solution, so that we know we're right.

ulucs 7y ago

If I may quote from the Integer Programming chapter in Vohra's book, "Before proceeding you should convince yourself that no ‘simple’ scheme based on solving the underlying linear program and rounding the resulting solution can find the optimal integer solution."

LolWolf 7y ago
Depends on the problem (in max-flow, min-cut the trivial rounding scheme gets you the optimal point immediately :). Kidding aside, generally this is very true, but for a surprising number of practical problems, the LP relaxation and some redundant constraints will often have zero integrality gap. (In many other problems, you’re hosed, so there’s also that.) EDIT: For context, this is how LDPCs are decoded in robust cases. https://people.eecs.berkeley.edu/~wainwrig/Papers/FelWaiKar05.pdf https://people.eecs.berkeley.edu/~wainwrig/Papers/FelWaiKar0...
- kxyvr 7y ago
  I suppose that we could also state that solving with a totally unimodular matrix also absolves us from going through the trouble of going through branch and bound, but that's a pretty niche case. I guess I react strongly whenever I hear this kind of sentiment because the result of rounding the continuous solution can be arbitrarily bad, but now we have a false sense of confidence that we did some kind of optimization, when we really didn't. My experience has been that rounding continuous solutions to integer gives some pretty interesting and incredibly bad solutions. For posterity's sake, Wolsey has a good example of how things can go poorly in the introduction of the book Integer Programming: max 1 x1 + 0.64 x2 st 50 x1 + 31 x2 <= 250 3 x1 - 2 x2 >= -4 x1, x2 >=0 x1, x2 integer The linear programming solution is (376/193,950/193), which is approximately (1.9482,4.9223). The integer optimal solution is (5,0), which is far away. I'll also contend that the integer programming solvers nowadays are really good. If we can get away with rounding the solution, then the the solver will find the solution in only a few iterations because it often does precisely that in order to go through the branch, bound, and cut algorithm. The difference is that a good solver can get a certificate of optimality when it finds the solution, so that we know we're right.