DIMACS Workshop on Next Generation of Unit Commitment Models

September 27 - 28, 1999
DIMACS Center, Rutgers University, Piscataway, NJ

Mike Rothkopf, Rutgers University, RUTCOR, rothkopf@rutcor.rutgers.edu
Ben F. Hobbs, Johns Hopkins University, bhobbs@jhu.edu
Hung-Po Chao, Electric Power Research Institute, hchao@epri.com
Co-sponsored by DIMACS and EPRI.

Presented under the auspices of the Special Year on Large Scale Discrete Optimization.

For many years, the electric power industry has been using methods to help them solve the unit commitment problem. The result has been savings of tens and perhaps hundreds of millions of dollars in fuel costs. However, things are changing. Optimization technology is improving and the industry is undergoing radical restructuring. Consequently, the role of commitment models is changing and the value of the improved solutions that better algorithms might yield is increasing. The purpose of this conference is to explore the technology and needs of the next generation of computer models for aiding unit commitment decisions.

The unit commitment problem can be defined as the scheduling of production from power generation units over a daily to weekly time horizon in order to accomplish some objective. The problem solution must respect both generator constraints (such as ramp rate limits and minimum up or down times) and system constraints (reserve and energy requirements and, potentially, transmission constraints). The objective function should account for costs associated with energy production and start-up and shut-down decisions, along with possible revenue or customer impacts of those decisions. The resulting problem is a large scale nonlinear integer program.

Because of the problem's size and complexity, and because of the large economic benefits that could result from its improved solution, considerable attention has been devoted to algorithm development. Heuristics such as "priority lists" have long been used by industry; but in the last three decades, more systematic procedures based on a variety of algorithms have been proposed and tested. These techniques have include dynamic programming, branch-and-bound mixed integer programming, linear and network programming approaches, and Benders decomposition methods, among others. Recently, metaheuristic methods have been tested, such as genetic programming and simulated annealing, along with expert systems and neural networks. However, the solution approach that has been most successful, and which is most widely used at present, is Lagrangian relaxation. This procedure decomposes the problem by multiplying constraints that couple different generators (such as energy demand and reserve constraints) by Lagrangian multipliers and placing them in the objective function. Given a set of multiplier values, the problem is then separable in the generating units, and a dynamic program of low dimension can be used to obtain a trial schedule for each unit. A process of multiplier adjustment is used to search for feasible near-optimal solutions.

Lagrangian relaxation has proven useful for quick development of good, if not optimal, generator schedules. However, recent improvements in integer programming codes and other algorithms suggest that it may be possible to find better solutions more rapidly. Meanwhile, restructuring has sharpened the appetite of generation owners for more efficient operation. In the past, utilities have been regulated on a cost-plus basis, and so may not have put as much priority on squeezing out the last few percent improvements in the objective function. Furthermore, system operators realized that cost functions were approximate and so were perhaps more likely to be satisfied with good solutions that were technically suboptimal. Now, with restructuring, we have schedule coordinators making commitment decisions in a market environment, and ISOs dealing with bids. Bids are precise, and small improvements in solutions can result in significant changes in payments to bidders. Further, the fact that optimization models are, in some cases, being used to determine which generators will be operated and thus paid implies that there is a greater incentive to get exact answers to make the bidding process legitimate (and to disempower the bid taker).

In other words, it's a whole new world, and a reconsideration of how unit commitment models are solved and the purposes for which they are used is needed. The goal of this workshop is to bring together those who know the problem and what is needed with those who know what improvements in algorithms are really possible.

The workshop will start with a series of in-depth presentations by top experts in algorithms and utility systems operations. Then working groups will convene to define the new roles that unit commitment models may play and promising directions in algorithm development and application. The products of the workshop will be an EPRI report and journal articles summarizing deliberations and presenting its conclusions. The intent of the workshop sponsors is that this workshop will ultimately result in better algorithms yielding more value to their users.

Next: Call for Participation
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on September 7, 1999.