An efficient compact quadratic convex reformulation for general integer quadratic programs. (English) Zbl 1267.90092
Summary: We address the exact solution of general integer quadratic programs with linear constraints. These programs constitute a particular case of mixed-integer quadratic programs for which we introduce in our work [Math. Program. 131, No. 1–2(A), 381–401 (2012; Zbl 1235.90100)] a general solution method based on quadratic convex reformulation, that we called MIQCR. This reformulation consists in designing an equivalent quadratic program with a convex objective function. The problem reformulated by MIQCR has a relatively important size that penalizes its solution time. In this paper, we propose a convex reformulation less general than MIQCR because it is limited to the general integer case, but that has a significantly smaller size. We call this approach compact quadratic convex reformulation (CQCR). We evaluate CQCR from the computational point of view. We perform our experiments on instances of general integer quadratic programs with one equality constraint. We show that CQCR is much faster than MIQCR and than the general nonlinear solver BARON (see [N. V. Sahinidis and M. Tawarmalani, “BARON 9.0.4: Global optimization of mixed-integer nonlinear programs”, User’s manual (2010])) to solve these instances. Then, we consider the particular class of binary quadratic programs. We compare MIQCR and CQCR on instances of the constrained task assignment problem. These experiments show that CQCR can solve instances that MIQCR and other existing methods fail to solve.
Keywords:
quadratic programming; integer programming; exact convex reformulation; computational experimentsCitations:
Zbl 1235.90100References:
| [1] | Audet, C., Hansen, P., Savard, G.: Essays and Surveys in Global Optimization. GERAD 25th Anniversary Series. Springer, New York (2005) · Zbl 1071.90001 |
| [2] | Audet, C., Hansen, P., Jaumard, B., Savard, G.: Links between linear bilevel and mixed 0–1 programming problems. J. Optim. Theory Appl. 93(2), 273–300 (1997) · Zbl 0901.90153 · doi:10.1023/A:1022645805569 |
| [3] | Billionnet, A., Elloumi, S., Lambert, A.: Extending the QCR method to the case of general mixed integer program. Math. Program. 13(1), 381–401 (2012) · Zbl 1235.90100 · doi:10.1007/s10107-010-0381-7 |
| [4] | Billionnet, A., Elloumi, S., Lambert, A.: Linear reformulations of integer quadratic programs. In: Le Thi, H.A., Bouvry, P., Tao, P.D. (eds.) Modelling, Computation and Optimization in Information Systems and Management Sciences, Second International Conference, MCO 2008, September 8–10, Metz, France, pp. 43–51 (2008) · Zbl 1160.90589 |
| [5] | Billionnet, A., Elloumi, S., Plateau, M.-C.: Improving the performance of standard solvers for quadratic 0–1 programs by a tight convex reformulation: the QCR method. Discrete Appl. Math. 157(6), 1185–1197 (2009) · Zbl 1169.90405 · doi:10.1016/j.dam.2007.12.007 |
| [6] | Borchers, B.: CSDP, A C library for semidefinite programming. Optim. Methods Softw. 11(1), 613–623 (1999) · Zbl 0973.90524 · doi:10.1080/10556789908805765 |
| [7] | Cui, Y.: Dynamic programming algorithms for the optimal cutting of equal rectangles. Appl. Math. Model. 29, 1040–1053 (2005) · Zbl 1163.90779 · doi:10.1016/j.apm.2005.02.007 |
| [8] | EIQP: http://cedric.cnam.fr/\(\sim\)lambe_a1/siqp/Library/index.php |
| [9] | Elloumi, S.: Contribution à la résolution des programmes non linéaires en variables 0–1, application aux problèmes de placement de tâches dans les systèmes distribués. Thèse de doctorat en informatique, Conservatoire National des Arts et Métiers (1991) |
| [10] | Feo, T.A., Resende, M.G.C.: A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8, 67–71 (1989) · Zbl 0675.90073 · doi:10.1016/0167-6377(89)90002-3 |
| [11] | Floudas, C.A.: Deterministic Global Optimization. Kluwer Academic, Dordrecht (2000) · Zbl 0980.49027 |
| [12] | Frangioni, A., Gentile, C.: Perspective cuts for a class of convex 0–1 mixed integer programs. Math. Program. 106, 225–236 (2006) · Zbl 1134.90447 · doi:10.1007/s10107-005-0594-3 |
| [13] | Fu, H.L., Shiue, L., Cheng, X., Du, D.Z., Kim, J.M.: Quadratic integer programming with application in the chaotic mappings of complete multipartite graphs. J. Optim. Theory Appl. 110(3), 545–556 (2001) · Zbl 1064.90028 · doi:10.1023/A:1017584227417 |
| [14] | Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completness. Freeman, San Francisco (1979) · Zbl 0411.68039 |
| [15] | globallib: http://www.gamsworld.org/global/globallib/globalstat.htm |
| [16] | Hahn, P., Kim, B.J., Guignard, M., Smith, J., Zhu, Y.R.: An algorithm for the generalized quadratic assignment problem. Comput. Optim. Appl. 40(3), 351–372 (2008). Available online doi: 10.1007/s10589-007-9093-1 · Zbl 1153.90521 · doi:10.1007/s10589-007-9093-1 |
| [17] | Hua, Z.S., Banerjee, P.: Aggregate line capacity design for PWB assembly systems. Int. J. Prod. Res. 38(11), 2417–2441 (2000) · Zbl 0973.90507 |
| [18] | IBM-ILOG, IBM ILOG CPLEX 12.1 Reference Manual. IBM ILOG CPLEX (2010) |
| [19] | Liberti, L., Maculan, N.: Nonconvex optimization and its applications. In: Global Optimization: From Theory to Implementation. Springer, New York (2006) · Zbl 1087.90005 |
| [20] | Laguna, M., Mart, R.: GRASP and path relinking for 2-layer straight line crossing minimization. INFORMS J. Comput. 11, 44–52 (1999) · Zbl 1092.90544 · doi:10.1287/ijoc.11.1.44 |
| [21] | Lambert, A.: Résolution de programmes quadratiques en nombres entiers. Thèse de doctorat en informatique, Conservatoire National des Arts et Métiers. (ref. CEDRIC 1838) (2009) |
| [22] | Mateus, G.R., Resende, M.G.C., Silva, R.M.A.: GRASP with path-relinking for the generalized quadratic assignment problem. J. Heuristics 17(1), 527–565 (2011) · Zbl 1233.90213 · doi:10.1007/s10732-010-9144-0 |
| [23] | minlplib: http://www.gamsworld.org/minlp/minlplib.htm |
| [24] | Resende, M.G.C., Ribeiro, C.C.: GRASP with path-relinking: recent advances and applications. In: Ibaraki, T., Nonobe, K., Yagiura, M. (eds.) Metaheuristics: Progress as Real Problem Solvers, pp. 29–63. Springer, Berlin (2005) |
| [25] | Sahinidis, N.V., Tawarmalani, M.: BARON 9.0.4: Global optimization of mixed-integer nonlinear programs. User’s manual (2010). Available at http://www.gams.com/dd/docs/solvers/baron.pdf |
| [26] | Sahinidis, N.V., Tawarmalani, M.: A polyhedral branch-and-cut approach to global optimization. Math. Program. 103(2), 225–249 (2005) · Zbl 1099.90047 · doi:10.1007/s10107-005-0581-8 |
| [27] | Sherali, H.D., Adams, W.P.: A tight linearization and an algorithm for zero-one quadratic programming problems. Manag. Sci. 32(10), 1274–1290 (1986) · Zbl 0623.90054 · doi:10.1287/mnsc.32.10.1274 |
| [28] | TAPLib: http://cedric.cnam.fr/oc/TAP/TAP.html |
| [29] | Tawarmalani, M., Sahinidis, N.V.: Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming. Kluwer Academic, Dordrecht (2002) · Zbl 1031.90022 |
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.
