An exact solution method for unconstrained quadratic 0-1 programming: a geometric approach

被引：15

作者：

Li, D. ^{[1
]}

Sun, X. L. ^{[2
]}

Liu, C. L. ^{[3
]}

机构：

[1] Chinese Univ Hong Kong, Dept Syst Engn & Engn Management, Shatin, Hong Kong, Peoples R China

[2] Fudan Univ, Sch Management, Dept Management Sci, Shanghai 200433, Peoples R China

[3] Shanghai Univ Finance & Econ, Dept Appl Math, Shanghai 200433, Peoples R China

来源：

JOURNAL OF GLOBAL OPTIMIZATION | 2012年 / 52卷 / 04期

基金：

中国国家自然科学基金;

关键词：

Quadratic; 0-1; programming; Nonlinear integer programming; Optimality condition; Lower bounds; Variable fixation; Branch-and-bound method; BOUND ALGORITHM; BOX CONSTRAINTS; MAXIMUM CUT; OPTIMIZATION; BRANCH; SEMIDEFINITE; FORMULATION; REDUCTION;

D O I：

10.1007/s10898-011-9713-2

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We explore in this paper certain rich geometric properties hidden behind quadratic 0-1 programming. Especially, we derive new lower bounding methods and variable fixation techniques for quadratic 0-1 optimization problems by investigating geometric features of the ellipse contour of a (perturbed) convex quadratic function. These findings further lead to some new optimality conditions for quadratic 0-1 programming. Integrating these novel solution schemes into a proposed solution algorithm of a branch-and-bound type, we obtain promising preliminary computational results.

引用

页码：797 / 829

页数：33

共 53 条

[21] CONVERTING 0-1 POLYNOMIAL PROGRAMMING PROBLEM TO A 0-1 LINEAR PROGRAM [J].

GLOVER, F ;

WOOLSEY, E .

OPERATIONS RESEARCH, 1974, 22 (01) :180-182

[22] FURTHER REDUCTION OF ZERO-ONE POLYNOMIAL PROGRAMMING PROBLEMS TO ZERO-ONE LINEAR PROGRAMMING PROBLEMS [J].

GLOVER, F ;

WOOLSEY, E .

OPERATIONS RESEARCH, 1973, 21 (01) :156-161

[23] Adaptive memory tabu search for binary quadratic programs [J].

Glover, F ;

Kochenberger, GA ;

Alidaee, B .

MANAGEMENT SCIENCE, 1998, 44 (03) :336-345

[24] Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming [J].

Goemans, MX ;

Williamson, DP .

JOURNAL OF THE ACM, 1995, 42 (06) :1115-1145

[25] UNCONSTRAINED QUADRATIC BIVALENT PROGRAMMING PROBLEM [J].

GULATI, VP ;

GUPTA, SK ;

MITTAL, AK .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1984, 15 (01) :121-125

[26] ROOF DUALITY, COMPLEMENTATION AND PERSISTENCY IN QUADRATIC 0-1 OPTIMIZATION [J].

HAMMER, PL ;

HANSEN, P ;

SIMEONE, B .

MATHEMATICAL PROGRAMMING, 1984, 28 (02) :121-155

[27]

Hammer PL, 1968, OKONOMETRIE UNTERNEH

[28]

Hansen P., 1993, ORSA Journal on Computing, V5, P97, DOI 10.1287/ijoc.5.2.97

[29]

HANSEN P, 2000, G200059 GERAD

[30] Solving quadratic (0,1)-problems by semidefinite programs and cutting planes [J].

Helmberg, C ;

Rendl, F .

MATHEMATICAL PROGRAMMING, 1998, 82 (03) :291-315

← 1 2 3 4 5 6 →