Integer linear programming for trust-region subproblems in integer optimal control with total variation regularization
No Thumbnail Available
Date
2025
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Alternative Title(s)
Abstract
In this work we concern ourselves with integer linear programs we obtain from a uniform discretization of subproblems arising in a trust-region algorithm for integer optimal control problems with total variation regularization. The underlying domain is either one-dimensional or two-dimensional and the control value set is a finite contiguous subset of the integers. We introduce several relaxations which not only provide lower bounds for our integer programming formulation but also allow us to obtain a conditional $p$-approximation.
We provide NP-hardness results which show that a more general version of the integer program obtained from a non-uniform discretization of the trust-region subproblem is NP-hard by a reduction from the knapsack problem. Furthermore, we conjecture the NP-hardness of the two-dimensional case even with a binary control value set. We support this conjecture by providing a reduction from the minimum bisection problem for grid graphs with an arbitrary number of holes which has been conjectured to be NP-hard for several decades.
We show that the polyhedron of the linear programming relaxation has a very special property. For vertex solutions we prove that non-integer values can only be attained in entry combinations subject to structural restrictions which also enforce that the fractional value attained in each of these entries is identical. This property is reminiscent of the solution for the relaxed knapsack problem in which at most one entry is fractional.
For the one-dimensional case we are able to provide a shortest path approach for the more general case of a non-uniform discretization with a corresponding integer program. This provides a pseudo-polynomial algorithm. For the two-dimensional case we employ an integer programming solver instead. We can use the one-dimensional case to calculate as well as improve good feasible points which allows for a primal heuristic. Furthermore, we supply a simple branching priority derived from the one-dimensional case. Based on the special property of the polyhedron, we derive cutting planes which make use of a connection to graph-based problems as well as the so-called minimum cut ratio. Finally, we extend a decomposition approach for the overall trust-region algorithm.
We validate our approaches with several numerical examples and note significant run time improvements for the one-dimensional and two-dimensional cases. We discuss under which conditions our approaches are especially effective but also argue their limitations.
Description
Table of contents
Keywords
Integer linear programming, Cutting planes, Optimal control, Graph theory
Subjects based on RSWK
Ganzzahlige Optimierung, Optimale Kontrolle, Trust-Region-Algorithmus, Graphentheorie