Graphical models are a powerful representation framework for automated reasoning tasks. These models use graphs to capture
conditional independencies between variables, allowing for a concise representation of the knowledge. Optimization tasks defined
within this framework are typically tackled with either search or inference. Search methods are time exponential in the number of variables and can operate in linear space. Inference algorithms are
time and space exponential in the tree width of the problem. This potentially higher space complexity makes these methods impractical.
The AND/OR search space for graphical models is a newly introduced framework for search that is sensitive to the independencies
in the model, often resulting in exponentially reduced complexities. The AND/OR search is based on a pseudo-tree which expresses
independencies between variables, resulting in a search tree exponential in the depth of the pseudo-tree, rather than the
number of variables.
The AND/OR Branch-and-Bound algorithm (AOBB) is a new search method that explores the AND/OR search tree for solving optimization
tasks in graphical models. In this paper we extend the algorithm for solving combinatorial optimization problems from the
class of Mixed Integer Linear Programs (MILP). A MILP instance is a linear program where some of the decision variables are
constrained to have only integer values at the optimal solution (we consider only binary integer variables). AOBB can be readily
adapted for solving this class of optimization problems by arranging the integer variables into a start pseudo-tree and, then,
traversing the corresponding AND/OR search tree. This rather straightforward extension can be further improved. We introduce
a dynamic version of AOBB which uses a recursive decomposition of the problem, based on hypergraph separators. The hypergraph of a
MILP instance has a vertex for each constraint and a hyperedge, which corresponds to a variable, connects all the constraints
that contain that variable. A separator translates into a subset of variables that, when instantiated, decompose the problem
into independent components. The algorithm traverses an AND/OR search tree based on a pseudo-tree which is recomputed dynamically
at each search tree node using the hypergraph separator of the respective subproblem. The search process is guided in both
cases by lower-bounding heuristic estimates computed at each node by solving the linear relaxation (i.e. ignoring the integrality
restrictions) of the subproblem rooted at that node. Preliminary evaluation of the structural properties of several hard problem
instances from the MIPLIB2003 library showed promise that the new AND/OR search schemes can improve significantly over the
traditional OR tree search approach. Finally, we mention that more advanced strategies developed in the recent years for integer
programming, such as the branch-and-cut scheme, can be readily adapted to exploit the AND/OR structural paradigm.