Skip to content

Latest commit

 

History

History
165 lines (128 loc) · 6.56 KB

README.md

File metadata and controls

165 lines (128 loc) · 6.56 KB
Raw

DAOOPT: Distributed AND/OR Optimization

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

Compilation

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.

CMake

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.

Usage

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.

Sequential execution

Simply compile the Worker variant and run it on your problem, no further setup needed.

Distributed execution

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.

Background / References

AND/OR Branch-and-Bound

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.

Distributed AND/OR Branch-and-Bound

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.

Stochastic Greedy Variable Elimination

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.

Join Graph Linear Programming

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.

Acknowledgments

This work has been partially supported by NIH grant 5R01HG004175-03 and NSF grants IIS-0713118 and IIS-1065618.

Known issues

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.

Disclaimer

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! ;-)