A polyhedral study on unit commitment with a single type of binary variables

Abstract

Efficient power production scheduling is a crucial concern for power system operators aiming to minimize the operational costs. Previous studies have primarily focused on Mixed-integer Linear Programming (MILP) formula­tions that utilize two or three types of binary variables for Unit Commit­ment (UC) problems. The investigation of strong formulations with a single type of binary variables has been limited, as it is believed to be challenging to derive strong valid inequalities for them (James Ostrowski, Anjos, and Vannelli 2012) and the improvement of compactness is often accompanied by a compromise in tightness (Ben Knueven, Jim Ostrowski, and J. Wang 2018). To address these difficulties, we consider a compact formulation for the UC problem using a single type of binary variables, which reduces the size of the search tree for the branch-and-cut algorithm. To enhance the tightness of this compact formulation, two-period UC polytope and multi-period strong valid inequalities involving single and two continuous variables are developed. Conditions under which these strong valid inequalities serve as facet-defining inequalities for the multi-period UC polytope are provided. As the number of these inequalities could be large, polynomial separation algorithms are proposed to find most violated inequalities. The efficacy of the derived strong valid inequalities in tightening the compact formulation is demonstrated through computational experiments on network-constrained UC problems. The result indicates that our strong valid inequalities can speed up the solution process of the compact formulation significantly. Par­ticularly, our strong valid inequalities can also be used to tighten two/three-­binary UC formulations.