Efficient Solution of Discrete Subproblems Arising in Integer Optimal Control with Total Variation Regularization
INFORMS Journal on Computing · 2023-07 · 35 (4) · 869-885
DOI: 10.1287/ijoc.2023.1294 ↗Kurz gefasst
Fachartikel in der Zeitschrift INFORMS Journal on Computing, 2023-07. Verfasst von Marvin Severitt und 1 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 34 Literaturangaben.
Abstract (Originalsprache)
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 [Formula: see text] algorithm. Specifically, the analysis of a Lagrangian relaxation yields a consistent heuristic function for the [Formula: see text] algorithm and a preprocessing procedure, which can be employed to accelerate the [Formula: see text] 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 [Formula: see text] algorithm and topological sorting outperform a general-purpose IP solver significantly. Moreover, the accelerated [Formula: see text] 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. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms–Discrete. Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2023.1294 .
Zitieren
APA
Severitt, M., & Manns, P. (2023). Efficient Solution of Discrete Subproblems Arising in Integer Optimal Control with Total Variation Regularization. INFORMS Journal on Computing, 35(4), 869-885. https://doi.org/10.1287/ijoc.2023.1294
Vancouver
Severitt M, Manns P. Efficient Solution of Discrete Subproblems Arising in Integer Optimal Control with Total Variation Regularization. INFORMS Journal on Computing. 2023;35(4):869-885. doi:10.1287/ijoc.2023.1294
BibTeX
@article{Severitt2023,
author = {Severitt, Marvin and Manns, Paul},
title = {Efficient Solution of Discrete Subproblems Arising in Integer Optimal Control with Total Variation Regularization},
journal = {INFORMS Journal on Computing},
year = {2023},
volume = {35},
number = {4},
pages = {869--885},
doi = {10.1287/ijoc.2023.1294}
}
EUVIMED