The polytope of binary sequences with bounded variation

When addressing optimal control problems with binary switches varying over time, it often arises as a subproblem to optimize a linear function over the set of binary vectors of a given finite length satisfying certain practical constraints, such as a minimum dwell time or a bound on the number of switchings over the entire time horizon. While the former constraint has been investigated polyhedrally, no results seem to exist for the latter, although it arises naturally in many applications, e.g., when discretizing binary optimal control problems subject to a bounded total variation. 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 switching patterns in this case and devise a linear-time exact separation algorithm.



View The polytope of binary sequences with bounded variation