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

69 (3 by ULiège)

Number of downloads

198 (2 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

See more details

publications

supporting

mentioning

contrasting

Smart Citations

Citing PublicationsSupportingMentioningContrasting

View Citations

See how this article has been cited at scite.ai

scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.

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.

Similar publications

Sorry the service is unavailable at the moment. Please try again later.

Name	Provider / Domaine	Expiration	Description
JSESSIONID	Oracle Corporation www.uliege.be	Session	General purpose platform session cookie, used by sites written in JSP. Usually used to maintain an anonymous user session by the server.
CookieScriptConsent	CookieScript .uliege.be	1 year	This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.

Name	Provider / Domaine	Expiration	Description
_pk_id	InnoCraft Ltd .uliege.be	1 year	Used to store a few details about the user such as the unique visitor ID
_pk_ses	InnoCraft Ltd .uliege.be	30 minutes	Short lived cookies used to temporarily store data for the visit
_pk_ref	InnoCraft Ltd .uliege.be	6 months	Used to store the attribution information, the referrer initially used to visit the website