A pseudo-Boolean consensus approach to nonlinear 0–1 optimization

It is proved that any pseudo-Boolean function f can be represented as f ( x ) ≡ z + φ ( x , x ̄ ) , where z is the minimum of f and φ is a polynomial with positive coefficients in the original variables x i and in their complements x ̄ i . A non-constructive proof and a constructive one are given. T...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2008-07, Vol.156 (13), p.2449-2458
Main Author: Simeone, Bruno
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Boolean algebra
Calculus of variations and optimal control
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Consensus
Exact sciences and technology
Mathematical analysis
Mathematics
Nonlinear binary optimization
Numerical analysis
Numerical analysis. Scientific computation
Numerical methods in mathematical programming, optimization and calculus of variations
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:It is proved that any pseudo-Boolean function f can be represented as f ( x ) ≡ z + φ ( x , x ̄ ) , where z is the minimum of f and φ is a polynomial with positive coefficients in the original variables x i and in their complements x ̄ i . A non-constructive proof and a constructive one are given. The latter, which is based on a generalization to pseudo-Boolean functions of the well-known Boolean-theoretical operation of consensus, provides a new algorithm for the minimization of pseudo-Boolean functions.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2007.09.021