×

zbMATH — the first resource for mathematics

Transformation-based preprocessing for mixed-integer quadratic programs. (English) Zbl 1338.90276
Summary: This paper presents two preprocessing techniques for mixed-integer quadratic programs with non-convex objective functions, where the continuous part of the Hessian is invertible. The techniques aim at reducing the number of bilinear terms in the objective. Results show that one of the techniques decreases the solution times once the reduction in bilinear terms crosses a threshold.

MSC:
90C11 Mixed integer programming
90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
15A04 Linear transformations, semilinear transformations
Software:
BARON; SCIP; OPTI; Matlab
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] Sahinidis, N, BARON: a general purpose global optimization software package, J. Global Optim., 8, 201-205, (1996) · Zbl 0856.90104
[3] Achterberg, T, SCIP: solving constraint integer programs, Math. Program. Comput., 1, 1-41, (2009) · Zbl 1171.90476
[4] 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
[5] Zheng, XJ; Sun, XL; Li, D, Separable relaxation for nonconvex quadratic integer programming: integer diagonalization approach, J. Optim. Theory Appl., 146, 463-489, (2010) · Zbl 1198.90299
[6] 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
[7] Currie, J., Wilson D.I.: OPTI: lowering the barrier between open source optimizers and the industrial MATLAB user. In: Proceedings of foundations of computer-aided process operations (2012) · Zbl 1171.90476
[8] Dolan, ED; MorĂ©, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
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.