{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T07:55:30Z","timestamp":1769586930138,"version":"3.49.0"},"reference-count":56,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T00:00:00Z","timestamp":1648684800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["grant agreement No 647573)"],"award-info":[{"award-number":["grant agreement No 647573)"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Solving mixed-integer nonlinear programs (MINLPs) is hard from both a theoretical and practical perspective. Decomposing the nonlinear and the integer part is promising from a computational point of view. In general, however, no bounds on the objective value gap can be established and iterative procedures with potentially many subproblems are necessary. The situation is different for mixed-integer optimal control problems with binary variables that switch over time. Here, a priori bounds were derived for a decomposition into one continuous nonlinear control problem and one mixed-integer linear program, the combinatorial integral approximation (CIA) problem. In this article, we generalize and extend the decomposition idea. First, we derive different decompositions and analyze the implied a priori bounds. Second, we propose several strategies to recombine promising candidate solutions for the binary control functions in the original problem. We present the extensions for ordinary differential equations-constrained problems. These extensions are transferable in a straightforward way, though, to recently suggested variants for certain partial differential equations, for algebraic equations, for additional combinatorial constraints, and for discrete time problems. We implemented all algorithms and subproblems in AMPL for a proof-of-concept study. Numerical results show the improvement compared to the standard CIA decomposition with respect to objective function value and compared to general-purpose MINLP solvers with respect to runtime.<\/jats:p>","DOI":"10.3390\/a15040121","type":"journal-article","created":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T21:33:03Z","timestamp":1648762383000},"page":"121","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Combinatorial Integral Approximation Decompositions for Mixed-Integer Optimal Control"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3540-2897","authenticated-orcid":false,"given":"Clemens","family":"Zeile","sequence":"first","affiliation":[{"name":"Department of Mathematics, Otto-von-Guericke-Universit\u00e4t Magdeburg, 39106 Magdeburg, Germany"}]},{"given":"Tobias","family":"Weber","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Otto-von-Guericke-Universit\u00e4t Magdeburg, 39106 Magdeburg, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0283-9075","authenticated-orcid":false,"given":"Sebastian","family":"Sager","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Otto-von-Guericke-Universit\u00e4t Magdeburg, 39106 Magdeburg, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2022,3,31]]},"reference":[{"key":"ref_1","unstructured":"Egerstedt, M., Wardi, Y., and Delmotte, F. (2003, January 9\u201312). Optimal Control of Switching Times in Switched Dynamical Systems. Proceedings of the 42nd IEEE Concference of Decision and Control, Maui, HI, USA."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"726","DOI":"10.1109\/TAC.2006.875053","article-title":"Optimal control of continuous-time switched affine systems","volume":"51","author":"Seatzu","year":"2006","journal-title":"IEEE Trans. Autom. Control."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Buss, M., Glocker, M., Hardt, M., Stryk, O.V., Bulirsch, R., and Schmidt, G. (2002). Nonlinear Hybrid Dynamical Systems: Modelling, Optimal Control, and Applications, Springer.","DOI":"10.1007\/3-540-45426-8_18"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1109\/MCS.2008.931718","article-title":"Hybrid dynamical systems","volume":"29","author":"Goebel","year":"2009","journal-title":"IEEE Control. Syst."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2174\/1874114200903010014","article-title":"Nonlinear Programming Techniques for Operative Planning in Large Drinking Water Networks","volume":"3","author":"Burgschweiger","year":"2009","journal-title":"Open Appl. Math. J."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Doban, A.I., and Lazar, M. (2015, January 15\u201317). A switched systems approach to cancer therapy. Proceedings of the 2015 European Control Conference (ECC), Linz, Austria.","DOI":"10.1109\/ECC.2015.7330949"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Koch, T., Hiller, B., Pfetsch, M.E., and Schewe, L. (2015). Evaluating Gas Network Capacities, SIAM. Available online: https:\/\/archive.siam.org\/books\/mo21\/mo21_toc.pdf.","DOI":"10.1137\/1.9781611973693"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/s10957-005-5499-z","article-title":"Optimal Control for Traffic Flow Networks","volume":"126","author":"Gugat","year":"2005","journal-title":"J. Optim. Theory Appl."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1155","DOI":"10.1137\/040605503","article-title":"Combinatorial and Continuous Models for the Optimization of Traffic Flows on Networks","volume":"16","author":"Herty","year":"2006","journal-title":"SIAM J. Optim."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"B53","DOI":"10.1137\/15M1048197","article-title":"Partial Outer Convexification for Traffic Light Optimization in Road Networks","volume":"39","author":"Potschka","year":"2017","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_11","first-page":"675","article-title":"Optimal control for continuous supply network models","volume":"1","author":"Herty","year":"2007","journal-title":"Netw. Heterog. Media"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Abichandani, P., Benson, H., and Kam, M. (2008, January 11\u201313). Multi-vehicle path coordination under communication constraints. Proceedings of the American Control Conference, Seattle, WA, USA.","DOI":"10.1109\/ACC.2008.4586566"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"8503","DOI":"10.1021\/ie0601192","article-title":"A Nonlinear Programming Superstructure for Optimal Dynamic Operations of Simulated Moving Bed Processes","volume":"45","author":"Kawajiri","year":"2006","journal-title":"Ind. Eng. Chem. Res."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"211","DOI":"10.3182\/20060607-3-IT-3902.00039","article-title":"Dynamic Optimization of an Industrial Evaporator using Graph Search with Embedded Nonlinear Programming","volume":"39","author":"Sonntag","year":"2006","journal-title":"IFAC Proc. Vol."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"3508","DOI":"10.1007\/s10439-021-02848-2","article-title":"An Intra-Cycle Optimal Control Framework for Ventricular Assist Devices Based on Atrioventricular Plane Displacement Modeling","volume":"49","author":"Zeile","year":"2021","journal-title":"Ann. Biomed. Eng."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1002\/oca.778","article-title":"A variable time transformation method for mixed-integer optimal control problems","volume":"27","author":"Gerdts","year":"2006","journal-title":"Optim. Control. Appl. Methods"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"109325","DOI":"10.1016\/j.automatica.2020.109325","article-title":"Multiphase mixed-integer nonlinear optimal control of hybrid electric vehicles","volume":"123","author":"Robuschi","year":"2021","journal-title":"Automatica"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Lee, J., and Leyffer, S. (2012). A benchmark library of mixed-integer optimal control problems. Mixed Integer Nonlinear Programming, Springer.","DOI":"10.1007\/978-1-4614-1927-3"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Biegler, L., Campbell, S., and Mehrmann, V. (2012). Mixed-Integer DAE Optimal Control Problems: Necessary conditions and bounds. Control and Optimization with Differential-Algebraic Constraints, SIAM.","DOI":"10.1137\/9781611972252"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/j.conengprac.2008.07.005","article-title":"Look-ahead control for heavy trucks to minimize trip time and fuel consumption","volume":"17","author":"Ivarsson","year":"2009","journal-title":"Control. Eng. Pract."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1401","DOI":"10.1016\/S0005-1098(99)00050-3","article-title":"Control Parametrization Enhancing Technique for Optimal Discrete-Valued Control Problems","volume":"35","author":"Lee","year":"1999","journal-title":"Automatica"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"5407","DOI":"10.1109\/TAC.2017.2697681","article-title":"Second-Order Switching Time Optimization for Switched Dynamical Systems","volume":"62","author":"Stellato","year":"2017","journal-title":"IEEE Trans. Autom. Control."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1291","DOI":"10.1016\/j.conengprac.2004.04.003","article-title":"Applied Hybrid System Optimization: An Empirical Investigation of Complexity","volume":"12","author":"Till","year":"2004","journal-title":"Control. Eng. Pract."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1007\/s10107-016-1023-5","article-title":"On the time transformation of mixed integer optimal control problems using a consistent fixed integer control function","volume":"161","author":"Ringkamp","year":"2017","journal-title":"Math. Program."},{"key":"ref_25","unstructured":"Sager, S., Tetschke, M., and Zeile, C. (2022, February 15). A Numerical Study of Transformed Mixed-Integer Optimal Control Problems, Available online: http:\/\/www.optimization-online.org\/DB_FILE\/2020\/03\/7698.pdf."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/oca.751","article-title":"Solving mixed-integer optimal control problems by Branch&Bound: A case study from automobile test-driving with gear shift","volume":"26","author":"Gerdts","year":"2005","journal-title":"Optim. Control. Appl. Methods"},{"key":"ref_27","unstructured":"Sager, S. (2005). Numerical Methods for Mixed\u2013Integer Optimal Control Problems, Der Andere Verlag."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1007\/s10898-014-0156-4","article-title":"Efficient upper and lower bounds for global mixed-integer optimal control","volume":"61","author":"Sager","year":"2015","journal-title":"J. Glob. Optim."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s10107-007-0185-6","article-title":"Direct Methods With Maximal Lower Bound for Mixed-Integer Optimal Control Problems","volume":"118","author":"Sager","year":"2009","journal-title":"Math. Program."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/s10626-014-0187-5","article-title":"Optimal control of hybrid switched systems: A brief survey","volume":"25","author":"Zhu","year":"2015","journal-title":"Discret. Event Dyn. Syst."},{"key":"ref_31","unstructured":"Burgschweiger, J., Gn\u00e4dig, B., and Steinbach, M. (2022, February 15). Optimization Models for Operative Planning in Drinking Water Networks, Available online: file:\/\/\/C:\/Users\/MDPI\/Downloads\/ZR-04-48.pdf."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/s00186-011-0355-4","article-title":"Combinatorial Integral Approximation","volume":"73","author":"Sager","year":"2011","journal-title":"Math. Methods Oper. Res."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1153","DOI":"10.1007\/s11590-016-1011-y","article-title":"Error bounds for mixed integer nonlinear optimization problems","volume":"10","author":"Stein","year":"2016","journal-title":"Optim. Lett."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1017\/S0962492913000032","article-title":"Mixed-Integer Nonlinear Optimization","volume":"Volume 22","author":"Iserles","year":"2013","journal-title":"Acta Numerica"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1371","DOI":"10.1137\/18M1182917","article-title":"Approximation Properties and Tight Bounds for Constrained Mixed-Integer Optimal Control","volume":"58","author":"Kirches","year":"2016","journal-title":"SIAM J. Control. Optim."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/s10589-012-9518-3","article-title":"Relaxation Methods for Mixed-Integer Optimal Control of Partial Differential Equations","volume":"55","author":"Hante","year":"2013","journal-title":"Comput. Optim. Appl."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1103","DOI":"10.1002\/oca.2315","article-title":"Relaxation methods for hyperbolic PDE mixed-integer optimal control problems","volume":"38","author":"Hante","year":"2017","journal-title":"Optim. Control. Appl. Methods"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"6502","DOI":"10.1016\/j.ifacol.2020.12.1799","article-title":"pycombina: An open-source tool for solving combinatorial approximation problems arising in mixed-integer optimal control","volume":"53","author":"Zeile","year":"2020","journal-title":"IFAC-PapersOnLine"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Biegler, L. (2010). Nonlinear Programming: Concepts, Algorithms, and Applications to Chemical Processes, SIAM.","DOI":"10.1137\/1.9780898719383"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Gerdts, M. (2012). Optimal Control of ODEs and DAEs, De Gruyter.","DOI":"10.1515\/9783110249996"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10107-010-0405-3","article-title":"The Integer Approximation Error in Mixed-Integer Optimal Control","volume":"133","author":"Sager","year":"2012","journal-title":"Math. Program. A"},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"548","DOI":"10.1109\/LCSYS.2021.3082989","article-title":"Switching Cost Aware Rounding for Relaxations of Mixed-Integer Optimal Control Problems: The 2-D Case","volume":"6","author":"Bestehorn","year":"2021","journal-title":"IEEE Control. Syst. Lett."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1007\/s10107-020-01581-3","article-title":"Mixed-integer optimal control problems with switching costs: A shortest path approach","volume":"188","author":"Bestehorn","year":"2021","journal-title":"Math. Program."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"2645","DOI":"10.1137\/20M1377187","article-title":"Relaxed multibang regularization for the combinatorial integral approximation","volume":"59","author":"Manns","year":"2021","journal-title":"SIAM J. Control. Optim."},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Leyffer, S., and Manns, P. (2022, February 15). Sequential Linear Integer Programming for Integer Optimal Control with Total Variation Regularization, Available online: https:\/\/arxiv.org\/pdf\/2106.13453.pdf.","DOI":"10.1051\/cocv\/2022059"},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1007\/s10589-018-9993-2","article-title":"Combinatorial optimal control of semilinear elliptic PDEs","volume":"70","author":"Buchheim","year":"2018","journal-title":"Comput. Optim. Appl."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1007\/s10107-021-01656-9","article-title":"Penalty alternating direction methods for mixed-integer optimal control with combinatorial constraints","volume":"188","author":"Hante","year":"2021","journal-title":"Math. Program."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"990","DOI":"10.1109\/LCSYS.2019.2920425","article-title":"On the Mixed-Integer Linear-Quadratic Optimal Control With Switching Cost","volume":"3","year":"2019","journal-title":"IEEE Control. Syst. Lett."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"1238","DOI":"10.1016\/j.jprocont.2009.03.008","article-title":"Reformulations and Algorithms for the Optimization of Switching Decisions in Nonlinear Optimal Control","volume":"19","author":"Sager","year":"2009","journal-title":"J. Process. Control."},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Zeile, C. (2021). Combinatorial Integral Decompositions for Mixed-Integer Optimal Control. [Ph.D. Thesis, Otto\u2013von\u2013Guericke\u2013Universit\u00e4t Magdeburg].","DOI":"10.3390\/a15040121"},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1007\/s10107-020-01533-x","article-title":"Mixed-integer optimal control under minimum dwell time constraints","volume":"188","author":"Zeile","year":"2021","journal-title":"Math. Program."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1007\/s10589-020-00244-5","article-title":"On mixed-integer optimal control with constrained total variation of the integer control","volume":"78","author":"Sager","year":"2021","journal-title":"Comput. Optim. Appl."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1051\/cocv\/2019016","article-title":"Improved Regularity Assumptions for Partial Outer Convexification of Mixed-Integer PDE-Constrained Optimization Problems","volume":"26","author":"Manns","year":"2020","journal-title":"ESAIM Control. Optim. Calc. Var."},{"key":"ref_54","unstructured":"Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley Longman Publishing Co., Inc."},{"key":"ref_55","unstructured":"Fourer, R., Gay, D., and Kernighan, B. (2022, February 15). AMPL: A Modeling Language for Mathematical Programming, Available online: https:\/\/vanderbei.princeton.edu\/307\/textbook\/AMPLbook.pdf."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.jprocont.2019.05.016","article-title":"Design, Implementation and Simulation of an MPC algorithm for Switched Nonlinear Systems under Combinatorial Constraints","volume":"81","author":"Buerger","year":"2019","journal-title":"Process. Control."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/4\/121\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:47:51Z","timestamp":1760136471000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/4\/121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,31]]},"references-count":56,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2022,4]]}},"alternative-id":["a15040121"],"URL":"https:\/\/doi.org\/10.3390\/a15040121","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,31]]}}}