The basic algorithm for pseudo-Boolean programming revisited

AbstractThe 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 has linear-time complexity when applied to functions associated in a natural way with graphs of bounded tree-width. We also propose a new approach to the elimination of a variable based on a branch-and-bound scheme, which allows shortcuts in Boolean manipulations. Computational results are reported on