Comment by thrance
It's harder than linear programming though.
It's harder than linear programming though.
I normally use Simplex method which is fast and not polynomial in the worst case though
You 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.
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).