IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v35y2023i4p869-885.html
   My bibliography  Save this article

Efficient Solution of Discrete Subproblems Arising in Integer Optimal Control with Total Variation Regularization

Author

Listed:
  • Marvin Severitt

    (Faculty of Mathematics, TU Dortmund University, Dortmund 44227, Germany)

  • Paul Manns

    (Faculty of Mathematics, TU Dortmund University, Dortmund 44227, Germany)

Abstract

We consider a class of integer linear programs (IPs) that arise as discretizations of trust-region subproblems of a trust-region algorithm for the solution of control problems, where the control input is an integer-valued function on a one-dimensional domain and is regularized with a total variation term in the objective, which may be interpreted as a penalization of switching costs between different control modes. We prove that solving an instance of the considered problem class is equivalent to solving a resource-constrained shortest-path problem (RCSPP) on a layered directed acyclic graph. This structural finding yields an algorithmic solution approach based on topological sorting and corresponding run-time complexities that are quadratic in the number of discretization intervals of the underlying control problem, the main quantifier for the size of a problem instance. We also consider the solution of the RCSPP with an A * algorithm. Specifically, the analysis of a Lagrangian relaxation yields a consistent heuristic function for the A * algorithm and a preprocessing procedure, which can be employed to accelerate the A * algorithm for the RCSPP without losing optimality of the computed solution. We generate IP instances by executing the trust-region algorithm on several integer optimal control problems. The numerical results show that the accelerated A * algorithm and topological sorting outperform a general-purpose IP solver significantly. Moreover, the accelerated A * algorithm is able to outperform topological sorting for larger problem instances. We also give computational evidence that the performance of the superordinate trust-region algorithm may be improved if it is initialized with a solution obtained with the combinatorial integral approximation.

Suggested Citation

  • Marvin Severitt & Paul Manns, 2023. "Efficient Solution of Discrete Subproblems Arising in Integer Optimal Control with Total Variation Regularization," INFORMS Journal on Computing, INFORMS, vol. 35(4), pages 869-885, July.
    • Handle: RePEc:inm:orijoc:v:35:y:2023:i:4:p:869-885
    DOI: 10.1287/ijoc.2023.1294
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2023.1294
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2023.1294?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Falk Hante & Sebastian Sager, 2013. "Relaxation methods for mixed-integer optimal control of partial differential equations," Computational Optimization and Applications, Springer, vol. 55(1), pages 197-225, May.
    2. Sebastian Sager & Michael Jung & Christian Kirches, 2011. "Combinatorial integral approximation," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 73(3), pages 363-380, June.
    3. Sebastian Sager & Clemens Zeile, 2021. "On mixed-integer optimal control with constrained total variation of the integer control," Computational Optimization and Applications, Springer, vol. 78(2), pages 575-623, March.
    4. Sven Leyffer & Paul Manns & Malte Winckler, 2021. "Convergence of sum-up rounding schemes for cloaking problems governed by the Helmholtz equation," Computational Optimization and Applications, Springer, vol. 79(1), pages 193-221, May.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Sven Leyffer & Paul Manns & Malte Winckler, 2021. "Convergence of sum-up rounding schemes for cloaking problems governed by the Helmholtz equation," Computational Optimization and Applications, Springer, vol. 79(1), pages 193-221, May.
    2. Christoph Buchheim & Renke Kuhlmann & Christian Meyer, 2018. "Combinatorial optimal control of semilinear elliptic PDEs," Computational Optimization and Applications, Springer, vol. 70(3), pages 641-675, July.
    3. S. Göttlich & A. Potschka & C. Teuber, 2019. "A partial outer convexification approach to control transmission lines," Computational Optimization and Applications, Springer, vol. 72(2), pages 431-456, March.
    4. Pipicelli, Michele & Muccillo, Massimiliano & Gimelli, Alfredo, 2023. "Influence of the control strategy on the performance of hybrid polygeneration energy system using a prescient model predictive control," Applied Energy, Elsevier, vol. 329(C).
    5. Dominik Garmatter & Margherita Porcelli & Francesco Rinaldi & Martin Stoll, 2023. "An improved penalty algorithm using model order reduction for MIPDECO problems with partial observations," Computational Optimization and Applications, Springer, vol. 84(1), pages 191-223, January.
    6. Falk M. Hante & Martin Schmidt, 2019. "Complementarity-based nonlinear programming techniques for optimal mixing in gas networks," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 7(3), pages 299-323, September.
    7. Frison, Lilli & Kollmar, Manuel & Oliva, Axel & Bürger, Adrian & Diehl, Moritz, 2024. "Model predictive control of bidirectional heat transfer in prosumer-based solar district heating networks," Applied Energy, Elsevier, vol. 358(C).
    8. Sebastian Sager & Mathieu Claeys & Frédéric Messine, 2015. "Efficient upper and lower bounds for global mixed-integer optimal control," Journal of Global Optimization, Springer, vol. 61(4), pages 721-743, April.
    9. Falk Hante & Sebastian Sager, 2013. "Relaxation methods for mixed-integer optimal control of partial differential equations," Computational Optimization and Applications, Springer, vol. 55(1), pages 197-225, May.
    10. Sebastian Sager & Clemens Zeile, 2021. "On mixed-integer optimal control with constrained total variation of the integer control," Computational Optimization and Applications, Springer, vol. 78(2), pages 575-623, March.
    11. Martin Siebenborn, 2018. "A Shape Optimization Algorithm for Interface Identification Allowing Topological Changes," Journal of Optimization Theory and Applications, Springer, vol. 177(2), pages 306-328, May.
    12. Yan-Chao Liang & Jane J. Ye, 2021. "Optimality Conditions and Exact Penalty for Mathematical Programs with Switching Constraints," Journal of Optimization Theory and Applications, Springer, vol. 190(1), pages 1-31, July.
    13. Bürger, Adrian & Bohlayer, Markus & Hoffmann, Sarah & Altmann-Dieses, Angelika & Braun, Marco & Diehl, Moritz, 2020. "A whole-year simulation study on nonlinear mixed-integer model predictive control for a thermal energy supply system with multi-use components," Applied Energy, Elsevier, vol. 258(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:35:y:2023:i:4:p:869-885. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.