  In this paper, we propose novel algorithms for inferring the Maximum a
Posteriori (MAP) solution of discrete pairwise random field models under
multiple constraints. We show how this constrained discrete optimization
problem can be formulated as a multi-dimensional parametric mincut problem via
its Lagrangian dual, and prove that our algorithm isolates all constraint
instances for which the problem can be solved exactly. These multiple solutions
enable us to even deal with `soft constraints' (higher order penalty
functions). Moreover, we propose two practical variants of our algorithm to
solve problems with hard constraints. We also show how our method can be
applied to solve various constrained discrete optimization problems such as
submodular minimization and shortest path computation. Experimental evaluation
using the foreground-background image segmentation problem with statistic
constraints reveals that our method is faster and its results are closer to the
ground truth labellings compared with the popular continuous relaxation based
methods.
