Minimization of a quadratic pseudo-Boolean function

Minimization of a quadratic pseudo-Boolean function

0.00 Avg rating0 Votes
Article ID: iaor1998960
Country: Netherlands
Volume: 78
Issue: 1
Start Page Number: 106
End Page Number: 115
Publication Date: Oct 1994
Journal: European Journal of Operational Research
Authors: ,
Abstract:

We present a branch and bound algorithm for minimizing a quadratic pseudo-Boolean function f(x). At each node of the search tree the lower bound is computed in three phases and is equal to b1 + b2 + b3. Computation of b1 is based upon roof duality, b2 uses the characterization of some positive quadratic posiforms associated with the directed cycles of the implication graph of Aspvall, Plass and Tarjan and b3 is computed by searching in a posiform of degree 4 some subfunctions which cannot be equal to zero. These subfunctions are found by using the notion of implication between literals. Computational results on several hundred test problems with up to 100 variables demonstrate the efficiency of this lower bound.

Reviews

Required fields are marked *. Your email address will not be published.