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

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

INFORMS Journal on Computing, 2025, vol. 37, issue 4, 1121-1141

Abstract: We analyze integer linear programs that we obtain after discretizing two-dimensional subproblems arising from a trust-region algorithm for mixed integer optimal control problems with total variation regularization. We discuss NP-hardness of the discretized problems and the connection to graph-based problems. We show that the underlying polyhedron exhibits structural restrictions in its vertices with regard to which variables can attain fractional values at the same time. Based on this property, we derive cutting planes by employing a relation to shortest-path and minimum bisection problems. We propose a branching rule and a primal heuristic which improves previously found feasible points. We validate the proposed tools with a numerical benchmark in a standard integer programming solver. We observe a significant speedup for medium-sized problems. Our results give hints for scaling toward larger instances in the future.

Keywords: mixed-integer programming; constrained minimum cut problems; cutting planes; Lagrangian relaxation; integer optimal control (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2024.0680 (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:37:y:2025:i:4:p:1121-1141

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 ().