Solving Certain Types of Large-Scale Scheduling Problems via Hybrid Decomposition 

We discuss an efficient solution method for the stochastic unit commitment problem, an important large-scale scheduling problem. Using a Benders framework, the solution method decomposes the problem into a mixed-integer linear master problem, and linear and continuous subproblems. The master problem corresponds to the first-stage decisions and includes all the scheduling variables and their corresponding constraints. The subproblems correspond to the actual operation of the production units. Based on the success of column-and-constraint generation algorithms to solve robust optimization problems, we improve the generally ineffective communication between the master problem and the subproblems in the standard Benders algorithm by adding primal variables and constraints from the subproblems to the master problem, which provides a better approximation of the recourse function. Our computational experiments demonstrate the effectiveness of this hybrid decomposition method.