A solution approach to the ROADEF/EURO 2010 challenge based on Benders' Decomposition

We present a Benders’ decomposition based framework for solving a large scale energy management problem with varied constraints posed as the ROADEF/EURO 2010 challenge. Because of the nature of the problem, not all constraints can be modeled satisfactorily as linear constraints and the approach is therefore divided into two stages: in the first stage Benders feasibility and optimality cuts are added based on the linear programming relaxation of the Benders Master problem, and in the second stage feasible integer solutions are enumerated and procedure is applied to each solution in an attempt to make them satisfy the constraints not part of the mixed integer program.

A number of experiments are performed on the available benchmark instances. These experiments show that the approach is competitive on the smaller instances, but not for the larger ones. We believe the exact approach gives insight into the problem and additionally makes it possible to find lower bounds on the problem, which is typically not the case for the competing heuristics.