3 ms·
Yeah, but the problem is that the reduction might be large in practice (in the sense that reducing the original problem to SAT or MIP might require the introduc
by LolWolf 7y ago
Yeah, but the problem is that the reduction might be large in practice (in the sense that reducing the original problem to SAT or MIP might require the introduction of a large number of variables).
While theoretically polynomially reducible, if the rewriting multiplies the number of variables by 1000 then it’s likely not good in practice.
- kragen 7y agoI don't have experience reducing problems to SAT but I think the usual inflation factor is a lot less than 1000. I think the trivial reduction I found from SAT to ILP uses 3 ILP variables per SAT variable, but there might be a better one, and I might be misremembering; it might be 4 or something.
- LolWolf 7y agoSure, the SAT -> ILP is small but the reduction to SAT—or MILP directly—can sometimes (but not often) be large. Either way, I agree that there is likely some way in which the original commenter’s problem can be solved via MILP/MICP methods (indeed, I’ve found very few problems in practice that cannot be easily reduced) :)