Mixed Integer Programming to Globally Minimize the Economic Load Dispatch Problem With Valve-Point Effect

Michael Azzam, Easter S. Suviseshamuthu, Augustin Lefèvre, P.-a. AbsilarXiv 2014 · DOI · arXiv

Optimal distribution of power among generating units to meet a specific demand subject to system constraints is a cornerstone of power system operations. However, the Economic Load Dispatch Problem (ELDP) is notoriously difficult to solve globally due to "valve-point effects," which introduce non-smoothness and non-convexity into the cost functions. Historically, this complexity has led researchers to rely on stochastic, population-based heuristics. This paper presents a deterministic alternative using Mixed-Integer Quadratic Programming (MIQP), offering guaranteed global optimality and superior computational performance.

TL;DR

The authors replace unpredictable, population-based heuristics with a rigorous Mixed-Integer Quadratic Programming (MIQP) framework. Their adaptive under-approximation method provides a mathematical guarantee of global optimality and consistently finds lower-cost solutions than previous state-of-the-art methods in a fraction of a second.

The Challenge: Valve-Point Effects

In an idealized model, a generator's fuel cost is a smooth quadratic curve. In reality, steam turbines utilize multiple admission valves to control power output. As these valves open, "wire-drawing" effects cause sharp increases in losses, creating "ripples" or oscillations in the cost curve. Mathematically, this is modeled by adding a rectified sine term to the standard quadratic cost function.

Figure 1: The cost function f(p) exhibiting valve-point effects (dashed line) and its piecewise approximation (solid line).

This valve-point effect turns a simple convex optimization into a non-convex nightmare filled with local minima. Because standard gradient-based methods often get stuck in these "traps," the field has been dominated by stochastic heuristics like Genetic Algorithms (GA) or Particle Swarm Optimization (PSO). While useful, these methods offer no guarantee of finding the absolute best solution and can produce inconsistent results across different runs.

Proposed Methods

The authors propose shifting the problem into the realm of Mixed-Integer Quadratic Programming (MIQP). By using integer variables to represent discrete segments of the cost curve, they can leverage powerful commercial solvers to find global optimums. They introduce two distinct strategies:

1. Simple MIQP Approach

This method replaces the rectified sine term with a fixed "sawtooth" piecewise-linear approximation. By using a very limited number of linear segments, the problem remains computationally light while often reaching the global minimum found by much more complex heuristic algorithms.

2. Adaptive Piecewise-Quadratic Under-approximation

This more sophisticated method builds an under-estimation of the cost function that is iteratively refined. The algorithm starts with a loose approximation, solves the resulting MIQP, and then "tightens" the approximation specifically at the point of the current optimal solution.

Figure 6: Algorithm 1 for the adaptive piecewise-quadratic under-approximation method.

Crucially, the authors provide a mathematical proof (Theorem 2) showing that any limit point of this sequence of MIQP solutions is a guaranteed global solution of the original ELDP. This moves the problem from "best-effort" heuristics to "guaranteed" deterministic optimization.

Experimental Validation

The methods were tested against standard benchmarks in the power systems literature, including 3-unit, 13-unit, and 40-unit systems. These datasets are the "gold standard" for ELDP research, allowing for direct comparison against dozens of previously published heuristic-based papers.

Key Results

  • New Global Records: For the 13-unit and 40-unit cases, the authors identified generation costs lower than any previously reported results in the literature.
  • Extreme Speed: The 40-unit problem—a significant challenge for many heuristics—was solved in roughly 0.2 to 0.9 seconds on a standard dual-core PC.
  • Deterministic Reliability: Unlike stochastic methods, the MIQP approach is deterministic. It provides a "certificate" of optimality, ensuring the operator that no better solution exists within the defined constraints.

Insights and Future Directions

The paper demonstrates that heuristics are often "overkill" for the ELDP. Even the crude Method 1 matched or beat hybrid heuristics that require thousands of iterations. The adaptive method further proves that high-resolution approximations are only necessary where the optimal solution actually lies, rather than across the entire domain.

While the results are promising, future work remains in scaling these methods to grids with thousands of units, where the number of integer variables could impact solver performance. Additionally, incorporating transmission losses and dynamic constraints (ramping limits over time) are logical next steps for this deterministic framework.

Summary updated

Abstract

Optimal distribution of power among generating units to meet a specific demand subject to system constraints is an ongoing research topic in the power system community. The problem, even in a static setting, turns out to be hard to solve with conventional optimization methods owing to the consideration of valve-point effects which make the cost function nonsmooth and nonconvex. This difficulty gave rise to the proliferation of population-based global heuristics in order to address the multi-extremal and nonsmooth problem. In this paper, we address the economic load dispatch problem (ELDP) with valve-point effect in its classic formulation where the cost function for each generator is expressed as the sum of a quadratic term and a rectified sine term. We propose two methods that resort to piecewise-quadratic surrogate cost functions, yielding surrogate problems that can be handled by mixed-integer quadratic programming (MIQP) solvers. The first method shows that the global solution of the ELDP can often be found by using a fixed and very limited number of quadratic pieces in the surrogate cost function. The second method adaptively builds piecewise-quadratic surrogate under-estimations of the ELDP cost function, yielding a sequence of surrogate MIQP problems. It is shown that any limit point of the sequence of MIQP solutions is a global solution of the ELDP. Moreover, numerical experiments indicate that the proposed methods outclass the state-of-the-art algorithms in terms of minimization value and computation time on practical instances.
BibTeX
@misc{azzam2014mixed,
  author = {Michael Azzam and Easter S. Suviseshamuthu and Augustin Lefèvre and P.-A. Absil},
  title = {{Mixed Integer Programming to Globally Minimize the Economic Load Dispatch Problem With Valve-Point Effect}},
  year = {2014},
  eprint = {1407.4261},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1407.4261},
}
Figure