NP-hard does not mean easy
NP-hard does not mean easy

                
                    
                        
                            August 25, 2023
                        
                
                
                

                

                
                    
                        Recently the internet resurfaced
my 2017 article, "NP-hard does not mean hard".
I wrote the article mainly
to express the nuance that NP-hardness
only models the worst case of a problem,
not the average case under any particular distribution—i.e.,
the instances you happen to encounter in the real world.
More specifically, being NP-hard means
that a problem has sufficient expressive power
to model arbitrary boolean logic.
But you can't blame NP-hardness
for why you're bad at Super Mario.
One commenter made a remark
that I've seen repeated elsewhere
in various forms, that NP-hard problems
like SAT and traveling salesman
are "basically solved,"
due to the quality of modern SAT solving techniques
CDCL,
modern integer linear programming (ILP) solvers like Gurobi,
and, I guess, decent heuristics for traveling salesman problems (I find the focus on TSP strange because I haven't yet heard of anyone who really cares about solving TSP in practice, compared to packing and scheduling problems which are everywhere).
Based on my experience, both directly at Google
and indirectly through research and interviews
I've conducted for my next book,
Practical Math for Programmers,
this is far from the case.
Though all these tools that solve NP-hard problems are good,
everyone who actually uses them
is acutely aware of the underlying difficulty.
we can hardly call the problems themselves "solved."
I used ILP solvers at Google to solve massive
optimization problems.
Or rather, we tried to make them massive,
packing as much as we could into a single model.
But we quickly hit the limits
of what the world's best solvers could handle
in a decent time frame (say, 12 hours).
A big part of the problem with my work at Google
included numerical stability and small numbers.
As you might know, an ILP solver is minimizing or maximizing a linear objective—in
my case cost to Google—subject to a set of linear constraints.
My constraints collectively expressed
many of the constraints of building and managing computers in datacenters.
Originally we hoped to build one massive ILP to solve it all,
but it just not realistic.
For one, the decisions that needed to be made
ranged in scale from the cost of individual memory sticks
to the global power usage of all of Google's datacenters.
These numbers differ by many, many orders of magnitude.
And internally, an ILP solver decides where to search next
by inspecting various ratios of constants
from the problem definition.
When these ratios get smaller than 10^(-16),
floating point inaccuracy creeps in and makes the solver
flounder by exploring the wrong parts of the search tree.
Beyond that,
ILP solvers do not always return optimal solutions.
They instead ask the user to configure an optimality gap,
and the solver stops when its best solution
is provably better than the threshold.
In particular, with a poor choice of units,
that optimality gap can hide all the "real" hardness in your problem.
Or worse, it can cause the solver to sacrifice
the quality of many small decisions,
the sum of which are small compared to the major decisions being made.
That seems like an acceptable trade-off,
until the team that is responsible for ensuring the small decisions are sensible
come yelling that the solver is making stupid decisions, and they're right.
Incrementally better solvers or a better model won't help you here.
It's the core NP-hardness that matters:
working out that remaining 0.01% optimality
is where the exponential growth comes in,
and proving a given solution is optimal requires
the solver to increase its lower bound on the optimal solution,
which in that last mile is effectively a brute force search.
The way to deal with this
is to decompose a massive problem
into subproblems.
Solve the models in order, or in parallel,
or in a dependency graph topological sort.
The decomposition naturally sacrifices global optimality
so the damn solver can finish in time.
In many cases it makes sense,
since there is a natural decomposition
that you can plan large-scale details of a datacenter building,
that shouldn't have too large an impact on any individual server rack.
But still, some decisions that must be made at scale and in aggregate
prevent more optimal choices made later.
So the challenge is to find a decomposition that is workable
for the business.
But it all starts from the failure to solve an NP-hard problem.
Similar examples pop up all throughout applied solvers.
I'll give two brief ones that I expand on in Practical Math.
The first is in version selection for package managers.
The leading techniques are based on CDCL solvers—see PubGrub—but
they can't use existing solvers as a black box because
they are too slow. The Conda package manager made a big issue of its
performance problems in this
article,
and it boils down to "SAT solvers are slow."
Even more modern solvers like PubGrub
needed to reimplement CDCL from scratch
so that they could inject custom domain-aware heuristics
to make it performant enough for modestly-sized package ecosystems.
Another, which I have been studying more recently
after an excellent interview with Lily Xu,
is in how ILP solvers were applied to wildlife conservation.
More specifically, wildlife sanctuaries around the world have to deal with poachers
and other things that threaten wildlife.
On the poaching side, the math problem is in how to schedule ranger patrols
in the park so as to best combat poaching.
The original techniques that Xu and her colleagues tried to use,
based on some prior work of Milind Tambe and his group on patrol scheduling
at airports for counterterrorism,
used ILPs to solve a game-theoretic
formulation of the scheduling problem.
But they found ILP solvers couldn't scale to the problem sizes they needed.
In fact, Tambe and his other students found the same scaling problems
even staying within the setting of patrol scheduling for counterterrorism.
Both Xu's and Tambe's work branches off to their novel approaches
from the starting obstacle of needing to solve impractically large ILPs.
And in both cases, they have some manner of decomposing the problem
into sub problems,
with a lot of extra work to analyze that the results still produce an optimal solution
(otherwise it's hard to publish, I'm sure).
All that is far from the hardest part of applying math
to wildlife conservation, but it supports my claim that you can't treat NP-hard problems as if they were solved, even in practice and even on "real world" instances.
                    
                

                

            