Groupe d’études et de recherche en analyse des décisions


The Basic Algorithm for Pseudo-Boolean Programming Revisited

, et

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