Many problems, many objectives

by Nicole Gaynor

Patrick Reed’s team at Cornell University created a new algorithm to solve problems that require optimization of many conflicting objectives. His team focuses on managing droughts, but their methodology can be used in many other fields.

Let’s say you want to buy a car. You want four doors, minimal cost, minimal upkeep, and high gas mileage. How do you find the car that best fits these objectives?

That is a small-scale example of a multi-objective problem, one in which you try to optimize four or more factors. Patrick Reed, a professor at Cornell University, specializes in solving such problems on a much larger and more complex scale using massive computing systems like Blue Waters. He recently targeted water resource management in the Lower Rio Grande Valley (LRGV) at the southern tip of Texas.

The LRGV is on the edge of the Desert Southwest, an area that is expected to see lower river levels due to less spring snowmelt from the Rocky Mountains and less consistent rainfall in the coming decades. Municipalities across this region will need to support a rapidly growing population with a shrinking water supply.

A better solver

Reed and colleague David Hadka, a recent doctoral graduate from Reed’s research group, wrote in a 2014 paper published in Water Resources Research that the LRGV is “a severely challenging urban water portfolio planning problem.” A water portfolio is the variety of ways a municipality can obtain water. For this study, they considered three strategies:

1. buy a percentage of input to a reservoir, which is the standard but is not flexible
2. lease water from farmers as needed with monthly price fluctuations, which is more flexible but can lead to volatile prices
3. pay a fee in January to fix the cost for a given volume of water for the year and then buy water as needed throughout the year, which is still more flexible than option one and avoids the price volatility in option two

In 2007, Reed’s first attempt to solve the problem required months of computing time, and Reed says most existing solvers cannot tackle the LRGV problem even today.

Reed’s group developed a new, more efficient solver that uses their multi-master Borg multi-objective evolutionary algorithm (MOEA). That EA in MOEA means the algorithm learns how to modify water portfolios to improve their performance as the program runs. The algorithm also runs differently depending on the number of processors.

The researchers tested the performance of their solver using different core counts from 512 to 524,288 cores (aka, benchmarking). They designed the LRGV case to be extremely difficult by only allowing 20 minutes to find the best solution possible. The goal is to go from months to minutes while producing better results with the new algorithm running on Blue Waters.

This benchmarking found that the solver performs better in parallel than in serial because of its ability to learn and adapt itself—detecting when the search stagnates, for example—as it discovers problem characteristics. The scalability of algorithm increases as the amount of time to simulate the consequences of each scenarios increases. That means the Borg MOEA is prepared to solve extremely large, complex problems on future, even bigger supercomputers.

The solver works by using groups of searches that help each other find which water portfolio decisions meet the LRGV’s multiple objectives the best. Each processor evaluates the water portfolios it is given, and if it finds something interesting it communicates that to the rest of the processors. Then the other processors can help zero in on the most interesting solutions.

Imagine a search and rescue team looking for a child in a complex mountain range. The group of people combs a large area until someone finds the child’s scarf and notifies the rest of the search team. Then the searchers focus on the area near the scarf, taking it as a sign that the child may be nearby. More people reach the goal of this single-objective problem (find the child) more quickly. Much like this search party, a group search is much more efficient for a multi-objective problem.

Water resource management is very complex, but the search for the best tradeoff solutions operates using a similar concept. Reed and Hadka sought to minimize five elements: cost, lack of reliability, surplus water, dropped or unused water transfers, and number of leases required over ten years. They also considered the three strategies for managing water listed earlier.

The Borg MOEA algorithm takes all of this into account in finding the most promising tradeoff solutions (yes, plural) for a multitude of possible futures. There is no single best solution because improving one objective degrades the others.

The common thread

“Benchmarking on the LRGV relates to our Blue Water team’s general interest in droughts, but more importantly we have expanded the size and scope of multi-objective design problems that can be addressed,” says Reed. “Our new solver has broad value to a range of applications.”

This problem uses mathematical concepts in the solver that are similar to those used in their satellite path efficiency project on Blue Waters (see “Keeping Satellites on Track“).

In addition to satellite design and operation and reservoir management, Reed says his collaborators are using multi-objective analysis to help decide government spending for research and programs, a topic near and dear to every researcher’s heart.

“Anywhere people have to face tough tradeoffs, multi-objective analysis may help a lot,” says Reed.

Disclaimer: Due to changes in website systems, we've adjusted archived content to fit the present-day site and the articles will not appear in their original published format. Formatting, header information, photographs and other illustrations are not available in archived articles.