← Back to Projects
2019 Computational Hydrology

Innovative Optimization Algorithm for Hydro Unit Commitment

Saving water and computational resources using a novel heuristic solution scheme.

Read Publication
Python (cvxpy) Mathematical Modeling (MILP) Optimization Algorithm Design

THE PROBLEM

Short-term resource optimization when dealing with complex physical infrastructure, such as power generation in hydropower plants, is notoriously difficult (NP-hard). This often forces a trade-off: either oversimplify the physical reality, or accept computation times that are useless for real-world operations.

THE ACTION

I designed an algorithmic architecture to break the accuracy-efficiency tradeoff. It deconstructs the intractable problem into a series of highly tractable (MILP) optimizations, which reliably converges to an optimal solution without stripping away the physical constraints.

THE RESULT

The architecture outperforms standard commercial MINLP solvers by an order of magnitude in speed, delivering highly reliable, deployable solutions with zero practical loss in fidelity.

Inspiration & Context

Experienced researchers often advise beginners to stay away from some topics as your first research project. I ignored that advice in 2016 when I was a Master's student in Water Resources Engineering at Iran University of Science and Technology. I was drawn to Robust Optimization because it philosophically appealed to me: preparing for worst-case scenarios in the face of absolute uncertainty. It took me a while to be able to read and write the notations on the reference books, let alone learning how to apply it to simple optimization problems. I was determined so I kept going and eventually I was able to apply it to various typical optimization problems.

Through my advisor I realized that the Ministry of Energy solves this short-term scheduling problem for hydropower plants in an oversimplified way that is not efficient in terms of water usage. That sounded like resource optimization to me and it got me in without any friction. I got all the information I needed from the operators to mathematically model the system. I was really excited to apply Robust Optimization as electricity demand, which hydropower plants are to meet, is a great example of an inherently uncertain parameter. But after modeling the system, I hit a wall: solving it required commercial MINLP solvers that were just out of my reach. I couldn't test my robust optimization strategy without being able to solve the original problem.

Was I disappointed? Absolutely. Discouraged? Not at all. This is where the problem solving part of my brain takes over with pleasure. After immersing myself in the system's physics and constraints, I realized I could decouple the two variables involved in the non-linear (non-convex) constraint. I fixed them with calculated initial guesses, solved a linearized version, and iteratively updated those variables based on accurate physical equations. It worked. It always converged to an optimal and accurate solution.

SIDE STORY When the Commercial Solvers Failed.

Of course I kept on looking for ways to be able to use the MINLP solvers. I was adamant to compare my own algorithm with them. I finally found an online platform (NEOS Server) where I could upload my optimization code and it would run it on their servers with commercial solvers. Long live University of Wisconsin-Madison!

But here was the real challenge: the commercial solvers were not able to step in the feasible region of the problem using the initial points that the software automatically generated (?) Another brick wall? Yeah, more like another chance to innovate. I designed a heuristic algorithm (read more in the published research paper) that generates initial points that helps the solvers get started.

Technical Details

We mathematically modeled two cascaded hydropower dams in Iran: Karun 3 and Karun 4. The problem is to create a 24-hour schedule for the turbines in both dams that meets the forecasted electricity demand while minimizing:

  1. Water release
  2. The number of times the turbines are turned on and off (to reduce wear and tear).

subject to a set of physical and operational constraints

The Mathematical Formulation

1. The Objective

The primary goal is water conservation: minimizing total release volume while penalizing frequent turbine switching.

$$ \text{Minimize } Z = \sum_{t=1}^{24} \sum_{r \in \{3,4\}} (R_{r,t} \times 3600) + \text{Startup Penalties} $$

2. The Computational Bottleneck

Power generation is naturally non-convex. The relationship between head, flow, and status is governed by a complex fractional polynomial which I derived from the turbines' hill charts:

$$ p_{r,i,t} = \left( \frac{q_{r,i,t} + \alpha_{3}^{p} h_{r,t}^{2} - \alpha_{2}^{p} h_{r,t} - \alpha_{1}^{p}}{\alpha_{4}^{p} + \alpha_{5}^{p} h_{r,t}} \right) Z_{r,i,t} $$

Feeding this directly into a solver creates an intractable search space for real-time operations.

THE BREAKTHROUGH

3. Sequential MILP Approximation

To break the deadlock, I developed a decoupling scheme. By using the net head (\(\bar{h}\)) and efficiency (\(\bar{\xi}\)) from the previous iteration as fixed constants, the non-linear equation transforms into a highly efficient Mixed-Integer Linear form:

$$ p_{r,i,t} = \bar{\xi}_{r,i,t} \bar{h}_{r,t} q_{r,i,t} $$

It starts with an initial guess for \(\bar{h}\) and \(\bar{\xi}\). Once a provisional generation schedule is generated, the algorithm must verify its physical validity. It calculates the actual net head and efficiency resulting from the newly proposed turbine flows. The check phase measures the discrepancy between these true values and the initial fixed constants (\(\bar{h}\) and \(\bar{\xi}\)). If the difference is within a strict, predefined tolerance, the model has converged.

If the tolerance limit is breached, the algorithm discards the old values. The actual head and efficiency values computed during the check phase replace the previous constants. This data is then inserted back into the linear solver, running a new iteration that forces the mathematical approximation to progressively lock in on the reservoir's actual hydrodynamics.

The algorithm "Guesses, Checks, and Replaces"—iterating until the fast linear approximation perfectly matches the strict physical reality of the dams.

4. Physical Boundaries

Turbine Discharge Limits

Flow stays within mechanical bounds, but only when the unit is active (\(Z=1\)).

$$ Z_{r,i,t} \cdot Q_{min,r} \le q_{r,i,t} \le Z_{r,i,t} \cdot Q_{max,r} $$

Grid Demand Balance

The total generation across the cascade must meet the hourly load.

$$ \sum_{r \in \{3,4\}} \sum_{i} p_{r,i,t} \ge \text{Demand}_{t} $$

... subject to further constraints including cascaded reservoir water balance, physical storage limits, minimum up/down times, and spinning reserve requirements.

NP-hard

In computational complexity theory, NP-hard refers to a class of problems that are at least as difficult as the hardest problems in the "Non-deterministic Polynomial" set.

Practically, this means that as the number of turbines or hours in the schedule increases, the time required to find the absolute perfect solution grows exponentially, making traditional methods too slow for real-time operations.

MILP

Mixed-Integer Linear Programming is a mathematical modeling technique where the objective and constraints are linear, but some variables are restricted to be integers (usually 0 or 1).

In hydropower, binary variables are used to represent whether a turbine is "On" or "Off." Linear approximations make these models much faster to solve than non-linear ones.

MINLP

Mixed-Integer Non-Linear Programming is the "boss level" of optimization. It combines integer constraints (On/Off) with complex, non-linear physical formulas (like water pressure and turbine efficiency curves).

While highly accurate, these problems are notoriously difficult and slow to solve. Our approach approximates these non-linearities using a sequence of faster MILP steps.

Initial Points

Optimization algorithms often require an initial guess to start the search for the optimal solution. The quality of this guess can significantly affect the convergence speed and success of the solver.

Non-Convex Relationship

A non-convex relationship means that the mathematical function describing the system has multiple local minima and maxima, making it difficult for optimization algorithms to find the global optimum. In our case, the power output of a turbine doesn't change in a simple, predictable way with changes in water flow and head, which is why we need to use approximations to solve the problem efficiently.

This non-convexity is what makes the original problem so computationally challenging and is the reason why our linearized approach is so effective.

Hill Chart

A hill chart is a representation of a turbine's efficiency across different operating conditions. It shows how the power output varies with changes in water flow and head.