Parallel matheuristics for the discrete unit commitment problem with min‐stop ramping constraints

• Author: El‐ghazali Talbi,Nicolas Dupin
• Published date: 01 January 2020
• DOI: http://doi.org/10.1111/itor.12557
• Date: 01 January 2020

Intl. Trans. in Op. Res. 27 (2020) 219–244

DOI: 10.1111/itor.12557

INTERNATIONAL

TRANSACTIONS

IN OPERATIONAL

RESEARCH

Parallel matheuristics for the discrete unit commitment

problem with min-stop ramping constraints

Nicolas Dupin and El-ghazali Talbi

Centre de Rechercheen Informatique Signal et Automatique de Lille, University of Lille, UMR 9189, CRIStAL, F-59000,

Lille, France

E-mail: nicolas.dupin.2006@polytechnique.org [Dupin]; El-ghazali.Talbi@univ-lille1.fr [Talbi]

Received 31 October 2016; receivedin revised form 4 April 2018; accepted 12 April 2018

Abstract

The discrete unit commitment problem with min-stop ramping constraints optimizes the daily productionof

thermal power plants, subject to an operational reactivity of thermal units in a 30-minute delay. Previously,

mixed integer programming (MIP) formulations aimed at an exact optimizationapproach. This paper derives

matheuristics to face the short time limit imposed by the operational constraints. Continuous relaxations

guide the search for feasible solutions exploiting tailored variable fixing strategies. Parallel matheuristics are

derived considering complementary strategies in parallel. Tests were performed on more than 600 real-life

instances. Our parallel matheuristic provides high-quality solutions and outperforms the MIP approach in

the time limits imposed by the industrial application. This paper illustrates a special interest for matheuristics

in industrial highly constrained problems: many tailored neighborhood searches can be derived from an

MIP formulation, and their combination in a parallel scheme improves the solution quality as well as the

consistency of the heuristic.

Keywords: matheuristic; mixed integer programming; unit commitment problem; hybrid heuristics; variable fixing; LP-

guided heuristics; kernel search; parallel metaheuristics

1. Introduction

Energy management induces complex production problems as electricity is not storable on a large

scale. This means thata large volume of electricity needs to be generated at the time of consumption.

However, power stations are not always able to keep up with the fluctuating demand. The processof

dealing with power production and demand induces several levels of optimization problems from

strategic decisions in an uncertain environmentto daily production decisions (Renaud, 1993). These

problems come under the umbrella of unit commitment (UC) problems, which involve minimizing

the cost of the power generation and providing electricity according to the power demands and the

power generation constraints.

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies

Published by John Wiley & Sons Ltd, 9600 Garsington Road, Oxford OX4 2DQ, UK and 350 Main St, Malden, MA02148,

USA.

220 N. Dupin and E-g. Talbi / Intl. Trans. in Op. Res. 27 (2020) 219–244

Fig. 1. Illustration of the daily variations of power demands in the French unit commitment for severaltypes of day in

winter and summer: Global demand in megawattsis given on the y-axis and discretized time is given on the x-axis.

Source:RTE(R

´

aseau de Transport d’ ´

Electricit´

a), the electricity transmission system operator of France.

This paper presents a short-term UC problem within a time window of two days and using

a 30-minute discrete time step. This length-of-time step highlights demand peaks, as shown in

Fig. 1, for summer and winter days. The resulting UC problem to be solved is how to structure

modulation capacity (nominal production, primary, and secondary reserves) in the face of real-time

uncertainty. Hydroelectric dams are particularly suited to modulating production in real time.

These modulation capacities are limited, and reservoirs will at some point need to be refilled. The

aim of this study is to examine the extent to which France’s thermal energy sources are able to

modulate the power generation within 30 minutes. Thermal power stations are not able to react

quickly to demand changes due to certain dynamic constraints.

In this paper, we use the discretized UC problem (UCPd) with minimum stop and ramping

constraints for thermal units (Dupin, 2017). UCPd was modeled using a mixedinteger programming

(MIP) formulation. We will examine how to compute the best solutions to this problem within

the few minutes allowed by the industrial application. We investigate hybrid MIP optimization

with heuristics, with the aim of improving the limitations of a direct application of a generic

MIP solver.

This paper is organized as follows. In Section 2, wedescribe the constraints of the UCPd extending

the formulation of Dupin (2017). In Section 3, we discuss the related state-of-the-art elements. In

C

2018 The Authors.

International Transactionsin Operational Research C

2018 International Federation ofOperational Research Societies