Abstract
We are interested in structures and efficient methods for mixed-integer nonlinear programs (MINLP) that arise from a first discretize, then optimize approach to time-dependent mixed-integer optimal control problems (MIOCPs). In this study we focus on combinatorial constraints, in particular on restrictions on the number of switches on a fixed time grid. We propose a novel approach that is based on a decomposition of the MINLP into a NLP and a MILP. We discuss the relation of the MILP solution to the MINLP solution and formulate bounds for the gap between the two, depending on Lipschitz constants and the control discretization grid size. The MILP solution can also be used for an efficient initialization of the MINLP solution process. The speedup of the solution of the MILP compared to the MINLP solution is considerable already for general purpose MILP solvers. We analyze the structure of the MILP that takes switching constraints into account and propose a tailored Branch and Bound strategy that outperforms cplex on a numerical case study and hence further improves efficiency of our novel method.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abhishek K, Leyffer S, Linderoth J (2006) Filmint: an outer-approximation-based solver for nonlinear mixed integer programs. Preprint ANL/MCS-P1374-0906, Argonne National Laboratory, Mathematics and Computer Science Division
Applegate D, Bixby R, Chvátal V, Cook W, Espinoza D, Goycoolea M, Helsgaun K (2009) Certification of an optimal TSP tour through 85, 900 cities. Oper Res Lett 37(1): 11–15
Belotti P, Lee J, Liberti L, Margot F, Waechter A (2009) Branching and bounds tightening techniques for non-convex MINLP. Optim Methods Softw 24: 597–634
Bixby RE, Fenelon M, Gu Z, Rothberg E, Wunderling R (2004) Mixed-integer programming: a progress report. In: The sharpest cut: the impact of manfred padberg and his work. SIAM
Bonami P, Biegler L, Conn A, Cornuéjols G, Grossmann I, Laird C, Lee J, Lodi A, Margot F, Sawaya N, Wächter A (2009) An algorithmic framework for convex mixed integer nonlinear programs. Discr Optim 5(2): 186–204
Bonami P, Cornuejols G, Lodi A, Margot F (2009) Feasibility pump for mixed integer nonlinear programs. Math Program 199: 331–352
Bonami P, Kilinc M, Linderoth J (2009) Algorithms and software for convex mixed integer nonlinear programs. Technical Report 1664, University of Wisconsin
Burgschweiger J, Gnädig B, Steinbach M (2008) Optimization models for operative planning in drinking water networks. Optim Eng 10(1): 43–73 Online first
Christof T, Löbel A PORTA—polyhedron representation transformation algorithm http://www.zib.de/Optimization/Software/Porta/. PORTA Homepage
Christof T, Reinelt G (1996) Combinatorial optimization and small polytopes. TOP 4(1): 1–53
Floudas C, Akrotirianakis I, Caratzoulas S, Meyer C, Kallrath J (2005) Global optimization in the 21st century: advances and challenges. Comput Chem Eng 29(6): 1185–1202
Grossmann I (2002) Review of nonlinear mixed-integer and disjunctive programming techniques. Optim Eng 3: 227–252
Kameswaran S, Biegler L (2006) Simultaneous dynamic optimization strategies: recent advances and challenges. Comput Chem Eng 30: 1560–1575
Lee J, Leung J, Margot F (2004) Min-up/ min-down polytopes. Discr Optim 1: 77–85
Leineweber D, Bauer I, Bock H, Schlöder J (2003) An efficient multiple shooting based reduced SQP strategy for large-scale dynamic process optimization, Part I: theoretical aspects. Comput Chem Eng 27: 157–166
Margaliot M (2007) A counterexample to a conjecture of Gurvits on switched systems. IEEE Trans Automat Control 52(6): 1123–1126
Sager S (2005) Numerical methods for mixed–integer optimal control problems. Der andere Verlag, Tönning, Lübeck, Marburg ISBN 3-89959-416-9. Available at http://sager1.de/sebastian/downloads/Sager2005.pdf
Sager S (2009) Reformulations and algorithms for the optimization of switching decisions in nonlinear optimal control. J Process Control 19(8): 1238–1247
Sager S, Reinelt G, Bock H (2009) Direct methods with maximal lower bound for mixed-integer optimal control problems. Math Program 118(1): 109–149
Sager S, Bock H, Diehl M (2011) The integer approximation error in mixed-integer optimal control. Accepted by Mathematical Programming doi:10.1007/s10107-010-0405-3
Sharon Y, Margaliot M (2007) Third-order nilpotency, finite switchings and asymptotic stability. J Differ Equ 233: 135–150
Tawarmalani M, Sahinidis N (2002) Convexification and global optimization in continuous and mixed- integer nonlinear programming: theory, algorithms, software, and applications. Kluwer, Dordrecht
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sager, S., Jung, M. & Kirches, C. Combinatorial integral approximation. Math Meth Oper Res 73, 363–380 (2011). https://doi.org/10.1007/s00186-011-0355-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00186-011-0355-4