UPPER-BOUNDS FOR QUADRATIC 0-1 MAXIMIZATION

被引：22

作者：

BOROS, E ^{[1
]}

CRAMA, Y ^{[1
]}

HAMMER, PL ^{[1
]}

机构：

[1] STATE UNIV LIMBURG,DEPT QUANTITAT,6200 MD MAASTRICHT,NETHERLANDS

来源：

OPERATIONS RESEARCH LETTERS | 1990年 / 9卷 / 02期

基金：

美国国家科学基金会;

关键词：

pseudo-Boolean programming; quadratic; 0-1; maximization;

D O I：

10.1016/0167-6377(90)90044-6

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, three different approaches are generalised to obtain upper bounds for the maximum of a quadratic pseudo-Boolean function f over [0,1]n. The original approaches (complementation, majorization and linearization) were introduced by Hammer, Hansen and Simeone [9]. The generalization in this paper yields three upper bounds, Ck, Mk and Lk for each integer k ≥ 2, where Cn = Ln = Mn is the maximum of f, and C2 = L2 = M2 is the roof duality bound studied in [9]. It is proved that Ck = Mk = Lk for all values of k. © 1990.

引用

页码：73 / 79

页数：7

共 13 条

[1] ADAMS WP, 1988, URI061 CLEMS U TECHN
[2] NONLINEAR 0-1 PROGRAMMING .1. LINEARIZATION TECHNIQUES
BALAS, E
MAZZOLA, JB
[J]. MATHEMATICAL PROGRAMMING, 1984, 30 (01) : 1 - 21
[3] BALAS E, 1984, MATH PROGRAM, V30, P22, DOI 10.1007/BF02591797
[4] BOROS E, 1989, UNPUB CHVATAL CUTS O
[5] BOURJOLLY JM, 1988, UNPUB COMBINATORIAL
[6] CRAMA Y, 1988, RUTCOR3288 RUTG U RE
[7] DESIMONE C, 1988, RUTCOR5388 RUTG U RE
[8] Garey M.R., 1979, COMPUTERS INTRACTABI, V174
[9] ROOF DUALITY, COMPLEMENTATION AND PERSISTENCY IN QUADRATIC 0-1 OPTIMIZATION
HAMMER, PL
HANSEN, P
SIMEONE, B
[J]. MATHEMATICAL PROGRAMMING, 1984, 28 (02) : 121 - 155
[10] Hansen P., 1979, Discrete Optimisation, P53

← 1 2 →