The basic algorithm for pseudo-Boolean programming revisited (Q2277139): Difference between revisions

A pseudo-Boolean function is a real-valued function of 0-1 variables, which can be expressed (nonuniquely) as a polynomial in its variables and their complements. The basic algorithm for pseudo-Boolean programming due to \textit{P. L. Hammer} and \textit{S. Rudeanu} [see their book ``Boolean methods in Operations Research and related areas'' (1968; Zbl 0155.280)] recursively eliminates variables so that at each iteration a function is produced depending on one variable less, but having the same optimal value as the previous one. In this paper it is shown that the basic algorithm has linear-time complexity when applied to function associated in a natural way with graphs of bounded tree-width. A new approach to the elimination of a variable based on a branch-and-bound scheme is also proposed, which allows shortcuts in Boolean manipulations. The paper is concluded by some computational results obtained with a FORTRAN 77 program for problems with up to 200 variables.