×

Global optimality conditions and optimization methods for quadratic integer programming problems. (English) Zbl 1247.90199

This paper establishes some sufficient and some necessary global optimality conditions for quadratic integer programming problems. The results given in this work extend results presented in [A. Beck and M. Teboulle, SIAM J. Optim. 11, No. 1, 179–188 (2000; Zbl 0990.90089)]; [W. Chen and L. Zhang, J. Glob. Optim. 46, No. 2, 191–206 (2010; Zbl 1209.90292)] and [V. Jeyakumar, A. M. Rubinov and Z.Y. Wu, Math. Program. 110, No. 3, 521–541 (2007; Zbl 1206.90178)]. The authors develop a new local optimization method by exploiting the obtained necessary global optimality condition and propose a new global optimization method by combining the sufficient global optimality condition, the local optimization method and an auxiliary function. Some numerical examples are provided to illustrate the performance of both optimization methods.

MSC:

90C10 Integer programming
90C20 Quadratic programming
90C46 Optimality conditions and duality in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alperin H., Nowak I.: Lagrangian smothing heuristics for max-cut. J. Heuristics 11, 447–463 (2005) · Zbl 1122.90426
[2] Beck A., Teboulle M.: Global optimality conditions for quadratic optimization problems with binary constraints. SIAM J. Optim. 11, 179–188 (2000) · Zbl 0990.90089
[3] Bertsimas D., Ye Y.: Semidefinite relaxations, multivariate normal distributions, and order statistics. In: Du, D.Z., Pardalos, P. (eds) Handbook of Combinatorial Optimization, pp. 1–7. Kluwer Academic Publishers, Dordrecht (1998) · Zbl 1052.90594
[4] Borosa E., Hammera P.L., Sunb R., Tavares G.: A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO). Discret. Optim. 5, 501–529 (2008) · Zbl 1170.90454
[5] Burer S., Monreiro R.D.C., Zhang Y.: Rank-two relaxation heuristics for max-cut and other binary quadratic programs. SIAM J. Optim. 12, 503–521 (2001) · Zbl 1152.90532
[6] Chen W., Zhang L.S.: Global optimality conditions for quadratic 0-1 optimization problems. J Glob Optim 46(2), 191–206 (2009) · Zbl 1209.90292
[7] Erenguc S.S., Benson H.P.: An algorithm for indefinite integer quadratic programming. Comput. Math. Appl. 21, 99–106 (1991) · Zbl 0721.90056
[8] Forrester R.J., Greenberg H.J.: Quadratic binary programming models in computational biology. Algorithm. Oper. Res. 3, 110–129 (2008) · Zbl 1277.90085
[9] Frieda G., Jadranka S.K.: On simultaneous approximation in quadratic integer programming. Oper. Res. Lett. 8, 251–255 (1989)
[10] Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco, CA (1979) · Zbl 0411.68039
[11] Goemans M.X., Williamson D.P.: Improved approximation algorithms for maximum cut ans satisfiability problems using semidefinite programming. J. ACM 42, 1115–1145 (1995) · Zbl 0885.68088
[12] Halikias G.D., Jaimoukha I.M., Malik U., Gungah S.K.: New bounds on the unconstrained quadratic integer programming problem. J. Glob. Optim. 39, 543–554 (2007) · Zbl 1146.90041
[13] Huang H.X., Pardalos P., Prokopyev O.A.: Lower bound improvement and forcing rule for quadratic binary programming. Comput. Optim. Appl. 33, 187–208 (2006) · Zbl 1111.90081
[14] Hua Z.S., Zhang B., Xu X.Y.: A new variable reduction technique for convex integer quadratic programs. Appl. Math. Model. 32, 224–231 (2008) · Zbl 1187.90211
[15] Iasemidis L.D., Pardalos P.M., Sackellares J.C., Shian D.S.: Quadratic binary programming and dynamical system approach to determine the predictability of epileptic seizures. J. Comb. Optim. 5, 9–26 (2001) · Zbl 1050.92031
[16] Jeyakumar V., Rubinov A.M., Wu Z.Y.: Global optimality conditions for non-convex quadratic minimization problems with quadratic constraints. Math. Program. Ser. A 110, 521–541 (2007) · Zbl 1206.90178
[17] Malik U., Jaimoukha I.M., Halikias G.D., Gungah S.K.: On the gap between the quadratic integer programming problem and its semidefinite relaxation. Math. Program. Ser. A 107, 505–515 (2006) · Zbl 1111.90076
[18] Mohamed D.: An enumerative algorithm framework for a class of nonlinear integer programming problems. Eur. J. Oper. Res. 101, 104–121 (1997) · Zbl 0929.90057
[19] Pardalos P.M., Rodgers G.P.: Computational aspects of branch and bound algorithm for quadratic zero-one programming. Computing 45, 131–144 (1990) · Zbl 0721.65034
[20] Prokopyev O.A., Kong N., Martinez-Torres D.L.: The equitable dispersion problem. Eur. J. Oper. Res. 197, 59–67 (2009) · Zbl 1157.90539
[21] Renu G., Bandopadhyaya L., Puri M.C.: Ranking in quadratic integer programming problems. Eur. J. Oper. Res. 95, 231–236 (1996) · Zbl 0953.90560
[22] Rubinov A.M.: Abstract Convexity and Global Optimization. Kluwer, Dordrecht (2000) · Zbl 0985.90074
[23] Shor N.Z.: On a bounding method for quadratic extremal problems with 0–1 variables. Kibernetika 2, 48–50 (1985)
[24] Thoai N.V.: Global optimization techniques for solving the general quadratic integer programming problem. Comput. Optim. Appl. 10, 149–163 (1998) · Zbl 0896.90150
[25] Vassilev V., Genova K.: An approximate algorithm for nonlinear integer programming. Eur. J. Oper. Res. 74, 170–178 (1994) · Zbl 0803.90094
[26] Wu Z.Y., Yang Y.J., Bai F.S.: A filled function method for quadratic problems with binary constraints. Optimization 58(5), 1–14 (2009) · Zbl 1158.92312
[27] Zhu W.X.: A provable better Branch and Bound method for a nonconvex integer quadratic programming problem. J. Comput. Syst. Sci. 70, 107–117 (2005) · Zbl 1079.90167
[28] Zwick, U.: Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems. In: Proceeding of 31th STOC, pp. 676–687 (1999) · Zbl 1345.90064
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.