SAL Home NUMERICS Optimization


OPBDP is an implementation in C++ of an implicit enumeration algorithm for solving (non)linear 0-1 (or pseudo-Boolean) optimization problems with integer coefficients. The implicit enumeration algorithm can be seen as a generalization of the Davis-Putnam enumeration algorithm for solving propositional satisfiability problems in clausal form to the pseudo-Boolean case.

The package can use different heuristics for selecting the variable on which to split next. It should be fairly easy to write your own variable selection heuristics. Currently, five heuristics are available:

  • no heuristics, i.e. next free variable to 1
  • an adapted two-sided Jeroslow-Wang heuristics (coming from propositional satisfiability problems)
  • one similar to h1; (probably not exceeding double range floating point precision)
  • selects a literal that yields maximal further fixings in the next step
  • randomly selects a literal (rand)

Current Version:   ??

License Type:   Free

Home Site:

Source Code Availability:

Yes (from Home Site)

Available Binary Packages:

  • Debian Package: No
  • RedHat RPM Package: No
  • Other Packages: Yes (from Home Site)

Targeted Platforms:

SunOS, Solaris, Linux

Software/Hardware Requirements:


Other Links:

Mailing Lists/USENET News Groups:


User Comments:

  • None

See A Screen Shot? (Not Yet)

  SAL Home   |   Numerical Analysis   |   Optimization

Comments? SAL@KachinaTech.COM
Copyright © 1995-2001 by Herng-Jeng Jou
Copyright © 1997-2001 by Kachina Technologies, Inc.
All rights reserved.