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

Marvin Severitt () and Paul Manns ()
Additional contact information
Marvin Severitt: Faculty of Mathematics, TU Dortmund University, Dortmund 44227, Germany
Paul Manns: Faculty of Mathematics, TU Dortmund University, Dortmund 44227, Germany

INFORMS Journal on Computing, 2023, vol. 35, issue 4, 869-885

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.

Keywords: integer programming; resource-constrained shortest-path problems; A * algorithm; Lagrangian relaxation; integer optimal control (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.1294 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:35:y:2023:i:4:p:869-885

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().