Novel exploitation of convex hull invariance for solving unit commitment by using surrogate Lagrangian relaxation and branch-and-cut

Many important problems in power systems, including unit commitment and economic dispatch (UCED), are modeled as MILP problems which are computationally intensive. Such problems can often be viewed as subsystems coupled by system-wide constraints. These structures have been efficiently exploited by surrogate Lagrangian relaxation and branch-and-cut to solve UCED problems with combined cycle units by relaxing system-wide coupling constraints, decomposing the relaxed problem into subproblems, and solving each subproblem by branch-and-cut. However, while complicated features of a subproblem are handled locally within that subproblem, there is no guarantee that each subproblem can be efficiently solved because corresponding convex hulls are generally difficult to obtain, and the overall computational effort may be significant. In this paper, this difficulty is alleviated by the novel exploitation of the invariance of subproblem constraints and the associated convex hulls with respect to updating of Lagrange multipliers. Consequently, cuts remain valid throughout the entire iterative process. When cuts are retained, solving subproblems in subsequent iterations becomes easier than starting from scratch. This idea is operationalized in CPLEX by using C Concert Technology to extract, save and load CPLEX-generated cuts by using callable libraries. Numerical results demonstrate that the new approach is computationally efficient and generates good feasible solutions.