The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

CAP -- Contig Assembly Program

OPBDP is an implementation in C++ of an implicit enumeration for solving (non)linear 0-1 (or pseudo-Boolen) optimization problems with integer coefficients. A Technical report desribing the techniques used in opbdp is included.

Logic-based methods for modelling and solving combinatorial problems have recently started to play a significant role in both theory and practice. The application of logic to combinatorial problems has a dual aspect. On one hand, constraint logic programming allows one to declaratively model combinatorial problems over an appropriate constraint domain, the problems then being solved by a corresponding constraint solver. Besides being a high-level declarative interface to the constraint solver, the logic programming language allows one also to implement those subproblems that cannot be naturally expressed with constraints. On the other hand, logic-based methods can be used as a constraint solving technique within a constraint solver for combinatorial problems modelled as 0-1 integer programs.

  • Download Files (local site)
  • OPBDP - A Davis-Putnam Based Enumeration Algorithm for Linear Pseudo-Boolea

    Problem Links

    Linear Programming (5)
    Satisfiability (4)

    This page last modified on 2008-07-10 .