I disagree. Any particular descision problem can be seen as an instance of an NP-hard problem. If you know you're looking at a subset of some NP-complete family, you should try to work out whether that subset is NP-hard (which you could show by finding an NP-hard problem such that any instance can be converted to an instance of your problem).
A solver won’t be the optimal solution that you may (or more likely may not) discover for your particular problem. But it’ll be good enough in most cases.
A solver, like an integer linear programming solver, will find optimal solutions (or approximations, depending on what you ask for, and how long you give it to run).
Right. For some problems it’ll be optimal in execution time, for most it won’t be and you may be forced to let it approximate. But that’s usually still good enough.
Which is distinct from spending time trying to find an optimal solution, in the general case.
In general, using a general purpose solver won't be 'optimal in execution time'. (And in general, we have no clue what the optimal execution time for any NP hard or NP complete problem is, because then we'd also have solved P vs NP.)
For some problems it’ll be optimal in execution time, for most it won’t be and you may be forced to let it approximate. But that’s usually still good enough.
Yes, it depends on your problem and your application. For some problems, you can approximate well, and in some applications that's good. And in some other applications it's fine to occasionally not solve a problem at all.
Comments
Unless your particular NP-complete problem is trivially a transformation of one with known optimal solutions, it's generally not worth trying.
I disagree. Any particular descision problem can be seen as an instance of an NP-hard problem. If you know you're looking at a subset of some NP-complete family, you should try to work out whether that subset is NP-hard (which you could show by finding an NP-hard problem such that any instance can be converted to an instance of your problem).
See entanglement chess ( https://entanglement-chess.netlify.app/help.html ) for an example of a problem that is not NP-hard despite looking that way at first glance.
What makes you think so? Modern SMT solvers and Mixed Integer Linear programming solvers are really, really good.
That’s the sort of thing I mean by not bothering.
A solver won’t be the optimal solution that you may (or more likely may not) discover for your particular problem. But it’ll be good enough in most cases.
A solver, like an integer linear programming solver, will find optimal solutions (or approximations, depending on what you ask for, and how long you give it to run).
Right. For some problems it’ll be optimal in execution time, for most it won’t be and you may be forced to let it approximate. But that’s usually still good enough.
Which is distinct from spending time trying to find an optimal solution, in the general case.
In general, using a general purpose solver won't be 'optimal in execution time'. (And in general, we have no clue what the optimal execution time for any NP hard or NP complete problem is, because then we'd also have solved P vs NP.)
Yes, it depends on your problem and your application. For some problems, you can approximate well, and in some applications that's good. And in some other applications it's fine to occasionally not solve a problem at all.