Generalized min-up/min-down polytopes

Cécile Rottner (1)

1 EDF R&D - EDF R&D

Consider a time horizon and a set of possible states for a given system. The system must be in exactly one state at a time. In this paper, we generalize classical results on min-up/min-down constraints for a 2-state system to an n-state system. The minimum-time constraints enforce that if the system switches to state i at time t, then it must remain in state i for a minimum number of time steps. The minimum-time polytope is defined as the convex hull of integer solutions satisfying the minimum-time constraints. A variant of minimum-time constraints is also considered, namely the no-spike constraints. They enforce that if state i is switched on at time t, the system must remain on states j ≥ i during a minimum time. Symmetrically, they enforce that if state i is switched off at time t, the system must remain on states j < i during a minimum time. The no-spike polytope is defined as the convex hull of integer solutions satisfying the no-spike constraints. For both the minimum-time polytope and the no-spike polytope, we introduce families of valid inequalities. We prove that these inequalities lead to a complete description of linear size for each polytope.

Domaines: Optimisation et contrôle [math.OC]

Cécile Rottner. Generalized min-up/min-down polytopes. 2023. ⟨hal-03938035⟩