  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.
