An implementation of sequential as well as distributed AND/OR Branch-and-Bound and its Breadth-Rotating AND/OR Branch-and-Bound enhancement for combinatorial optimization problems expressed as MPE (max-product) queries over graphical models like Bayes and Markov networks.
Also implements the following:
- full context-based caching.
- mini-buckets for heuristic generation.
- minfill heuristic to find variable orderings.
- limited discrepancy search to quickly find initial solution.
- stochastic local search to quickly find initial solution (via GLS+ code by Frank Hutter).
- stochastic iterative greedy variable ordering (code by Kalev Kask).
- join graph cost-shifting techniques (MPLP, JGLP, MBE-MM) (code by Alex Ihler).
See references at the bottom for details and algorithm analysis.
By Lars Otten, University of California, Irvine. Main AOBB source code under GPL, included libraries vary -- see LICENSE.txt for details
A recent set of Boost library headers is
required to compile the solver (confirmed to work is version 1.53.0),
either in the system-wide include path or copied/symlinked into
./lib/boost locally. In addition, all solver variants need the Boost
program_options library for linking; the dynamic parallel master also
needs the Boost thread and system library.
The easiest and most universal way of compilation is provided through
the included CMake files. Create a build subfolder and from within
it run cmake ... Afterwards make all starts compilation, while
make edit_cache allows to choose between release and debug compiler
flags, toggle static linking, and select one of the solver variants
(see references below); the default choice is the release-optimized,
dynamically linked, sequential solver.
Worker-- Purely sequential AOBB solver.Static-- Static master mode (also needs worker binaries).Dynamic-- Dynamic master mode (also needs worker binaries).
Some features (such as computing the optimal tuple vs. only its cost)
can be turned on/off by setting the respective preprocessor defines in
include/DEFINES.h.
To see the list of command line parameters, run the solver with the
--help argument. Problem input should be in UAI
format, a simple
text-based format to specify graphical model problems. Gzipped input
is supported.
Simply compile the Worker variant and run it on your problem, no
further setup needed.
DAOOPT assumes the Condor grid environment, the machine that the
master executable runs on needs to be able to submit jobs. The file
daoopt-template.condor from the working directory will be the basis
for the parallel subproblem submissions, it can be used to customize
Condor options. The sequential solver will be used for the parallel
subproblems, so you will also need to compile that first (probably
statically linked) for the appropriate architecture: rename the
sequential solver to daoopt.INTEL for 32 bit Linux hosts and/or
daoopt.X86_64 for 64 bit Linux hosts; placed in the working
directory these will be used automatically.
AND/OR Branch-and-Bound (AOBB) is a search framework developed in Rina Dechter's research group at UC Irvine, most recently enhanced through Breadth-Rotating AND/OR Branch-and-Bound (BRAOBB). Relevant publications:
- Rina Dechter and Robert Mateescu. "AND/OR Search Spaces for Graphical Models". In Artificial Intelligence, Volume 171 (2-3), pages 73-106, 2006.
- Radu Marinescu and Rina Dechter. "AND/OR Branch-and-Bound Search for Combinatorial Optimization in Graphical Models." In Artificial Intelligence, Volume 173 (16-17), pages 1457-1491, 2009.
- Radu Marinescu and Rina Dechter. "Memory Intensive AND/OR Search for Combinatorial Optimization in Graphical Models." In Artificial Intelligence, Volume 173 (16-17), pages 1492-1524, 2009.
- Lars Otten and Rina Dechter. "Anytime AND/OR Depth-first Search for Combinatorial Optimization." In AI Communications, Volume 25 (3), pages 211-227, 2012.
A recent expansion of the AOBB framework to allow using the parallel resources of a computational grid; it is still the focus of ongoing research. Some relevant publications:
- Lars Otten and Rina Dechter. "Towards Parallel Search for Optimization in Graphical Models". In Proceedings of ISAIM'10, Fort Lauderdale, FL, USA, January 2010.
- Lars Otten and Rina Dechter. "Load Balancing for Parallel Branch and Bound". In SofT'10 Workshop and CRAGS'10 Workshop, at CP'10, St. Andrews, Scotland, September 2010.
- Lars Otten and Rina Dechter. "Learning Subproblem Complexities in Distributed Branch and Bound". In DISCML'11 Workshop, at NIPS'11, Granada, Spain, December 2011.
- Lars Otten and Rina Dechter. "A Case Study in Complexity Estimation: Towards Parallel Branch-and-Bound over Graphical Models." In Proceedings of UAI'12, Catalina Island, CA, U.S.A, August 2012.
The solver integrates an enhanced greedy variable ordering algorithm. Relevant publication:
- Kalev Kask, Andrew E. Gelfand, Lars Otten, and Rina Dechter. "Pushing the Power of Stochastic Greedy Ordering Schemes for Inference in Graphical Models" In Proceedings of AAAI 2011, San Francisco, CA, USA, August 2011.
The standard mini-bucket heuristic is much improved with the use of cost-shifting techniques. Some relevant publications:
- Natalia Flerova, Alexander Ihler, Rina Dechter, and Lars Otten. "Mini-bucket Elimination with Moment Matching" in DISCML 2011 Workshop, at NIPS 2011, Granada, Spain, December 2011.
- Alexander Ihler, Natalia Flerova, Rina Dechter, and Lars Otten. "Join-graph based cost-shifting schemes" In Proceedings of UAI 2012, Catalina Island, CA, USA, August 2012.
This work has been partially supported by NIH grant 5R01HG004175-03 and NSF grants IIS-0713118 and IIS-1065618.
Solutions may not be reported correctly when using the --rotate option. For a workaround, disable tuple generation by definining the NO_ASSIGNMENT flag in include/DEFINES.h.
This code was written for research purposes and does therefore not strictly adhere to established coding practices and guidelines. View and use at your own risk! ;-)