Global optimality conditions and optimization methods for quadratic integer programming problems

被引：0
作者：
Z. Y. Wu
G. Q. Li
J. Quan
机构：
[1] University of Ballarat,School of Information Technology and Mathematical Sciences
[2] Shanghai University,Department of Mathematics
来源：
Journal of Global Optimization | 2011年 / 51卷
关键词：
Global optimality conditions; Quadratic integer programming problem; Optimization method; Auxiliary function; 41A65; 41A29; 90C30;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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
页数：19
相关论文
共 59 条
  • [1] Alperin H.(2005)Lagrangian smothing heuristics for max-cut J. Heuristics 11 447-463
  • [2] Nowak I.(2000)Global optimality conditions for quadratic optimization problems with binary constraints SIAM J. Optim. 11 179-188
  • [3] Beck A.(2008)A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO) Discret. Optim. 5 501-529
  • [4] Teboulle M.(2001)Rank-two relaxation heuristics for max-cut and other binary quadratic programs SIAM J. Optim. 12 503-521
  • [5] Borosa E.(2009)Global optimality conditions for quadratic 0-1 optimization problems J Glob Optim 46 191-206
  • [6] Hammera P.L.(1991)An algorithm for indefinite integer quadratic programming Comput. Math. Appl. 21 99-106
  • [7] Sunb R.(2008)Quadratic binary programming models in computational biology Algorithm. Oper. Res. 3 110-129
  • [8] Tavares G.(1989)On simultaneous approximation in quadratic integer programming Oper. Res. Lett. 8 251-255
  • [9] Burer S.(1995)Improved approximation algorithms for maximum cut ans satisfiability problems using semidefinite programming J. ACM 42 1115-1145
  • [10] Monreiro R.D.C.(2007)New bounds on the unconstrained quadratic integer programming problem J. Glob. Optim. 39 543-554
123456