A comparative analysis of different dual problems in the Lagrangian Relaxation context for solving the Hydro Unit Commitment problem

One of the most attractive methods to solve large-scale combinatorial optimization problems is the Lagrangian Relaxation (LR). The LR can be seen as a broad range of techniques which supplies a lower bound of the objective function and good starting points for heuristic searches to obtain feasible primal solutions. In this paper, we are interested in one of the most intriguing questions related to LR which is the construction of the dual problem. To accomplish this task, we use the Hydro Unit Commitment and Loading (HUCL) problem. Two reasons justify the choice: (i) it is a large-scale nonlinear 0-1 programming problem; (ii) the problem is highly relevant to use the energy resources in an electrical energy system efficiently. By means of the HUCL, we apply different kinds of decompositions, in the LR context, to construct two distinct dual problems. The analyses are strictly based on numerical experiments and the ideas here presented are intended to encourage researchers in the optimization community to explore LR dualization in other practical and relevant problems. (c) 2013 Elsevier B.V. All rights reserved.