On Discrete Subproblems in Integer Optimal Control with Total Variation Regularization in Two Dimensions.

This article focuses on the analysis and solution of integer linear programs arising from discretized two-dimensional trust-region subproblems in mixed integer optimal control problems (IOCPs) with total variation regularization. It establishes the strong NP-hardness of these discretized problems via a polynomial reduction from the minimum bisection problem on grid graphs with holes and reveals structural properties of the underlying polyhedron, notably that vertices can have fractional values only within a single connected component. Leveraging these insights, the authors develop cutting planes, a primal heuristic, and a branching rule to enhance integer programming solver performance, demonstrating significant computational speedups—up to 46%—on benchmark advection-diffusion problems. The study also shows equivalence between the linear relaxation and a Lagrangian relaxation of the problem, providing a conditional p-approximation guarantee, and discusses practical implications and future research directions for scaling and improving solution methods.