The basic algorithm for pseudo-Boolean programming revisited

[en] 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 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.

Disciplines :

Quantitative methods in economics & management
Mathematics

Author, co-author :

Crama, Yves ; Université de Liège - ULiège > HEC Liège : UER > Recherche opérationnelle et gestion de la production

Hansen, Pierre

Jaumard, Brigitte

Language :

English

Title :

The basic algorithm for pseudo-Boolean programming revisited

Publication date :

1990

Journal title :

Discrete Applied Mathematics

ISSN :

0166-218X

eISSN :

1872-6771

Publisher :

Elsevier Science, Amsterdam, Netherlands

Volume :

Pages :

171-185

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 23 December 2017

Statistics

Number of views

52 (3 by ULiège)

Number of downloads

178 (2 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

Arnborg Efficient algorithms for combinatorial problems on graphs with bounded decomposability, A survey , BIT; 1985, 25:2-23.
Arnborg, Corneil, Proskurowski (1987) Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic Discrete Methods 8:277-284.
Arnborg, Proskurowski (1989) Linear time algorithms for NP-hard problems restricted to partial k-trees. Discrete Appl. Math. 23:11-24.
Balas, Mazzola (1984) Nonlinear 0–1 programming: I. Linearization techniques. Math. Programming 30:1-21.
Balas, Mazzola (1984) Nonlinear 0–1 programming: II. Dominance relations and algorithms. Math. Programming 30:22-45.
Barahona (1986) A solvable case of quadratic 0–1 programming. Discrete Appl. Math. 13:23-26.
Bondy, Murty Graph Theory with Applications, Elsevier, New York; 1976.
Georgakopoulos, Kavvadias, Papadimitriou (1988) Probabilistic satisfiability. J. Complexity 4:1-11.
Granot, Granot (1980) Generalized covering relaxation for 0–1 programs. Operations Research 28:1442-1449.
Hammer, Rosenberg, Rudeanu (1963) On the determination of the minima of pseudo-Boolean functions. Stud. Cerc. Mat. , (Ivǎnescu), (in Romanian); 14:359-364.
Hammer, Rosenberg, Rudeanu (1963) Application of discrete linear programming to the minimization of Boolean functions. Rev. Math. Pures Appl. , (Ivǎnescu), (in Russian); 8:459-475.
Hammer, Rudeanu Boolean Methods in Operations Research and Related Areas, Springer, New York; 1968.
Hansen (1974) Programmes mathématiques en variables 0–1. Thése d'aggrégation, Université Libre de Bruxelles, Bruxelles; .
Hansen (1975) Les procédures d'optimisation et d'exploitation par séparation et évaluation. Combinatorial Programming , B. Roy, Reidel, Dordrecht; 19-65.
Hansen, Simeone (1986) Unimodular functions. Discrete Appl. Math. 14:269-281.
Knuth (1975) The Art of Computer Programming. Sorting and Searching , 2nd ed., Addison-Wesley, Reading, MA; 3.
Lawler, Bell (1966) A method for solving discrete optimization problems. Operations Research 14:1098-1112.
Mao, Wallingford (1968) An extension of Lawler and Bell's method of discrete optimization with examples from capital budgeting. Management Science 15:51-60.
Robertson, Seymour (1986) Graph minors: II. Algorithmic aspect of tree-width. J. Algorithms 7:309-322.
Taha (1972) A Balasian-based algorithm for zero-one polynomial programming. Management Science 18 B:328-343.
Taha (1972) Further improvements in the polynomial zero-one algorithm. Management Science 19:226-227.