A simple effective heuristic for embedded mixed-integer quadratic programming

References

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