Lagrangian Methods and Dynamic Programming Based MIP Formulations for the Unit Commitment Problem

Exactly solving hard optimization problems, in particular those mixing both nonlinear components and combinatorial ones, crucially requires the ability to derive tight bounds on the optimal value, which are obtained via relaxations. A fundamental trade-off exists between the tightness of the bound, which is important to avoid the explosion of the number of nodes in B&B approaches and better drive the heuristics and the branching decisions, and the cost of the solution of the continuous relaxation. This is in particular true because "strong" relaxations (providing tight bounds) are also very often "large" ones, i.e., with a very large–often exponential–number of variables and/or constraints. Navigating this trade-off is crucial to develop overall efficient solution algorithms, especially since apparently minor aspects may have a disproportionate large impacts depending on the fine details of the computational environment in which the algorithm is implemented. This Chapter provides an extensive illustration of this process using as test bed the Unit Commitment problem in electrical power production. In particular we will review several Mixed-Integer NonLinear formulations of (some of the most common variants of) the problem, with different trade-offs between size and "tightness", as well as algorithms for the efficient solutions of single-unit versions of the problem that motivate Lagrangian approaches. We will then compare the different variants, mostly in terms of their running time vs. the quality of the provided bound, in the context of a state-of-the-art software implementation, highlighting the several nontrivial choices that have to be navigated in order to choose the best approach for each given application.