Bounded variation in binary sequences
1 : TU Dortmund, Fakultät für Mathematik
* : Corresponding author
Vogelpothsweg 87 44227 Dortmund -
Germany
In many applications it arises as a subproblem to optimize a linear function over a set of binary, finite-length vectors satisfying certain practical constraints, such as a minimum dwell time or a bound on the overall number of changes. While the former constraint has been studied intensively, no results seem to exist for the latter. We investigate two variants of the problem, depending on whether the number of changes in a switch is penalized in the objective function or whether it is bounded by a hard constraint. We show that, while the former variant is easy to deal with, the latter is more complex, but still tractable. We present a full polyhedral description of the set of feasible switchings for this case.