Modified version of QPBO algorithm by Vladimir Kolmogorov for very large graphs. Original source code availbable at http://pub.ist.ac.at/~vnk/software.html.
Implements algorithms for minimizing functions of binary variables with unary and pairwise terms based on roof duality described in the following papers:
- Roof duality, complementation and persistency in quadratic 0-1 optimization.
P. L. Hammer, P. Hansen, and B. Simeone.
Mathematical Programming, 28:121-155, 1984.
- Network flows and minimization of quadratic pseudo-Boolean functions.
E. Boros, P. L. Hammer, and X. Sun.
Technical Report RRR 17-1991, RUTCOR Research Report, May 1991.
- Preprocessing of Unconstrained Quadratic Binary Optimization.
E. Boros, P. L. Hammer, and G. Tavares.
Technical Report RRR 10-2006, RUTCOR Research Report, April 2006.
- Optimizing binary MRFs via extended roof duality.
C. Rother, V. Kolmogorov, V. Lempitsky, and M. Szummer.
CVPR 2007.
Changed to allow for very large graphs with up to 2.1 billion nodes and "any number" of edges/terms.
Main changes include:
- Changed edge variables to
long long. - Changed a few other variables to
long long. - Reduced
sizeof(Node)by changing some variable types in thestruct.