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 条
[31]   Lower bound improvement and forcing rule for quadratic binary programming [J].
Huang, HX ;
Pardalos, PM ;
Prokopyev, OA .
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2006, 33 (2-3) :187-208
[32]   Quadratic binary programming and dynamical system approach to determine the predictability of epileptic seizures [J].
Iasemidis, LD ;
Pardalos, P ;
Sackellares, JC ;
Shiau, DS .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2001, 5 (01) :9-26
[33]  
KALANTARI B, 1990, NAV RES LOG, V37, P527, DOI 10.1002/1520-6750(199008)37:4<527::AID-NAV3220370407>3.0.CO
[34]  
2-P
[35]   MAXIMIZING A CONVEX QUADRATIC FUNCTION OVER A HYPERCUBE [J].
KONNO, H .
JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN, 1980, 23 (02) :171-188
[36]   Convergent Lagrangian and contour cut method for nonlinear integer programming with a quadratic objective function [J].
Li, D. ;
Sun, X. L. ;
Wang, F. L. .
SIAM JOURNAL ON OPTIMIZATION, 2006, 17 (02) :372-400
[37]   Optimal lot solution to cardinality constrained mean-variance formulation for portfolio selection [J].
Li, D ;
Sun, XL ;
Wang, J .
MATHEMATICAL FINANCE, 2006, 16 (01) :83-101
[38]  
Li D., 2006, Nonlinear Integer Programming
[39]  
Liu W, 2005, HCES0905 U MISS
[40]  
LU SH, 1984, EUR J OPER RES, V15, P110, DOI 10.1016/0377-2217(84)90054-7
123456