21–30 of 84 posts
Sadly, the field is still mostly dominated by commercial solvers. There are a few open source ones but their performance is nowhere near the commercial ones which is kind of expected given the number of people working on them and the little funding they have. It is really a pity that the OR world hasn't embraced open source as much as ML world.
These solvers really show that NP-hardness is no reason to give up. For example, they can solve surprisingly large Traveling Salesmen instances to proven optimality.
Earlier quoted context omitted.
NP-hard problems commonly come up as human-solvable puzzles. Like Sudoku... or perhaps a more applicable problem... layout and routing of electronic components on a PCB and/or chip. Or even assembly-language register allocation (coloring and packing problem). Trained Humans are surprisingly good at these problems, far better than expected given how much computational power we have today. So its clear we don't underst…
I’m not sure there’s necessarily going to be a satisfying general answer to find here though. I can invent an NP-complete problem with very easy instances by combining a linear time problem with an NP-complete problem, e.g. “Does this list of cities have a complete route shorter than X OR is one of the cities New York?” All of the “yes New York” solutions are easy, but there’s no deep, satisfying reason for that. It’…
These solvers really show that NP-hardness is no reason to give up. For example, they can solve surprisingly large Traveling Salesmen instances to proven optimality.
Solvers aren't magic. But it turns out that many naturally occurring instances of NP-hard problems aren't the "really hard" instances that the NP-hardness proof depends on. Solvers can also fail for really tiny problems. You simply have to try to figure out how hard (or how well adapted to the solver's heuristics) your particular problem instance is.
Even the famous SAT problem can almost be considered solved nowadays with the solvers we have.
"Combining the computer hardware speed increase of 4,000 times with the solver software performance improvement of 5 million times, the total improvement from 1989 to 2024 is a factor of 20 billion times faster!" No wonder people have started making jokes that programmers no longer know how to program! We can get away with a lot more now.
In the time from the Cray 1 -> then, there were 6 orders of magnitude of hardware gains, and 6 orders of magnitude in software as well.
These solvers really show that NP-hardness is no reason to give up. For example, they can solve surprisingly large Traveling Salesmen instances to proven optimality.
Solvers aren't magic. But it turns out that many naturally occurring instances of NP-hard problems aren't the "really hard" instances that the NP-hardness proof depends on. Solvers can also fail for really tiny problems. You simply have to try to figure out how hard (or how well adapted to the solver's heuristics) your particular problem instance is.
I seem to vaguely remember — this is ~17 years ago, now — that it's possible to "characterize" the really bad edge-cases for simplex and work around them (the whole point of the paper).
[1] https://cstheory.stackexchange.com/questions/2373/complexity...
Earlier quoted context omitted.
Solvers aren't magic. But it turns out that many naturally occurring instances of NP-hard problems aren't the "really hard" instances that the NP-hardness proof depends on. Solvers can also fail for really tiny problems. You simply have to try to figure out how hard (or how well adapted to the solver's heuristics) your particular problem instance is.
I’m saying this because most people got from their CS degree that NP hardness is practically a death sentence. But it‘s really not true. Even if the problem is proven to be NP hard (or worse) and every previous approach has failed. There can still be some trick or technique (non heuristic!) that brings a breakthrough. Maybe you still wait 10^whatever years for a solution in some cases. But if you get an answer in sec…
These solvers really show that NP-hardness is no reason to give up. For example, they can solve surprisingly large Traveling Salesmen instances to proven optimality.
For someone who studies computational complexity theory, is the ability to solve some instances of NP-hard problems efficiently due more to these instances having lower average-case complexity than worst-case complexity, or because they possess structural properties that allow for more effective algorithmic exploitation?
More formally, are certain NP-hard problems easier to solve because the expected time to solve a randomly selected instance from their language is polynomial? Or is it because real-world instances are not uniformly distributed across the language, and these instances possess some amount of Kolmogorov compressibility that leads to better-than-expected performance?
Earlier quoted context omitted.
NP-hard problems commonly come up as human-solvable puzzles. Like Sudoku... or perhaps a more applicable problem... layout and routing of electronic components on a PCB and/or chip. Or even assembly-language register allocation (coloring and packing problem). Trained Humans are surprisingly good at these problems, far better than expected given how much computational power we have today. So its clear we don't underst…
Sudoku puzzles are usually set by humans.
Edit: Wayne Gould https://en.m.wikipedia.org/wiki/Wayne_Gould
Earlier quoted context omitted.
Solvers aren't magic. But it turns out that many naturally occurring instances of NP-hard problems aren't the "really hard" instances that the NP-hardness proof depends on. Solvers can also fail for really tiny problems. You simply have to try to figure out how hard (or how well adapted to the solver's heuristics) your particular problem instance is.
I’m saying this because most people got from their CS degree that NP hardness is practically a death sentence. But it‘s really not true. Even if the problem is proven to be NP hard (or worse) and every previous approach has failed. There can still be some trick or technique (non heuristic!) that brings a breakthrough. Maybe you still wait 10^whatever years for a solution in some cases. But if you get an answer in sec…
People unfamiliar with the matter may attempt to solve the problem, might even get rewarded for effort and hard work if management is also unfamiliar with the matter. Maybe it's fine though...?