Comment by LegionMammal978
7 hours ago
Idk, I also thought so once upon the time. "Everyone knows that you can usually do much better than the worst case in NP-hard problems!" But at least for the non-toy problems I've tried using SAT/ILP solvers for, the heuristics don't improve on the exponential worst case much at all. It's seemed like NP-hardness really does meet the all-or-nothing stereotype for some problems.
Your best bet using them is when you have a large collection of smaller unstructured problems, most of which align with the heuristics.
> Your best bet using them is when you have a large collection of smaller unstructured problems, most of which align with the heuristics.
Agreed. An algorithm right now in our company turns a directed graph problem, which to most people would seem crazy, into roughly ~m - n (m edges, n nodes) SAT checks that are relatively small. Stuffing all the constraints into an ILP solver would be super inefficient (and honestly undefined). Instead, by defining the problem statement properly and carving out the right invariants, you can decompose the problem to smaller NP-complete problems.
Definitely a balancing act of design.
For some problems, there is not much you can do. But for many, it works.