A Synergistic Combination of Surrogate Lagrangian Relaxation and Branch-and-Cut for Mixed-Integer Optimization Problems

Abstract: Mixed-integer optimization problems are prevalent in dynamic systems. Historically, Lagrangian relaxation and subgradient methods were used to solve such problems by exploiting separability through relaxing coupling constraints and decomposing relaxed problems into subproblems. Although subgradient methods have been widely used to update multipliers, they require the relaxed problem to be fully optimized, and this can be computationally expensive. Moreover, convergence can be slow because multipliers often zigzag across “ridges” of the dual function. The recent trend is to solve these problems by using the branch-and-cut method that exploits problem linearity. However, complex problems such as stochastic unit commitment or even the deterministic version with combined cycle units in power systems can pose major computational challenges. The reason is that cuts that define a convex hull, referred to as “facet-defining” or “strong” cuts, are problem-dependent and may be difficult to obtain. Complex transitions among combined cycle states associated with one unit, for example, are treated as global constraints, and affect the entire problem. Very recently, we developed the Surrogate Lagrangian Relaxation method where a proper direction to update multipliers can be obtained without optimally solving all subproblems with much reduced computational effort and multiplier zigzagging. More importantly, convergence to the optimum does not require the knowledge of the optimal dual value. This was achieved with a constructive process in which distances between Lagrange multipliers at consecutive iterations decrease, and as a result, multipliers converge to a unique limit. The decrease cannot be too large to avoid premature termination of the iterative updating process. To enable an efficient exploitation of separability as well as linearity, surrogate Lagrangian relaxation and branch-and-cut are synergistically combined where surrogate Lagrangian relaxation is used to decompose a problem into subproblems by relaxing coupling constraints, and each subproblem is solved by using branch-and-cut. With decomposition, the complexity of a subproblem is much smaller than that of the original problem. Constraints associated with a subproblem are handled locally and no longer affect the entire problem. Furthermore, by exploiting the novel observation that subproblem constraints and therefore the associated subproblem convex hulls remain unchanged after multipliers are updated, solving subproblems becomes much easier than starting from scratch. Numerical results on unit commitment with combined cycles demonstrated that the new approach is computationally efficient. The approach opens up a new direction for optimizing mixed integer optimization problems in power systems and beyond.