{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T20:44:27Z","timestamp":1779914667901,"version":"3.53.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,12,7]],"date-time":"2020-12-07T00:00:00Z","timestamp":1607299200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,12,7]],"date-time":"2020-12-07T00:00:00Z","timestamp":1607299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["647573"],"award-info":[{"award-number":["647573"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["314838170"],"award-info":[{"award-number":["314838170"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["(647573)"],"award-info":[{"award-number":["(647573)"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012320","name":"Otto-von-Guericke-Universit\u00e4t Magdeburg","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100012320","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2021,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The<jats:italic>combinatorial integral approximation<\/jats:italic>(CIA) decomposition suggests solving mixed-integer optimal control problems by solving one continuous nonlinear control problem and one mixed-integer linear program (MILP). Unrealistic frequent switching can be avoided by adding a constraint on the total variation to the MILP. Within this work, we present a fast heuristic way to solve this CIA problem and investigate in which situations optimality of the constructed feasible solution is guaranteed. In the second part of this article, we show tight bounds on the integrality gap between a relaxed continuous control trajectory and an integer feasible one in the case of two controls. Finally, we present numerical experiments to highlight the proposed algorithm\u2019s advantages in terms of run time and solution quality.<\/jats:p>","DOI":"10.1007\/s10589-020-00244-5","type":"journal-article","created":{"date-parts":[[2020,12,7]],"date-time":"2020-12-07T12:03:56Z","timestamp":1607342636000},"page":"575-623","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["On mixed-integer optimal control with constrained total variation of the integer control"],"prefix":"10.1007","volume":"78","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0283-9075","authenticated-orcid":false,"given":"Sebastian","family":"Sager","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3540-2897","authenticated-orcid":false,"given":"Clemens","family":"Zeile","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,12,7]]},"reference":[{"issue":"1","key":"244_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s12532-018-0139-4","volume":"11","author":"JA Andersson","year":"2019","unstructured":"Andersson, J.A., Gillis, J., Horn, G., Rawlings, J.B., Diehl, M.: Casadi: a software framework for nonlinear optimization and optimal control. Math. Program. Comput. 11(1), 1\u201336 (2019)","journal-title":"Math. Program. Comput."},{"issue":"2","key":"244_CR2","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s10957-007-9305-y","volume":"136","author":"H Axelsson","year":"2008","unstructured":"Axelsson, H., Wardi, Y., Egerstedt, M., Verriest, E.: Gradient descent approach to optimal mode scheduling in hybrid dynamical systems. J. Optim. Theory Appl. 136(2), 167\u2013186 (2008)","journal-title":"J. Optim. Theory Appl."},{"key":"244_CR3","unstructured":"Bestehorn, F., Hansknecht, C., Kirches, C., Manns, P.: A switching cost aware rounding method for relaxations of mixed-integer optimal control problems (2019). http:\/\/www.optimization-online.org\/DB_FILE\/2019\/03\/7099.pdf. Accessed 25 Nov 2020"},{"key":"244_CR4","unstructured":"Bestehorn, F., Hansknecht, C., Kirches, C., Manns, P.: Mixed-integer optimal control problems with switching costs: A shortest path approach. submitted to Mathematical Programming B (2020). http:\/\/www.optimization-online.org\/DB_HTML\/2020\/02\/7630.html. Accessed 25 Nov 2020"},{"key":"244_CR5","unstructured":"Bock, H., Plitt, K.: A Multiple Shooting algorithm for direct solution of optimal control problems. In: Proceedings of the 9th IFAC World Congress, pp. 242\u2013247. Pergamon Press, Budapest (1984). http:\/\/www.iwr.uni-heidelberg.de\/groups\/agbock\/FILES\/Bock1984.pdf"},{"key":"244_CR6","unstructured":"Buerger, A., Zeile, C., Altmann-Dieses, A. Sager, S., Diehl, M.: An algorithm for mixed-integer optimal control of solar thermal climate systems with MPC-capable runtime (2018). https:\/\/ieeexplore.ieee.org\/document\/8550424"},{"key":"244_CR7","unstructured":"Buerger, A., Zeile, C., Altmann-Dieses, A. Sager, S., Diehl, M.: Design, implementation and simulation of an mpc algorithm for switched nonlinear systems under combinatorial constraints. Process Control 81, 15\u201330 (2019). https:\/\/mathopt.de\/PUBLICATIONS\/Buerger2019.pdf. Accessed 25 Nov 2020"},{"key":"244_CR8","doi-asserted-by":"crossref","unstructured":"B\u00fcrger, A., Zeile, C., Hahn, M., Altmann-Dieses, A., Sager, S., Diehl, M.: pycombina: An open-source tool for solving combinatorial approximation problems arising in mixed-integer optimal control (2020). Submitted","DOI":"10.1016\/j.ifacol.2020.12.1799"},{"issue":"4","key":"244_CR9","doi-asserted-by":"publisher","first-page":"990","DOI":"10.1109\/LCSYS.2019.2920425","volume":"3","author":"A De Marchi","year":"2019","unstructured":"De Marchi, A.: On the mixed-integer linear-quadratic optimal control with switching cost. IEEE Control Syst. Lett. 3(4), 990\u2013995 (2019)","journal-title":"IEEE Control Syst. Lett."},{"key":"244_CR10","doi-asserted-by":"crossref","unstructured":"Doban, A.I., Lazar, M.: A switched systems approach to cancer therapy. In: 2015 European Control Conference (ECC), pp. 2718\u20132724. IEEE (2015)","DOI":"10.1109\/ECC.2015.7330949"},{"issue":"3","key":"244_CR11","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1002\/oca.778","volume":"27","author":"M Gerdts","year":"2006","unstructured":"Gerdts, M.: A variable time transformation method for mixed-integer optimal control problems. Optim. Control Appl. Methods 27(3), 169\u2013182 (2006)","journal-title":"Optim. Control Appl. Methods"},{"key":"244_CR12","unstructured":"G\u00f6ttlich, S., Hante, F.M., Potschka, A., Schewe, L.: Penalty alternating direction methods for mixed-integer optimal control with combinatorial constraints. arXiv preprint arXiv:1905.13554 (2019)"},{"key":"244_CR13","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"RL Graham","year":"1979","unstructured":"Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.R.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287\u2013326 (1979)","journal-title":"Ann. Discrete Math."},{"key":"244_CR14","unstructured":"Jung, M.: Relaxations and Approximations for Mixed-Integer Optimal Control. Ph.D. thesis, University Heidelberg (2013). http:\/\/www.ub.uni-heidelberg.de\/archiv\/16036. Accessed 25 Nov 2020"},{"issue":"1","key":"244_CR15","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1080\/10556788.2014.890196","volume":"30","author":"M Jung","year":"2015","unstructured":"Jung, M., Reinelt, G., Sager, S.: The lagrangian relaxation for the combinatorial integral approximation problem. Optim. Methods Softw. 30(1), 54\u201380 (2015)","journal-title":"Optim. Methods Softw."},{"key":"244_CR16","unstructured":"Kirches, C.: Fast numerical methods for mixed-integer nonlinear model-predictive control. Ph.D. thesis, Ruprecht-Karls-Universit\u00e4t Heidelberg (2010). http:\/\/www.ub.uni-heidelberg.de\/archiv\/11636\/. Available at http:\/\/www.ub.uni-heidelberg.de\/archiv\/11636\/. Accessed 25 Nov 2020"},{"key":"244_CR17","unstructured":"Kirches, C., Kostina, E., Meyer, A., Schl\u00f6der, M.: Numerical solution of optimal control problems with switches, switching costs and jumps http:\/\/www.optimization-online.org\/DB_HTML\/2018\/10\/6888.html. Accessed 25 Nov 2020"},{"key":"244_CR18","first-page":"435","volume":"46","author":"M Kutta","year":"1901","unstructured":"Kutta, M.: Beitrag zur n\u00e4herungsweisen Integration totaler Differentialgleichungen. Zeitschrift f\u00fcr Mathematik und Physik 46, 435\u2013453 (1901)","journal-title":"Zeitschrift f\u00fcr Mathematik und Physik"},{"key":"244_CR19","unstructured":"Manns, P., Kirches, C.: Improved regularity assumptions for partial outer convexification of mixed-integer pde-constrained optimization problems. ESAIM: Control, Optimisation and Calculus of Variations (2019). http:\/\/www.optimization-online.org\/DB_HTML\/2018\/04\/6585.html. Accessed 18 Mar 2020"},{"key":"244_CR20","unstructured":"Rieck, R.M.: Discrete controls and constraints in optimal control problems. Ph.D. thesis, Technische Universit\u00e4t M\u00fcnchen (2017)"},{"issue":"1","key":"244_CR21","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/s10107-016-1023-5","volume":"161","author":"M Ringkamp","year":"2017","unstructured":"Ringkamp, M., Ober-Bl\u00f6baum, S., Leyendecker, S.: On the time transformation of mixed integer optimal control problems using a consistent fixed integer control function. Math. Program. 161(1), 551\u2013581 (2017). https:\/\/doi.org\/10.1007\/s10107-016-1023-5","journal-title":"Math. Program."},{"key":"244_CR22","doi-asserted-by":"publisher","first-page":"109325","DOI":"10.1016\/j.automatica.2020.109325","volume":"123","author":"N Robuschi","year":"2021","unstructured":"Robuschi, N., Zeile, C., Sager, S., Braghin, F., Cheli, F.: Multiphase mixed-integer nonlinear optimal control of hybrid electric vehicles. Automatica 123, 109325 (2021). https:\/\/doi.org\/10.1016\/j.automatica.2020.109325","journal-title":"Automatica"},{"issue":"2","key":"244_CR23","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/BF01446807","volume":"46","author":"CDT Runge","year":"1895","unstructured":"Runge, C.D.T.: \u00dcber die numerische Aufl\u00f6sung von Differentialgleichungen. Math. Ann. 46(2), 167\u2013178 (1895)","journal-title":"Math. Ann."},{"key":"244_CR24","unstructured":"Sager, S.: Numerical methods for mixed\u2013integer optimal control problems. Der andere Verlag, T\u00f6nning, L\u00fcbeck, Marburg (2005). https:\/\/mathopt.de\/PUBLICATIONS\/Sager2005.pdf. Accessed 18 Mar 2020"},{"key":"244_CR25","unstructured":"Sager, S.: A benchmark library of mixed-integer optimal control problems. In: J.\u00a0Lee, S.\u00a0Leyffer (eds.) Mixed Integer Nonlinear Programming, pp. 631\u2013670. Springer (2012). https:\/\/mathopt.de\/PUBLICATIONS\/Sager2012b.pdf. Accessed 18 Mar 2020"},{"key":"244_CR26","unstructured":"Sager, S., Bock, H., Diehl, M.: The Integer Approximation Error in Mixed-Integer Optimal Control. Mathematical Programming A 133(1\u20132), pp. 1\u201323 (2012). https:\/\/mathopt.de\/PUBLICATIONS\/Sager2012a.pdf. Accessed 18 Mar 2020"},{"key":"244_CR27","doi-asserted-by":"publisher","unstructured":"Sager, S., Jung, M., Kirches, C.: Combinatorial Integral Approximation. Mathematical Methods of Operations Research 73(3): 363\u2013380 (2011). https:\/\/doi.org\/10.1007\/s00186-011-0355-4. https:\/\/mathopt.de\/PUBLICATIONS\/Sager2011a.pdf. Accessed 18 Mar 2020","DOI":"10.1007\/s00186-011-0355-4"},{"key":"244_CR28","unstructured":"Sager, S., Reinelt, G., Bock, H.: Direct Methods With Maximal Lower Bound for Mixed-Integer Optimal Control Problems. Mathematical Programming 118(1), 109\u2013149 (2009). https:\/\/mathopt.de\/PUBLICATIONS\/Sager2009.pdf. Accessed 18 Mar 2020"},{"key":"244_CR29","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1080\/00207177508922030","volume":"21","author":"T Tsang","year":"1975","unstructured":"Tsang, T., Himmelblau, D., Edgar, T.: Optimal control via collocation and non-linear programming. Int. J. Control 21, 763\u2013768 (1975)","journal-title":"Int. J. Control"},{"issue":"1","key":"244_CR30","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/s10107-004-0559-y","volume":"106","author":"A W\u00e4chter","year":"2006","unstructured":"W\u00e4chter, A., Biegler, L.: On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106(1), 25\u201357 (2006)","journal-title":"Math. Program."},{"key":"244_CR31","doi-asserted-by":"publisher","unstructured":"Zeile, C., Rauwolf, T., Schmeisser, A., Mizerski, J. K., Braun-Dullaeus, R. C., Sager, S.: A Personalized Switched Systems Approach for the Optimal Control of Ventricular Assist Devices based on Atrioventricular Plane Displacement (2020). https:\/\/doi.org\/10.1101\/2020.05.27.119149","DOI":"10.1101\/2020.05.27.119149"},{"key":"244_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01533-x","author":"C Zeile","year":"2020","unstructured":"Zeile, C., Robuschi, N., Sager, S.: Mixed-integer optimal control under minimum dwell time constraints. Math. Program. (2020). https:\/\/doi.org\/10.1007\/s10107-020-01533-x","journal-title":"Math. Program."},{"key":"244_CR33","unstructured":"Zeile, C., Weber, T., Sager, S.: Combinatorial integral approximation decompositions for mixed-integer optimal control. submitted to Optimization Methods and Software (2018). http:\/\/www.optimization-online.org\/DB_HTML\/2018\/02\/6472.html. Submitted"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-020-00244-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-020-00244-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-020-00244-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,16]],"date-time":"2021-04-16T21:45:25Z","timestamp":1618609525000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-020-00244-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,7]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["244"],"URL":"https:\/\/doi.org\/10.1007\/s10589-020-00244-5","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,7]]},"assertion":[{"value":"21 October 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 November 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 December 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}