×

zbMATH — the first resource for mathematics

Linear transformation based solution methods for non-convex mixed integer quadratic programs. (English) Zbl 1373.90084
Summary: Two preprocessing techniques for mixed integer quadratic programs with non-convex objective functions are presented. The first is a convexification scheme and can be applied to problems were the continuous part of the Hessian is positive semidefinite. The second technique aims to reduce the size of the underestimating problems solved by branch-and-bound algorithms and can be applied to problems were the continuous part of the Hessian is singular. Numerical results are presented showing the effect of the preprocessing techniques.

MSC:
90C11 Mixed integer programming
90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Newby, E.: General solution methods for mixed integer quadratic programming and derivative free mixed integer non-linear programming problems. Ph.D. dissertation, University of the Witwatersrand (2013)
[2] Newby, E; Ali, MM, A trust-region-based derivative free algorithm for mixed integer programming, Comput. Optim. Appl., 60, 199-229, (2015) · Zbl 1308.90112
[3] Billionnet, A; Elloumi, S; Lambert, A, Extending the QCR method to general mixed-integer programs, Math. Program., 131, 381-401, (2012) · Zbl 1235.90100
[4] Burer, S, On the copositive representation of binary and continuous nonconvex quadratic programs, Math. Program., 120, 479-495, (2009) · Zbl 1180.90234
[5] Misener, R; Floudas, C, Glomiqo: global mixed-integer quadratic optimizer, J. Glob. Optim., (2012) · Zbl 1272.90034
[6] Burer, S; Saxena, A; Lee, J (ed.); Leyffer, S (ed.), The MILP road to MIQCP, 373-405, (2012), New York · Zbl 1242.90122
[7] Laurent, M; Poljak, S, Gap inequalities for the cut polytope, Eur. J. Combin., 17, 233-254, (1996) · Zbl 0849.52010
[8] Galli, L; Kaparis, K; Letchford, AN, Gap inequalities for non-convex mixed-integer quadratic programs, Oper. Res. Lett., 39, 297-300, (2011) · Zbl 1235.90102
[9] Buchheim, C., Wiegele, A.: Using semidefinite programming for solving non-convex mixed-integer quadratic problems. In: Proceedings of the European Workshop on Mixed Integer Nonlinear Programming (2010) · Zbl 1280.90091
[10] Sahinidis, N, BARON: a general purpose global optimization software package, J. Glob. Optim., 8, 201-205, (1996) · Zbl 0856.90104
[11] Belotti, P; Lee, J; Liberti, L; Margot, F; Wachter, A, Branching and bounds tightening techniques for non-convex MINLP, Optim. Methods Softw., 24, 597-634, (2009) · Zbl 1179.90237
[12] Achterberg, T, SCIP: solving constraint integer programs, Math. Program. Comput., 1, 1-41, (2009) · Zbl 1171.90476
[13] Gau, CY; Schrage, LE; Floudas, CA (ed.); Pardalos, PM (ed.), Implementation and testing of a branch-and-bound based method for deterministic global optimization: operations research applications, 145-164, (2003), Berlin
[14] Lin, Y; Schrage, LE, The global solver in the LINDO API, Optim. Methods Software., 24, 657-668, (2009) · Zbl 1177.90325
[15] Misener, R; Floudas, C, Glomiqo: global optimization of mixed-integer quadratically-constrained quadratic programs (MIQCQP) through piecewise-linear and edge-concave relaxations, Math. Program. B, 136, 155-182, (2012) · Zbl 1257.90079
[16] Pörn, R; Harjunkoski, I; Westerlund, T, Convexification of different classes of non-convex MINLP problems, Comput. Chem. Eng., 23, 439-448, (1999)
[17] Newby, E; Ali, MM, A note on convex reformulation schemes for mixed integer quadratic programs, J. Optim. Theory Appl., 160, 457-469, (2013) · Zbl 1298.90060
[18] Newby, E; Ali, MM, Transformation-based preprocessing for mixed-integer quadratic programs, J. Optim. Theory Appl., (2015) · Zbl 1338.90276
[19] Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985) · Zbl 0576.15001
[20] McCormick, GP, Computability of global solutions to factorable nonconvex programs: part I convex underestimating problems, Math. Program., 10, 147-175, (1976) · Zbl 0349.90100
[21] Anton, H., Rorres, C.: Elementary Linear Algebra. Wiley, New Jersey (2005) · Zbl 0615.15002
[22] Czyzyk, J; Mesnier, MP; More, JJ, The NEOS server, IEEE Comput. Sci. Eng., 5, 68-75, (1998)
[23] Gropp, W; Moré, JJ; Buhmann, MD (ed.); Iserles, A (ed.), Optimization environments and the NEOS server, 167-182, (1997), Cambridge · Zbl 1031.65075
[24] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
[25] Zamora, JM; Grossman, IE, A branch and contract algorithm for problems with concave univariate, bilinear and linear fractional terms, J. Glob. Optim., 14, 217-249, (1999) · Zbl 0949.90097
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.