On Discrete Subproblems in Integer Optimal Control with Total Variation Regularization in Two Dimensions

References

• Alnæs MS, Logg A, Ølgaard KB, Rognes ME, Wells GN (2014) Unified form language: A domain-specific language for weak formulations of partial differential equations. ACM Trans. Math. Software 40(2):1–37.Google Scholar
• Armon A, Zwick U (2006) Multicriteria global minimum cuts. Algorithmica 46:15–26.Crossref, Google Scholar
• Baratta IA, Dean JP, Dokken JS, Habera M, Hale JS, Richardson CN, Rognes ME, et al. (2023) DOLFINx: The next generation FEniCS problem solving environment. Zenodo (December 31), http://dx.doi.org/10.5281/zenodo.10447666.Google Scholar
• Bestehorn F, Hansknecht C, Kirches C (2021) Mixed-integer optimal control problems with switching costs: A shortest path approach. Math. Programming 188:621–652.Crossref, Google Scholar
• Boykov Y, Kolmogorov V (2004) An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Trans. Pattern Anal. Machine Intelligence 26(9):1124–1137.Crossref, Google Scholar
• Buchheim C, Grütering A, Meyer C (2024) Parabolic optimal control problems with combinatorial switching constraints: Part III: Branch-and-bound algorithm. Preprint, submitted January 18, https://arxiv.org/abs/2401.10018.Google Scholar
• Burger M, Dong Y, Hintermüller M (2012) Exact relaxation for classes of minimization problems with binary constraints. Preprint, submitted October 28, https://arxiv.org/abs/1210.7507.Google Scholar
• Bürger A, Zeile C, Altmann-Dieses A, Sager S, Diehl M (2018) An algorithm for mixed-integer optimal control of solar thermal climate systems with MPC-capable runtime. Proc. Eur. Control Conf. (IEEE, Piscataway, NJ), 1379–1385.Google Scholar
• Cristinelli G, Iglesias JA, Walter D (2023) Conditional gradients for total variation regularization with PDE constraints: A graph cuts approach Preprint, submitted October 30, https://arxiv.org/abs/2310.19777.Google Scholar
• De Marchi A (2019) On the mixed-integer linear-quadratic optimal control with switching cost. IEEE Control Systems Lett. 3(4):990–995.Crossref, Google Scholar
• De Simone C, Diehl M, Jünger M, Mutzel P, Reinelt G, Rinaldi G (1995) Exact ground states of Ising spin glasses: New experimental results with a branch-and-cut algorithm. J. Statist. Phys. 80:487–496.Crossref, Google Scholar
• Díaz J, Mertzios GB (2017) Minimum bisection is NP-hard on unit disk graphs. Inform. Comput. 256:83–92.Crossref, Google Scholar
• Feldmann AE, Widmayer P (2011) An O(n4) time algorithm to compute the bisection width of solid grid graphs. Demetrescu C, Halldórsson MM, eds. Algorithms ESA 2011, Lecture Notes in Computer Science, vol. 6942 (Springer, Berlin), 143–154.Crossref, Google Scholar
• Gerdts M (2005) Solving mixed-integer optimal control problems by branch & bound: A case study from automobile test-driving with gear shift. Optimal Control Appl. Methods 26:1–18.Crossref, Google Scholar
• Greig DM, Porteous BT, Seheult AH (1989) Exact maximum a posteriori estimation for binary images. J. Roy. Statist. Soc. Ser. B Statist. Methodology 51(2):271–279.Crossref, Google Scholar
• Gurobi Optimization LLC (2023) Gurobi Optimizer reference manual. Accessed October 11, 2024, https://www.gurobi.com.Google Scholar
• Hahn M, Kirches C, Manns P, Sager S, Zeile C (2021) Decomposition and approximation for PDE-constrained mixed-integer optimal control. Non-Smooth and Complementarity-Based Distributed Parameter Systems: Simulation and Hierarchical Optimization (Springer, Berlin), 283–305.Google Scholar
• Hante FM, Leugering G, Martin A, Schewe L, Schmidt M (2017) Challenges in optimal control problems for gas and fluid flow in networks of pipes and canals: From modeling to industrial applications. Industrial Mathematics and Complex Systems (Springer, Berlin), 77–122.Crossref, Google Scholar
• Jakob W, Rhinelander J, Moldovan D (2017) pybind11: Seamless operability between C++11 and Python. https://github.com/pybind/pybind11.Google Scholar
• Korte B, Vygen J (2018) Combinatorial Optimization, 6th ed. (Springer, Berlin).Google Scholar
• Leyffer S, Manns P (2022) Sequential linear integer programming for integer optimal control with total variation regularization. ESAIM Control Optim. Calculus Variations 28:66.Crossref, Google Scholar
• Loxton R, Lin Q, Padula F, Ntogramatzidis L (2020) Minimizing control volatility for nonlinear systems with smooth piecewise-quadratic input signals. Systems Control Lett. 145:104797.Crossref, Google Scholar
• Manns P, Schiemann A (2023) On integer optimal control with total variation regularization on multidimensional domains. SIAM J. Control Optim. 61(6):3415–3441.Crossref, Google Scholar
• Manns P, Severitt M (2024) On discrete subproblems in integer optimal control with total variation regularization in two dimensions. http://dx.doi.org/10.1287/ijoc.2024.0680.cd, https://github.com/INFORMSJoC/2024.0680.Google Scholar
• Marko J, Wachsmuth G (2023) Integer optimal control problems with total variation regularization: Optimality conditions and fast solution of subproblems. ESAIM Control Optim. Calculus Variations 29:81.Crossref, Google Scholar
• Nieuwenhuis C, Töppe E, Cremers D (2013) A survey and comparison of discrete and continuous multilabel approaches for the Potts model. Internat. J. Comput. Vision 104:223–240.Crossref, Google Scholar
• Papadimitriou CH, Sideri M (1996) The bisection width of grid graphs. Math. Systems Theory 29:97–110.Crossref, Google Scholar
• Papadimitriou CH, Yannakakis M (2000) On the approximability of trade-offs and optimal access of web sources. Proc. 41st Annual Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 86–92.Google Scholar
• Sager S, Jung M, Kirches C (2011) Combinatorial integral approximation. Math. Methods Oper. Res. 73(3):363–380.Crossref, Google Scholar
• Scroggs MW, Baratta IA, Richardson CN, Wells GN (2022a) Basix: A runtime finite element basis evaluation library. J. Open Source Software 7(73):3982.Crossref, Google Scholar
• Scroggs MW, Dokken JS, Richardson CN, Wells GN (2022b) Construction of arbitrary order finite element degree-of-freedom maps on polygonal and polyhedral cell meshes. ACM Trans. Math. Software 48(2):18:1–18:23.Google Scholar
• Severitt M, Manns P (2023) Efficient solution of discrete subproblems arising in integer optimal control with total variation regularization. INFORMS J. Comput. 35(4):869–885.Link, Google Scholar
• Soler M, Kamgarpour M, Lloret J, Lygeros J (2016) A hybrid optimal control approach to fuel-efficient aircraft conflict avoidance. IEEE Trans. Intelligent Transportation Systems 17(7):1826–1838.Crossref, Google Scholar
• Veksler O (1999) Efficient graph-based energy minimization methods in computer vision. PhD thesis, Cornell University, Ithaca, NY.Google Scholar