×

Solving the electricity production planning problem by a column generation based heuristic. (English) Zbl 1280.90137

Summary: This paper presents a heuristic method based on column generation for the EDF (Electricité De France) long-term electricity production planning problem proposed as subject of the ROADEF/EURO 2010 Challenge. This is to our knowledge the first-ranked method among those methods based on mathematical programming, and was ranked fourth overall. The problem consists in determining a production plan over the whole time horizon for each thermal power plant of the French electricity company, and for nuclear plants, a schedule of plant outages which are necessary for refueling and maintenance operations. The average cost of the overall outage and production planning, computed over a set of demand scenarios, is to be minimized. The method proceeds in two stages. In the first stage, dates for outages are fixed once for all for each nuclear plant. Data are aggregated with a single average scenario and reduced time steps, and a set-partitioning reformulation of this aggregated problem is solved for fixing outage dates with a heuristic based on column generation. The pricing problem associated with each nuclear plant is a shortest path problem in an appropriately constructed graph. In the second stage, the reload level is determined at each date of an outage, considering now all scenarios. Finally, the production quantities between two outages are optimized for each plant and each scenario by solving independent linear programming problems.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
90B90 Case-oriented studies in operations research
90C10 Integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baldacci, R., Christophides, N., & Mingozzi, A. (2008). An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Mathematical Programming, 351-385. · Zbl 1279.90139
[2] Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1996). Branch-and-price: column generation for solving huge integer programs. Operations Research, 46, 316-329. · Zbl 0979.90092 · doi:10.1287/opre.46.3.316
[3] Desaulniers, G., Desrosiers, J., & Solomon, M. M. (2005). GERAD. Column generation. Berlin: Springer. · Zbl 1084.90002 · doi:10.1007/b135457
[4] Dubost, L., Gonzalez, R., & Lemaréchal, C. (2005). A primal-proximal heuristic applied to the French unit-commitment problem. Mathematical Programming, 104(1), 129-151. · Zbl 1077.90083 · doi:10.1007/s10107-005-0593-4
[5] Finardi, E. C., da Silva, E. L., & Sagastizàbal, C. (2005). Solving the unit commitment problem of hydropower plants via Lagrangian relaxation and sequential quadratic programming. Computational and Applied Mathematics, 24, 317-342. · Zbl 1213.90272 · doi:10.1590/S0101-82052005000300001
[6] Frangioni, A., Gentile, C., & Lacalandra, F. (2008). Solving unit commitment problems with general ramp constraints. International Journal of Electrical Power & Energy Systems, 30(5), 316-326. · doi:10.1016/j.ijepes.2007.10.003
[7] Kallrath, J., Pardalos, P. M., Rebennack, S., & Scheidt, M. (2009). Optimization in the energy industry. · Zbl 1157.90003 · doi:10.1007/978-3-540-88965-6
[8] Kazarlis, S. A., Bakirtzis, A. G., & Petridis, V. (1996). A genetic algorithm approach to solve the unit commitment problem. IEEE Transactions on Power Systems, 11, 83-92. · doi:10.1109/59.485989
[9] Khemmoudj, M. I.; Porcheron, M.; Bennaceur, H., When constraints programming and local search solve the scheduling problem of edf nuclear power plant aoutages, 271-283 (2006)
[10] Lubbecke, M. E., & Desrosiers, J. (2005). Selected topics in column generation. Operations Research, November-December, 1007-1023. · Zbl 1165.90578 · doi:10.1287/opre.1050.0234
[11] Lusby, R., Muller, L. F., & Petersen, B. (2010). A solution approach to the roadef/euro 2010 challenge based on benders decomposition. Technical report.
[12] Porcheron, M., Gorge, A., Juen, O., Simovic, T., & Dereu, G. (2010). EDF R&D, Challenge roadef/euro 2010: a large-scale energy management problem with varied constraints.
[13] Wagelmans, A., van Hoesel, S., & Kolen, A. (1992). Economic lot sizing: an o(nlogn) algorithm that runs in linear time in the Wagner-Whitin case. Operations Research, 40, 145-156. · Zbl 0771.90031 · doi:10.1287/opre.40.1.S145
[14] Wagner, H. M., & Whitin, T. M. (1958). Dynamic version of the economic lot size model. Management Science, 5, 89-96. · Zbl 0977.90500 · doi:10.1287/mnsc.5.1.89
[15] Wolsey, L. A. (1998). Integer programming. · Zbl 0930.90072
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.