A new branch and bound algorithm for integer quadratic programming problems

Volume 9, Issue 3, pp 1153--1164 http://dx.doi.org/10.22436/jnsa.009.03.42

Download PDF

Download XML

• Export citations
  • CITATIONS & REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • ARTICLE CITATION
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)
  • REFERENCES
  • EndNote (.ENW)
  • Mendeley, JabRef (.BIB)
  • Papers, Zotero, Reference Manager, RefWorks (.RIS)

• 1395 Downloads
• 2612 Views

Authors

Xiaohua Ma - Institute of Information and System Sciences, Beifang University for Nationalities, Yinchuan, 750021, China. Yuelin Gao - Institute of Information and System Sciences, Beifang University for Nationalities, Yinchuan, 750021, China. Xia Liu - Institute of Information and System Sciences, Beifang University for Nationalities, Yinchuan, 750021, China.

Abstract

For integer quadratic programming problems, a new branch and bound algorithm is proposed in this paper through a series of improvements on the traditional branch and bound algorithm, which can be used to solve integer quadratic programming problems effectively and efficiently. This algorithm employs a new linear relaxation and bound method and a rectangular deep bisection method. At the same time, a rectangular reduction strategy is used to improve the approximation degree and speed up the convergence of the algorithm. Numerical results show that the proposed algorithm is feasible and effective and has improved the existing relevant branch and bound algorithms.

Share and Cite

Keywords

• Integer quadratic programming
• branch and bound
• linear relaxation
• rectangular deep bisection
• rectangular reduction.

MSC

•  47H10
•  54H25

References

• [1] M. L. Bergamini, I. Grossmann, N. Seenna, P. Aguirre, An improved piecewise oute-approximation algorithm for the global optimization of MINLP models involving concave and bilinear terms, Comput. Chem. Eng., 32 (2008), 477-493.


• [2] C. Buchheim, L. Trieu, Quadratic outer approximation for convex integer programming with box constraints, Exp. Algorithms, 7933 (2013), 224-235.


• [3] Z. P. Chen, F. Xi , A new branch-and-bound algorithm for solving large complex integer convex quadratic programs, Math. Numer. Sin., 26 (2004), 445-458.


• [4] M. A. Duran, I. E. Grossmann, An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36 (1986), 307-339.


• [5] V. P. Eronena, M. M. Mäkeläa, T. Westerlundb, Extended cutting plane method for a class of nonsmooth non-convex MINLP problems, Optim, 64 (2015), 641-661.


• [6] R. Fletcher, S. Leyffler, Solving mixed intger nonlinear programs by outer approximation, Math. program., 66 (1994), 327-349.


• [7] O. E. Flippo, A. H. Rinnoy Kan, A note on benders decomposion in mixed-integer quadratic programming, Oper. Res. Lett., 9 (1990), 81-83.


• [8] Y. L. Gao, Y. J. Wang, X. W. Du, A two-level relaxed bound method for a nonlinear class of 0-1 knapsack problems, Intelligent Information, Manage. Syst. Technol., 3 (2005), 461-470.


• [9] Y. L. Gao, F. Wei, A branch-and-bound reduced method for a class of non-negative integer quadratic programming problems, math. Numer. sin., 33 (2011), 233-248.


• [10] T. Kuno, Solving a Class of Multiplicative programs with 0-1 Knapsack Constraints , J. Optim. Theory Appl., 103 (1999), 121-135.


• [11] R. Misener, C. A. Floudas, GloMIQO: Global mixed-integer quadratic optimizer, J. Global Optim., 57 (2013), 3-50.


• [12] I. Nowak, S. Vigerske., LaGO: a (heuristic) branch and cut algorithm for nonconvex MINLPs., CEJOR Cent. Eur. J. Oper. Res., 16 (2008), 127-138.


• [13] A. Schrijver, Theory of linear and integer programming, John Wiley and Sons, Chichester (1986)


• [14] R. A. Stubbs, S. Mehrotea, A branch-and-cut method for 0-1mixed convex programming, Math. Program., 86 (1999), 512-532.


• [15] X. L. Sun, J. L. Li, H. Z. Luo, Convex relaxation and Lagrangian decomposition for indefinite quadratic integer programming, Optim, 59 (2010), 627-641.


• [16] T. Westerlund, F. Pettersson, An extended cutting plane method for solving convex MINLP problems, Comput. Chem. Eng., 19 (1995), 131-136.