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

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.

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.