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 条

[1] Finding independent sets in a graph using continuous multivariable polynomial formulations [J].

Abello, J ;

Butenko, S ;

Pardalos, PM ;

Resende, MGC .

JOURNAL OF GLOBAL OPTIMIZATION, 2001, 21 (02) :111-137

[2] A TIGHT LINEARIZATION AND AN ALGORITHM FOR ZERO-ONE QUADRATIC-PROGRAMMING PROBLEMS [J].

ADAMS, WP ;

SHERALI, HD .

MANAGEMENT SCIENCE, 1986, 32 (10) :1274-1290

[3] A branch and bound method via dc optimization algorithms and ellipsoidal technique for box constrained nonconvex quadratic problems [J].

An, LTH ;

Tao, PD .

JOURNAL OF GLOBAL OPTIMIZATION, 1998, 13 (02) :171-206

[4] EXPERIMENTS IN QUADRATIC 0-1 PROGRAMMING [J].

BARAHONA, F ;

JUNGER, M ;

REINELT, G .

MATHEMATICAL PROGRAMMING, 1989, 44 (02) :127-137

[5]

Beasley E., 1998, Heuristic algorithms for the unconstrained binary quadratic programming problem

[6]

Beasley J.E., 1990, OR-Library

[7] Global optimality conditions for quadratic optimization problems with binary constraints [J].

Beck, A ;

Teboulle, M .

SIAM JOURNAL ON OPTIMIZATION, 2000, 11 (01) :179-188

[8] MINIMIZATION OF A QUADRATIC PSEUDO-BOOLEAN FUNCTION [J].

BILLIONNET, A ;

SUTTER, A .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1994, 78 (01) :106-115

[9]

Billionnet A., 2005, 856 CEDRIC

[10] Using a mixed integer quadratic programming solver for the unconstrained quadratic 0-1 problem [J].

Billionnet, Alain ;

Elloumi, Sourour .

MATHEMATICAL PROGRAMMING, 2007, 109 (01) :55-68

← 1 2 3 4 5 6 →