Group for Research in Decision Analysis

G-88-35

The Basic Algorithm for Pseudo-Boolean Programming Revisited

, , and

The Basic Algorithm of pseudo-Boolean programming due to Hammer and Rudeanu allows to minimize nonlinear 0-1 functions by recursively eliminating one variable at each iteration. We show it solves in linear time problems whose objective functions are associated with k-trees. Moreover, we propose some shortcuts in boolean manipulations. Computational experiences are discussed.

, 22 pages