Global optimality conditions and optimization methods for quadratic integer programming problems

被引：7

作者：

Wu, Z. Y. ^{[1
]}

Li, G. Q. ^{[2
]}

Quan, J. ^{[2
]}

机构：

[1] Univ Ballarat, Sch Informat Technol & Math Sci, Ballarat, Vic 3353, Australia

[2] Shanghai Univ, Dept Math, Shanghai 200444, Peoples R China

来源：

JOURNAL OF GLOBAL OPTIMIZATION | 2011年 / 51卷 / 03期

基金：

中国国家自然科学基金;

关键词：

Global optimality conditions; Quadratic integer programming problem; Optimization method; Auxiliary function; ALGORITHM; HEURISTICS; BOUNDS; CUT;

D O I：

10.1007/s10898-011-9650-0

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this paper, we first establish some sufficient and some necessary global optimality conditions for quadratic integer programming problems. Then we present a new local optimization method for quadratic integer programming problems according to its necessary global optimality conditions. A new global optimization method is proposed by combining its sufficient global optimality conditions, local optimization method and an auxiliary function. The numerical examples are also presented to show that the proposed optimization methods for quadratic integer programming problems are very efficient and stable.

引用

页码：549 / 568

页数：20

共 28 条

[1] Lagrangian smoothing heuristics for Max-Cut [J].

Alperin, H ;

Nowak, I .

JOURNAL OF HEURISTICS, 2005, 11 (5-6) :447-463

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

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

Beck, A ;

Teboulle, M .

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

[4]

Bertsimas D., 1998, HDB COMBINATORIAL OP, P1

[5] A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO) [J].

Boros, Endre ;

Hammer, Peter L. ;

Sun, Richard ;

Tavares, Gabriel .

DISCRETE OPTIMIZATION, 2008, 5 (02) :501-529

[6] Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs [J].

Burer, S ;

Monteiro, RDC ;

Zhang, Y .

SIAM JOURNAL ON OPTIMIZATION, 2001, 12 (02) :503-521

[7] Global optimality conditions for quadratic 0-1 optimization problems [J].

Chen, Wei ;

Zhang, Liansheng .

JOURNAL OF GLOBAL OPTIMIZATION, 2010, 46 (02) :191-206

[8] AN ALGORITHM FOR INDEFINITE INTEGER QUADRATIC-PROGRAMMING [J].

ERENGUC, SS ;

BENSON, HP .

COMPUTERS & MATHEMATICS WITH APPLICATIONS, 1991, 21 (6-7) :99-106

[9]

Forrester R., 2008, ALGORITHMIC OPERATIO, V3, P110

[10]

FRIEDA G, 1989, OPER RES LETT, V8, P251

← 1 2 3 →