3 ms·
It's substantially harder than linear programming: it's equivalent to SAT, whereas linear programming is merely polynomial-time (and in practice weakly polynomi
by lambdaone 1y ago
It's substantially harder than linear programming: it's equivalent to SAT, whereas linear programming is merely polynomial-time (and in practice weakly polynomial-time with current algorithms).
- firesteelrain 1y agoI normally use Simplex method which is fast and not polynomial in the worst case though
- sirwhinesalot 1y agoYou can always just run a portfolio of Simplex/Barrier/PDLP and just grab whichever returns something first. The latter two are usually slower but polynomial time, so you always win. Can't do that with SAT or ILP.
- firesteelrain 1y agoSimplex usually runs fast, and Barrier or PDLP help with LP. But for SAT or ILP, there’s no quick way. You can’t just try a bunch and pick the fastest. Those problems are just tougher.