MINIMIZATION OF A QUADRATIC PSEUDO-BOOLEAN FUNCTION

被引：31
作者：
BILLIONNET, A [1 ]
SUTTER, A [1 ]
机构：
[1] FRANCE TELECOM,CTR NATL ETUD TELECOMMUN,F-92131 ISSY MOULINEAUX,FRANCE
来源：
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH | 1994年 / 78卷 / 01期
关键词：
ZERO-ONE QUADRATIC PROGRAMMING; BRANCH AND BOUND; COMPUTATION; LOWER BOUND; MAXIMUM SATISFIABILITY; STABILITY NUMBER;
D O I：
10.1016/0377-2217(94)90125-2
中图分类号：
C93 [管理学];
学科分类号：
12 ; 1201 ; 1202 ; 120202 ;
摘要：
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, P 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.
引用
收藏
页码：106 / 115
页数：10
相关论文
共 31 条
  • [11] Harmonic analysis and Boolean function complexity
    Bernasconi A.
    CALCOLO, 1998, 35 (3) : 149 - 186
  • [12] A lower bound for a constrained quadratic 0-1 minimization problem
    Billionnet, A
    Faye, A
    DISCRETE APPLIED MATHEMATICS, 1997, 74 (02) : 135 - 146
  • [13] Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem
    Hansen, Pierre
    Meyer, Christophe
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (06) : 1267 - 1290
  • [14] A fast quantum algorithm for the affine Boolean function identification
    Younes, Ahmed
    EUROPEAN PHYSICAL JOURNAL PLUS, 2015, 130 (02):
  • [15] An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints
    An L.T.H.
    Mathematical Programming, 2000, 87 (3) : 401 - 426
  • [16] An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints
    An, LTH
    MATHEMATICAL PROGRAMMING, 2000, 87 (03) : 401 - 426
  • [17] Improved Lower Bounds for Submodular Function Minimization
    Chakrabarty, Deeparnab
    Graur, Andrei
    Jiang, Haotian
    Sidford, Aaron
    2022 IEEE 63RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2022, : 245 - 254
  • [18] Exploring Target Function Approximation for Stochastic Circuit Minimization
    Wang, Chen
    Xiao, Weihua
    Hayes, John P.
    Qian, Weikang
    2020 IEEE/ACM INTERNATIONAL CONFERENCE ON COMPUTER AIDED-DESIGN (ICCAD), 2020,
  • [19] On globally solving linearly constrained indefinite quadratic minimization problems by decomposition branch and bound method
    Phong, TQ
    An, LTH
    Tao, PD
    RAIRO-RECHERCHE OPERATIONNELLE-OPERATIONS RESEARCH, 1996, 30 (01): : 31 - 49
  • [20] DECOMPOSITION BRANCH-AND-BOUND METHOD FOR GLOBALLY SOLVING LINEARLY CONSTRAINED INDEFINITE QUADRATIC MINIMIZATION PROBLEMS
    PHONG, TQ
    AN, LTH
    TAO, PD
    OPERATIONS RESEARCH LETTERS, 1995, 17 (05) : 215 - 220
1234