This post is about reduction methods in pseudo-Boolean optimization and a recent paper to appear at CVPR 2011.
1. Problem formulation
Consider a pseudo-Boolean function where and suppose is represented by a multilinear polynomial of the form
If , one standard method of solving (2) is using roof duality. It gives a lower bound of the optimal value and possibly also a partial assignment of variables.
If , one can always employ reductions to obtain an equivalent quadratic problem with additional variables. One possible reduction is
There are other possibilities, for example,
Different reductions lead to different results. Take for example the following cubic polynomial:
Using the first reduction followed by roof duality, we obtain a lower bound of -3 and no indication on how to assign the three variables. Using the second reduction, we obtain the (tight) lower bound of -2 and the optimal assignment of every variable (which is ).
3. Choosing between reductions
Andrew C. Gallagher, Dhruv Batra and Devi Parikh have a paper at the upcoming CVPR 2011 titled Inference for Order Reduction in Markov Random Fields, in which they try to choose between different possible reductions. They limit themselves to the case and create a labeling problem in which each term of degree 3 is assigned one of many possible reductions. Since it does not seem to be possible to maximize, say, the number of labeled variables in the resulting quadratic problem, they minimize the “non-submodular magnitude”, which is the sum of the positive coefficients of the resulting quadratic polynomial. Solving (2) is then a two-step procedure:
- Solve the labeling problem which assigns each term of degree 3 one of many possible reductions.
- Perform the reductions and solve the resulting quadratic problems using roof duality.
Step 1 is generally a very difficult problem and can therefore only be solved approximately. Also, it is not completely clear that minimizing the “non-submodular magnitude” generally results in more labeled variables or a better lower bound on (2). But the authors perform several experiments which suggests that this approach works quite well.