Comment by lambdaone
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).
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).
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.
I normally use Simplex method which is fast and not polynomial in the worst case though