On Discrete Subproblems in Integer Optimal Control with Total Variation Regularization in Two Dimensions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913720760795136 |
|---|---|
| author | Manns, Paul Severitt, Marvin |
| author_facet | Manns, Paul Severitt, Marvin |
| contents | We analyze integer linear programs which 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 regards 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 towards larger instances in the future. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_09213 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On Discrete Subproblems in Integer Optimal Control with Total Variation Regularization in Two Dimensions Manns, Paul Severitt, Marvin Optimization and Control 90C11, 90C35, 49M37 We analyze integer linear programs which 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 regards 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 towards larger instances in the future. |
| title | On Discrete Subproblems in Integer Optimal Control with Total Variation Regularization in Two Dimensions |
| topic | Optimization and Control 90C11, 90C35, 49M37 |
| url | https://arxiv.org/abs/2403.09213 |