Online Mixed-Integer Optimization in Milliseconds

References

• Agrawal A, Amos B, Barratt S, Boyd S, Diamond S, Kolter Z (2019) Differentiable convex optimization layers. Conf. Proc. Adv. Neural Inform. Process. Systems (NeurIPS 2019), vol. 32, 1–13.Google Scholar
• Akiba T, Sano S, Yanase T, Ohta T, Koyama M (2019) Optuna: A next-generation hyperparameter optimization framework. Proc. 25rd ACM SIGKDD Internat. Conf. on Knowledge Discovery and Data Mining (Association for Computing Machinery, New York), 2623–2631.Google Scholar
• Alvarez AM, Louveaux Q, Wehenkel L (2017) A machine learning-based approximation of strong branching. INFORMS J. Comput. 29(1):185–195.Link, Google Scholar
• Banjac G, Stellato B, Moehle N, Goulart P, Bemporad A, Boyd S (2017) Embedded code generation using the OSQP solver. Proc. IEEE Conf. Decision Control., 1906–1911.Google Scholar
• Bemporad A, Morari M (1999) Control of systems integrating logic, dynamics, and constraints. Automatica J. IFAC 35(3):407–427.Crossref, Google Scholar
• Bemporad A, Morari M, Dua V, Pistikopoulos EN (2002) The explicit linear quadratic regulator for constrained systems. Automatica J. IFAC 38(1):3–20.Crossref, Google Scholar
• Bengio Y, Lodi A, Prouvost A (2021) Machine learning for combinatorial optimization: A methodological tour d’horizon. Eur. J. Oper. Res. 290(2):405–421.Crossref, Google Scholar
• Bertsimas D, Pachamanova D (2008) Robust multiperiod portfolio management in the presence of transaction costs. Comput. Oper. Res. 35(1):3–17.Crossref, Google Scholar
• Bertsimas D, Stellato B (2021) The voice of optimization. Machine Learn. 110:249–277.Crossref, Google Scholar
• Bertsimas D, Tsitsiklis JN (1997) Introduction to Linear Optimization (Dynamic Ideas Press, Bellmont, MA). Google Scholar
• Bertsimas D, Weismantel R (2005) Optimization over Integers (Dynamic Ideas Press, Bellmont, MA).Google Scholar
• Bertsimas D, Jaillet P, Martin S (2019) Online vehicle routing: The edge of optimization in large-scale applications. Oper. Res. 67(1):143–162.Link, Google Scholar
• Bixby RE (2012) A brief history of linear and mixed-integer programming computation. Documenta Math. 107–121. Google Scholar
• Bojarski M, Del Testa D, Dworakowski D, Firner B, Flepp B, Goyal P, Jackel LD, et al.. (2016) End to end learning for self-driving cars. Preprint, https://arxiv.org/abs/1604.07316.Google Scholar
• Bonami P, Lodi A, Zarpellon G (2018) Learning a classification of mixed-integer quadratic programming problems. van Hoeve WJ, ed. Integration of Constraint Programming, Artificial Intelligence, and Operations Research (Springer International Publishing, Cham, Switzerland), 595–604.Crossref, Google Scholar
• Boyd S, Vandenberghe L (2004) Convex Optimization (Cambridge University Press).Crossref, Google Scholar
• Boyd S, Busseti E, Diamond S, Kahn RN, Koh K, Nystrup P, Speth J (2017) Multi-period trading via convex optimization. Foundations Trends Optim. 3(1):1–76.Crossref, Google Scholar
• Catalão JPS, Pousinho H, Mendes V (2010) Scheduling of head-dependent cascaded hydro systems: Mixed-integer quadratic programming approach. Energy Conversion Management 51(3):524–530.Crossref, Google Scholar
• Cauligi A, Culbertson P, Stellato B, Bertsimas D, Schwager M, Pavone M (2020) Learning mixed-integer convex optimization strategies for robot planning and control. Proc. IEEE Conf. Decision Control, 1698–1705.Google Scholar
• Cesa-Bianchi N, Orabona F (2021) Online learning algorithms. Annu. Rev. Statist. Appl. 8(1):165–190.Crossref, Google Scholar
• Chen S, Saulnier K, Atanasov N, Lee DD, Kumar V, Pappas GJ, Morari M (2018) Approximating explicit model predictive control using constrained neural networks. Proc. Annual Amer. Control Conf., 1520–1527.Google Scholar
• Dai H, Dai B, Song L (2016) Discriminative embeddings of latent variable models for structured data. Proc. 33rd Internat. Conf. on Machine Learn., vol. 48, 2702–2711.Google Scholar
• Dai H, Khalil EB, Zhang Y, Dilkina B, Song L (2017) Learning combinatorial optimization algorithms over graphs. Adv. Neural Inform. Process. Systems 30:6351–6361.Google Scholar
• Damen O, Chkeif A, Belfiore JC (2000) Lattice code decoder for space-time codes. IEEE Commun. Lett. 4(5):161–163. Crossref, Google Scholar
• Davis TA (2006) Direct Methods for Sparse Linear Systems (SIAM, Philadelphia).Crossref, Google Scholar
• Diamond S, Boyd S (2016) CVXPY: A Python-embedded modeling language for convex optimization. J. Machine Learn. Res. 17(83):1–5.Google Scholar
• Diamond S, Takapoui R, Boyd S (2018) A general system for heuristic minimization of convex functions over non-convex sets. Optim. Methods Software 33(1):165–193.Crossref, Google Scholar
• Diehl M, Bock HG, Schlöder JP, Findeisen R, Nagy Z, Allgöwer F (2002) Real-time optimization and nonlinear model predictive control of processes governed by differential-algebraic equations. J. Process Controls 12(4):577–585.Crossref, Google Scholar
• Domahidi A, Chu E, Boyd S (2013) ECOS: An SOCP solver for embedded systems. Proc. Eur. Control Conf., 3071–3076.Google Scholar
• Falcon W (2019) Pytorch lightning. github.com/PyTorchLightning/pytorch-lightning.Google Scholar
• Ferreau HJ, Bock HG, Diehl M (2008) An online active set strategy to overcome the limitations of explicit mpc. Internat. J. Robust Nonlinear Control 18(8):816–830.Crossref, Google Scholar
• Ferreau HJ, Kirches C, Potschka A, Bock HG, Diehl M (2014) qpOASES: A parametric active-set algorithm for quadratic programming. Math. Programming Comput. 6(4):327–363.Crossref, Google Scholar
• Fischetti M, Glover F, Lodi A (2005) The feasibility pump. Math. Programming 104(1):91–104.Crossref, Google Scholar
• Frick D, Domahidi A, Morari M (2015) Embedded optimization for mixed logical dynamical systems. Comput. Chemical Engrg. 72:21–33.Crossref, Google Scholar
• Gamrath G, Hiller B, Witzig J (2015) Reoptimization techniques for MIP solvers. Bampis E, ed. Experimental Algorithms (Springer International Publishing, Cham, Switzerland), 181–192.Crossref, Google Scholar
• Good IJ (1953) The population frequencies of species and the estimation of population parameters. Biometrika 40(3/4):237–264.Crossref, Google Scholar
• Goodfellow I, Bengio Y, Courville A (2016) Deep Learning (MIT Press, Cambrdge, MA).Google Scholar
• Gurobi Optimization, LLC (2020) Gurobi optimizer reference manual. Google Scholar
• Hassanzadeh A, Ralph TK (2014) On the value function of a mixed integer linear optimization problem and an algorithm for its construction. Technical report, COR@L Laboratory Report 14T-004, Lehigh University, Bethlehem, PA.Google Scholar
• Hazan E (2016) Introduction to online convex optimization. Foundations Trends Optim. 2(3–4):157–325.Crossref, Google Scholar
• Herzog F, Dondi G, Geering HP (2007) Stochastic model predictive control and portfolio optimization. Internat. J. Theoretical Appl. Finance 10(02):203–233.Crossref, Google Scholar
• Hinton G, Deng L, Yu D, Dahl GE, Mohamed A, Jaitly N, Senior A, et al. (2012) Deep neural networks for acoustic modeling in speech recognition: The shared views of four research groups. IEEE Signal Processing Magazine 29(6):82–97.Crossref, Google Scholar
• Jünger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, et al. (2010) 50 Years of Integer Programming 1958-2008 (Springer, Berlin).Crossref, Google Scholar
• Khalil EB, Bodic PL, Song L, Nemhauser G, Dilkina B (2016) Learning to branch in mixed integer programming. Proc. 30th AAAI Conf. on Artificial Intelligence (AAAI Press, Palo Alto, CA), 724–731.Google Scholar
• Klaučo M, Kalúz M, Kvasnica M (2019) Machine learning-based warm starting of active set methods in embedded model predictive control. Engrg. Appl. Artificial Intelligence 77:1–8.Crossref, Google Scholar
• Krizhevsky A, Sutskever I, Hinton GE (2012) Imagenet classification with deep convolutional neural networks. Adv. Neural Inform. Processing Systems 25:1–9.Google Scholar
• LaValle SM (2006) Planning Algorithms (Cambridge University Press, New York).Crossref, Google Scholar
• LeCun Y, Bengio Y, Hinton G (2015) Deep learning. Nature 521(7553):436–444.Crossref, Google Scholar
• Lodi A, Zarpellon G (2017) On learning and branching: A survey. TOP 25(2):207–236.Crossref, Google Scholar
• Marcucci T, Tedrake R (2021) Warm start of mixed-integer programs for model predictive control of hybrid systems. IEEE Trans. Automatic Control 66(6):2433–2448.Google Scholar
• Markowitz H (1952) Portfolio selection. J. Finance 7(1):77–91.Google Scholar
• Mattingley J, Boyd S (2010) Real-time convex optimization in signal processing. IEEE Signal Processing Magazine 27(3):50–61.Crossref, Google Scholar
• Mattingley J, Boyd S (2012) CVXGEN: A code generator for embedded convex optimization. Optim. Engrg. 13(1):1–27.Crossref, Google Scholar
• Misra S, Roald L, Ng Y (2021) Learning for constrained optimization: Identifying optimal active constraint sets. INFORMS J. Comput. 34(1):463–480.Google Scholar
• Nocedal J, Wright SJ (2006) Numerical Optimization. Springer Series in Operations Research and Financial Engineering, 2nd ed. (Springer, Berlin).Google Scholar
• Oberdieck R, Diangelakis NA, Papathanasiou MM, Nascu I, Pistikopoulos EN (2016) Pop–parametric optimization toolbox. Industrial Engrg. Chemical Res. 55(33):8979–8991.Crossref, Google Scholar
• Paige CC, Saunders MA (1982) LSQR: An algorithm for sparse linear equations and sparse least squares. ACM Trans. Math. Software 8(1):43–71.Crossref, Google Scholar
• Paszke A, Gross S, Chintala S, Chanan G, Yang E, DeVito Z, Lin Z, et al.. (2017) Automatic Differentiation in PyTorch (NIPS-W).Google Scholar
• Quandl (2019) WIKI S&P100 End-Of-Day Data. https://www.quandl.com/data/WIKI.Google Scholar
• Ralphs TL, Güzelsoy M (2006) Duality and warm starting in integer programming. Proc. NSF Design, Service, and Manufacturing Grantees and Res. Conf.Google Scholar
• Schouwenaars T, De Moor B, Feron E, How J (2001) Mixed integer programming for multi-vehicle path planning. Proc. Eur. Control Conf., 2603–2608.Google Scholar
• Silver D, Schrittwieser J, Simonyan K, Antonoglou I, Huang A, Guez A, Hubert T, et al. (2017) Mastering the game of Go without human knowledge. Nature 550(7676):354–359.Crossref, Google Scholar
• Stellato B, Banjac G, Goulart P, Bemporad A, Boyd S (2020) OSQP: An operator splitting solver for quadratic programs. Math. Program. Comput. 12(4):637–672.Google Scholar
• Sutton RS, Barto AG (2018) Reinforcement Learning: An Introduction, 2nd ed. (MIT Press, Cambridge, MA).Google Scholar
• Tavaslioğlu O, Prokopyev OA, Schaefer AJ (2019) Solving stochastic and bilevel mixed-integer programs via a generalized value function. Oper. Res. 67(6):1659–1677.Link, Google Scholar
• Trapp AC, Prokopyev OA, Schaefer AJ (2013) On a level-set characterization of the value function of an integer program and its application to stochastic programming. Oper. Res. 61(2):498–511.Link, Google Scholar
• Wang Y, Boyd S (2009) Fast model predictive control using online optimization. IEEE Trans. Control Systems Tech. 18(2):267–278.Crossref, Google Scholar
• You F, Grossmann IE (2008) Mixed-integer nonlinear programming models and algorithms for large-scale supply chain design with stochastic inventory management. Industrial Engrg. Chemical Res. 47(20):7802–7817.Crossref, Google Scholar