×

A simple effective heuristic for embedded mixed-integer quadratic programming. (English) Zbl 1434.90117

Summary: In this paper, we propose a fast optimisation algorithm for approximately minimising convex quadratic functions over the intersection of affine and separable constraints (i.e., the Cartesian product of possibly nonconvex real sets). This problem class contains many NP-hard problems such as mixed-integer quadratic programming. Our heuristic is based on a variation of the alternating direction method of multipliers (ADMM), an algorithm for solving convex optimisation problems. We discuss the favourable computational aspects of our algorithm, which allow it to run quickly even on very modest computational platforms such as embedded processors. We give several examples for which an approximate solution should be found very quickly, such as management of a hybrid-electric vehicle drivetrain and control of switched-mode power converters. Our numerical experiments suggest that our method is very effective in finding a feasible point with small objective value; indeed, we see that in many cases, it finds the global solution.

MSC:

90C20 Quadratic programming
90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Achterberg, T.; Berthold, T., Improving the feasibility pump, Discrete Optimization,, 4, 1, 77-86 (2007) · Zbl 1170.90443
[2] Aybat, N.; Zarmehri, S.; Kumara, S., An ADMM algorithm for clustering partially observed networks, Proceedings of the 2015 SIAM international conference on data mining (2015), Vancouver, Canada: SIAM, Vancouver, Canada
[3] Beasley, J. E., Heuristic algorithms for the unconstrained binary quadratic programming problem (1998), London: Management School, Imperial College, London
[4] Beck, A., Introduction to nonlinear optimization: Theory, algorithms, and applications with MATLAB, 19 (2014), Philadelphia, PA: SIAM, Philadelphia, PA · Zbl 1320.90001
[5] Bemporad, A., Solving mixed-integer quadratic programs via nonnegative least squares, 5th IFAC conference on nonlinear model predictive control, 73-79 (2015), Seville, Spain: International Federation of Automatic Control, Seville, Spain
[6] Bemporad, A.; Morari, M., Control of systems integrating logic, dynamics, and constraints, Automatica,, 35, 3, 407-427 (1999) · Zbl 1049.93514
[7] Bertacco, L.; Fischetti, M.; Lodi, A., A feasibility pump heuristic for general mixed-integer problems, Discrete Optimization,, 4, 1, 63-76 (2007) · Zbl 1169.90415
[8] Bertsekas, D. P.; Eckstein, J., Dual coordinate step methods for linear network flow problems, Mathematical Programming,, 42, 1-3, 203-243 (1988) · Zbl 0664.90031
[9] Bienstock, D., Computational study of a family of mixed-integer quadratic programming problems, Mathematical Programming,, 74, 2, 121-140 (1996) · Zbl 0855.90090
[10] Boley, D., Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs, SIAM Journal on Optimization,, 23, 4, 2183-2207 (2013) · Zbl 1288.65086
[11] Boyd, S.; Vandenberghe, L., Convex optimization (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1058.90049
[12] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning,, 3, 1, 1-122 (2011) · Zbl 1229.90122
[13] Bradley, A. M., Algorithms for the equilibration of matrices and their application to limited-memory quasi-newton methods (2010), Stanford University, CA: Stanford University, Stanford University, CA
[14] Buso, S.; Mattavelli, P., Digital control in power electronics, Lectures on Power Electronics,, 1, 1, 1-158 (2006)
[15] Camara, M.; Gualous, H.; Gustin, F.; Berthon, A.; Dakyo, B., DC/DC converter design for supercapacitor and battery power management in hybrid vehicle applications-polynomial control strategy, IEEE Transactions on Industrial Electronics,, 57, 2, 587-597 (2010)
[16] Carrión, M.; Arroyo, J. M., A computationally efficient mixed-integer linear formulation for the thermal unit commitment problem, IEEE Transactions on Power Systems,, 21, 3, 1371-1378 (2006)
[17] Catalão, J. P.S.; Pousinho, H. M.I.; Mendes, V. M.F., Scheduling of head-dependent cascaded hydro systems: Mixed-integer quadratic programming approach, Energy Conversion and Management,, 51, 3, 524-530 (2010)
[18] Chakraborty, S.; Lukasiewycz, M.; Buckl, C.; Fahmy, S.; Chang, N.; Park, S.; Adlkofer, H., Embedded systems and software challenges in electric vehicles, Proceedings of the conference on design, automation and test in Europe, 424-429 (2012), San Jose, CA: EDA Consortium, San Jose, CA
[19] Chartrand, R., Nonconvex splitting for regularized low-rank + sparse decomposition, IEEE Transactions on Signal Processing,, 60, 11, 5810-5819 (2012) · Zbl 1393.94190
[20] Chartrand, R.; Wohlberg, B., A nonconvex ADMM algorithm for group sparsity with sparse groups, Proceedings of IEEE international conference on acoustics, speech and signal processing (ICASSP), 6009-6013 (2013), Vancouver, Canada: IEEE, Vancouver, Canada
[21] Chu, E.; Parikh, N.; Domahidi, A.; Boyd, S., Code generation for embedded second-order cone programming, Proceedings of the 2013 European control conference, 1547-1552 (2013), Zurich, Switzerland: IEEE Control Systems Society, Zurich, Switzerland
[22] Chvátal, V.; Cook, W.; Hartmann, M., On cutting-plane proofs in combinatorial optimization, Linear Algebra and Its Applications,, 114, 455-499 (1989) · Zbl 0676.90059
[23] Damen, O.; Chkeif, A.; Belfiore, J., Lattice code decoder for space-time codes, IEEE Communications Letters,, 4, 5, 161-163 (2000)
[24] Deng, W.; Yin, W., On the global and linear convergence of the generalized alternating direction method of multipliers, Journal of Scientific Computing,, 66, 1-28 (2012)
[25] Derbinsky, N.; Bento, J.; Elser, V.; Yedidia, J. S., An improved three-weight message-passing algorithm (2013)
[26] Diehl, M.; Bock, H.; Schlöder, J., A real-time iteration scheme for nonlinear optimization in optimal feedback control, SIAM Journal on Control and Optimization,, 43, 5, 1714-1736 (2005) · Zbl 1078.65060
[27] Domahidi, A.; Chu, E.; Boyd, S., ECOS: An SOCP solver for embedded systems, Proceedings of the 12th European control conference, 3071-3076 (2013), Zurich, Switzerland: IEEE, Zurich, Switzerland
[28] Erseghe, T., Distributed optimal power flow using ADMM, IEEE Transactions on Power Systems,, 29, 5, 2370-2380 (2014)
[29] lt, M.; Jimbergsson, L., Using ADMM for hybrid system MPC (2015)
[30] Ferreau, H.; Kirches, C.; Potschka, A.; Bock, H.; Diehl, M., qpOASES: A parametric active-set algorithm for quadratic programming, Mathematical Programming Computation,, 6, 4, 327-363 (2014) · Zbl 1302.90146
[31] Fischetti, M.; Glover, F.; Lodi, A., The feasibility pump, Mathematical Programming,, 104, 1, 91-104 (2005) · Zbl 1077.90039
[32] Frick, D.; Domahidi, A.; Morari, M., Embedded optimization for mixed logical dynamical systems, Computers and Chemical Engineering,, 72, 21-33 (2015)
[33] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Computers & Mathematics with Applications,, 2, 1, 17-40 (1976) · Zbl 0352.65034
[34] Ghadimi, E.; Teixeira, A.; Shames, I.; Johansson, M., Optimal parameter selection for the alternating direction method of multipliers (ADMM): Quadratic problems, IEEE Transactions on Automatic Control,, 60, 3, 644-658 (2015) · Zbl 1360.90182
[35] Giselsson, P., Improved fast dual gradient methods for embedded model predictive control, International federation of automatic control (IFAC), 2303-2309 (2014), Cape Town, South Africa: Elsevier, Cape Town, South Africa
[36] Giselsson, P.; Boyd, S., Diagonal scaling in Douglas-Rachford splitting and ADMM, 53rd Annual IEEE conference on decision and control (CDC), 5033-5039 (2014), Los Angeles, CA: IEEE, Los Angeles, CA
[37] Giselsson, P.; Boyd, S., Monotonicity and restart in fast gradient methods, 53rd annual IEEE conference on decision and control (CDC), 5058-5063 (2014), Los Angeles, CA: IEEE, Los Angeles, CA
[38] Giselsson, P.; Boyd, S., Preconditioning in fast dual gradient methods, 53rd annual IEEE conference on decision and control (CDC), 5040-5045 (2014), Los Angeles, CA: IEEE, Los Angeles, CA
[39] Glover, I.; Grant, P. M., Digital communications (2010), London: Pearson Education, London
[40] Glowinski, R.; Marroco, A., On the solution of a class of nonlinear Dirichlet problems by a penalty-duality method and finite elements of order one, Revue française d’automatique, informatique, recherche opérationnelle. Analyse numérique,, 9, 2, 41-76 (1975) · Zbl 0368.65053
[41] Gomory, R. E., Outline of an algorithm for integer solutions to linear programs, Bulletin of the American Mathematical Society,, 64, 5, 275-278 (1958) · Zbl 0085.35807
[42] Hochbaum, D. S., Approximation algorithms for the set covering and vertex cover problems, SIAM Journal on Computing,, 11, 3, 555-556 (1982) · Zbl 0486.68067
[43] Hong, M., A distributed, asynchronous and incremental algorithm for nonconvex optimization: An ADMM based approach (2014)
[44] Hong, M.; Luo, Z., On the linear convergence of the alternating direction method of multipliers (2012)
[45] Hong, M.; Luo, Z.; Razaviyayn, M., Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems, IEEE international conference on acoustics, speech and signal processing, 3836-3840 (2015), South Brisbane, Oueensland: IEEE, South Brisbane, Oueensland
[46] Huang, K.; Sidiropoulos, N. D., Consensus-ADMM for general quadratically constrained quadratic programming (2016) · Zbl 1414.90256
[47] User’s manual for CPLEX (2009), North Castle, NY: International Business Machines Corporation, North Castle, NY
[48] Jeroslow, R. G.; Wang, J., Solving propositional satisfiability problems, Annals of Mathematics and Artificial Intelligence,, 1, 1-4, 167-187 (1990) · Zbl 0878.68107
[49] Jiang, B.; Ma, S.; Zhang, S., Alternating direction method of multipliers for real and complex polynomial optimization models, Optional,, 883-898 (2014) · Zbl 1291.90242
[50] Karp, R. M., Reducibility among combinatorial problems (1972), New York, NY: Springer, New York, NY
[51] Lawler, E. L.; Wood, D. E., Branch-and-bound methods: A survey, Operations Research,, 14, 4, 699-719 (1966) · Zbl 0143.42501
[52] Li, G.; Pong, T. K., Global convergence of splitting methods for nonconvex composite optimization, SIAM Journal on Optimization,, 25, 4, 2434-2460 (2015) · Zbl 1330.90087
[53] Li, R.; Zhou, D.; Du, D., Satisfiability and integer programming as complementary tools, Proceedings of the 2004 Asia and South Pacific design automation conference, 879-882 (2004), Kanagawa, Japan: IEEE, Kanagawa, Japan
[54] Liavas, A. P.; Sidiropoulos, N. D., Parallel algorithms for constrained tensor factorization via alternating direction method of multipliers, IEEE Transactions on Signal Processing,, 63, 20, 5450-5463 (2015) · Zbl 1394.94321
[55] Makela, O.; Warrington, J.; Morari, M.; Andersson, G., Optimal transmission line switching for large-scale power systems using the alternating direction method of multipliers, Power systems computation conference (PSCC) 2014, 1-6 (2014), Wroclaw, Poland: IEEE, Wroclaw, Poland
[56] Mattingley, J.; Boyd, S., CVXGEN: A code generator for embedded convex optimization, Optimization and Engineering,, 13, 1, 1-27 (2012) · Zbl 1293.65095
[57] Mattingley, J.; Wang, Y.; Boyd, S., Receding horizon control: Automatic generation of high-speed solvers, IEEE Control Systems Magazine,, 31, 3, 52-65 (2011) · Zbl 1395.93207
[58] The MOSEK optimization toolbox for MATLAB manual. Version 7.1 (Revision 28) (2015)
[59] Mota, J.; Xavier, J.; Aguiar, P.; schel, M., Basis pursuit in sensor networks, 2011 IEEE international conference on acoustics, speech and signal processing (ICASSP), 2916-2919 (2011), Prague, Czech Republic: IEEE, Prague, Czech Republic
[60] Murgovski, N.; Johannesson, L.; Sjöberg, J.; Egardt, B., Component sizing of a plug-in hybrid electric powertrain via convex optimization, Mechatronics,, 22, 1, 106-120 (2012)
[61] Muta, K.; Yamazaki, M.; Tokieda, J., Development of new-generation hybrid system THS II - drastic improvement of power performance and fuel economy, SAE Transactions,, 113, 3, 182-192 (2004)
[62] O’Donoghue, B.; Stathopoulos, G.; Boyd, S., A splitting method for optimal control, IEEE Transactions on Control Systems Technology,, 21, 6, 2432-2442 (2013)
[63] Oulai, D.; Chamberland, S.; Pierre, S., A new routing-based admission control for MPLS networks, IEEE Communications Letters,, 11, 2, 216-218 (2007)
[64] Padberg, M. W., On the facial structure of set packing polyhedra, Mathematical Programming,, 5, 1, 199-215 (1973) · Zbl 0272.90041
[65] Papadimitriou, C. H.; Steiglitz, K., Combinatorial optimization: Algorithms and complexity (1998), North Chelmsford, MA: Courier Corporation, North Chelmsford, MA · Zbl 0944.90066
[66] Papageorgiou, L. G.; Fraga, E. S., A mixed-integer quadratic programming formulation for the economic dispatch of generators with prohibited operating zones, Electric Power Systems Research,, 77, 10, 1292-1296 (2007)
[67] Peng, Z.; Chen, J.; Zhu, W., A proximal alternating direction method of multipliers for a minimization problem with nonconvex constraints, Journal of Global Optimization, 62, 1-18 (2015)
[68] Schizas, L.; Ribeiro, A.; Giannakis, G., Consensus in ad hoc WSNs with noisy links? Part I: Distributed estimation of deterministic signals, IEEE Transactions on Signal Processing,, 56, 1, 350-364 (2008) · Zbl 1390.94395
[69] Sedghi, H.; Anandkumar, A.; Jonckheere, E., Multi-step stochastic ADMM in high dimensions: Applications to sparse optimization and matrix decomposition, Advances in neural information processing systems, 2771-2779 (2014), Montreal, Canada: Advances in Neural Information Proecssing Systems 27, Montreal, Canada
[70] Shi, W.; Ling, Q.; Yuan, K.; Wu, G.; Yin, W., On the linear convergence of the admm in decentralized consensus optimization, IEEE Transactions on Signal Processing,, 62, 7, 1750-1761 (2014) · Zbl 1394.94532
[71] Sinnokrot, M.; Barry, J.; Madisetti, V., Embedded Alamouti space-time codes for high rate and low decoding complexity, 2008 42nd Asilomar conference on signals, systems and computers, 1749-1753 (2008), Pacific Grove, CA: IEEE, Pacific Grove, CA
[72] Sluis, A. V.D., Condition numbers and equilibration of matrices, Numerische Mathematik,, 14, 1, 14-23 (1969) · Zbl 0182.48906
[73] Smedley, K.; Cuk, S., One-cycle control of switching converters, IEEE Transactions on Power Electronics,, 10, 6, 625-633 (1995)
[74] Stubbs, R. A.; Mehrotra, S., A branch-and-cut method for 0-1 mixed convex programming, Mathematical Programming,, 86, 3, 515-532 (1999) · Zbl 0946.90054
[75] Ullmann, F., FiOrdOs: A Matlab toolbox for C-code generation for first order methods (2011), ETH Zurich
[76] Viterbo, E.; Boutros, J., A universal lattice code decoder for fading channels, IEEE Transactions on Information Theory,, 45, 5, 1639-1642 (1999) · Zbl 0957.94009
[77] Wahlberg, B.; Boyd, S.; Annergren, M.; Wang, Y., An ADMM algorithm for a class of total variation regularized estimation problems, IFAC Proceedings Volumes,, 45, 16, 83-88 (2012)
[78] Wang, D.; Lu, H.; Yang, M., Online object tracking with sparse prototypes, IEEE Transactions on Image Processing,, 22, 1, 314-325 (2013) · Zbl 1373.94423
[79] Wang, F.; Xu, Z.; Xu, H., Convergence of alternating direction method with multipliers for non-convex composite problems (2014)
[80] Wang, Y.; Boyd, S., Fast model predictive control using online optimization, IEEE Transactions on Control Systems Technology,, 18, 2, 267-278 (2010)
[81] Gao, D. Mi; Emadi, A., Modeling and simulation of electric and hybrid vehicles, Proceedings of the IEEE,, 95, 4, 729-745 (2007)
[82] Wolsey, L. A., Integer programming (1998), New York, NY: Wiley, New York, NY · Zbl 0930.90072
[83] Wright, S. J.; Nocedal, J., Numerical optimization (1999), New York, NY: Springer, New York, NY · Zbl 0930.65067
[84] Xu, Y.; Yin, W.; Wen, Z.; Zhang, Y., An alternating direction algorithm for matrix completion with nonnegative factors, Frontiers of Mathematics in China,, 7, 2, 365-384 (2012) · Zbl 1323.65044
[85] Zhang, R.; Kwok, J. T., Asynchronous distributed ADMM for consensus optimization, ICML, 1701-1709 (2014), Beijing, China: International Conference on Machine Learning, Beijing, China
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.