3 ms·
You can solve the integer case via branch and bound: solving the relaxed linear problem and then in a tree search constraining integer variables to be 0/1. Pote
by zelos 4y ago
You can solve the integer case via branch and bound: solving the relaxed linear problem and then in a tree search constraining integer variables to be 0/1. Potentially they're doing something equivalent to that?
- coliveira 4y agoBut this leads to an exponential time algorithm.
- throw_pm23 4y agoIf the claim were true that the solution is always integer, then one could use a poly-time LP solver.