We consider combinatorial problems that can be formulated as
minimization of a partially separable function of discrete variables
including such problems as vertex packing, pseudo-Boolean
optimization, 0-1 polynomial programming, weighted constraint
satisfaction and energy minimization in graphical models. While these
problems are generally NP-hard, an interesting possibility is to try
to identify a part of an optimal solution in polynomial time.
Specifically, using sufficient conditions based on the linear
programming relaxation. We pose the problem to find the largest part
of the solution identifiable in this way, called the maximum
persistency problem. The method generalizes many previously proposed
sufficient conditions in computer vision, bioinformatics and discrete
optimization and is guaranteed to find same or larger part of the
optimal solution in a number of cases.
A big practical obstacle however was the necessity to solve
large-scale linear programs exactly. In this work we propose an
algorithm that can utilise suboptimal solvers to the LP relaxation or
its dual, such as practically efficient TRW-S algorithm. The method
still provides global optimality guarantees for the determined part of
the solution compromising only a bit on the maximality but running
significantly faster (tens of seconds versus hours).
The method is of interest when the exact solution to the discrete
optimisation problem needs to be found (e.g. for distinguishing the
errors of the model from that of optimisation or during learning).