Bounding the Convex Hull Relaxation of the Unit Commitment Problem with the Shapley-Folkman Theorem

The Unit Commitment (UC) problem finds an optimal schedule for a set of generators by minimizing the total operation cost subject to demand and operational constraints. The UC problem is often modeled with a mixed-integer linear program (MILP). We employ the Shapley-Folkman Theorem to provide a bound on the size of fractional solutions of its convex hull relaxation. This result is used to obtain a bound on the optimality gap between the MILP and the convex hull relaxation, which is further tightened using several problem-specific properties of UC. We conduct extensive numerical experiments to study the tightness of this threshold, and how it is impacted by different parameters.