Bounded variation in binary sequences
Maja Hügging  1, *@  , Christoph Buchheim  1, *@  
1 : TU Dortmund, Fakultät für Mathematik
Vogelpothsweg 87 44227 Dortmund -  Germany
* : Corresponding author

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.


Online user: 2 Privacy
Loading...