3 ms·
Oh lucky you, your optimization problem is linear. I do something similar, but we have to use heuristics because our problem can't be modelled as a linear probl
by aliceryhl 7y ago
Oh lucky you, your optimization problem is linear. I do something similar, but we have to use heuristics because our problem can't be modelled as a linear problem.
- yoshimiagava 7y agoInteresting! Could you elaborate on this please?
- LolWolf 7y agoI’d be curious to hear more... often a lot of nonlinear problems can be turned into mixed integer cone programs (MICPs) which are also often fast to approximately or exactly solve in practice.
- kragen 7y agoSee, that's what I thought before I audited an operations research class, but it turns out that the reduction from SAT to ILP is trivial, so there are no problems in NP that can't be modeled as integer linear optimization problems.
- LolWolf 7y agoYeah, 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) :)