  One powerful technique to solve NP-hard optimization problems in practice is
branch-and-reduce search---which is branch-and-bound that intermixes branching
with reductions to decrease the input size. While this technique is known to be
very effective in practice for unweighted problems, very little is known for
weighted problems, in part due to a lack of known effective reductions. In this
work, we develop a full suite of new reductions for the maximum weight
independent set problem and provide extensive experiments to show their
effectiveness in practice on real-world graphs of up to millions of vertices
and edges.
  Our experiments indicate that our approach is able to outperform existing
state-of-the-art algorithms, solving many instances that were previously
infeasible. In particular, we show that branch-and-reduce is able to solve a
large number of instances up to two orders of magnitude faster than existing
(inexact) local search algorithms---and is able to solve the majority of
instances within 15 minutes. For those instances remaining infeasible, we show
that combining kernelization with local search produces higher-quality
solutions than local search alone.
