Dear readers, With the launch of e-newsletter CUHK in Focus, CUHKUPDates has retired and this site will no longer be updated. To stay abreast of the University’s latest news, please go to https://focus.cuhk.edu.hk. Thank you.
When one Chinese coastal city was looking for pure, fresh "sweet water," they turned to Prof. Jimmy Lee. Professor Lee has devoted his time to solving complex scheduling problems by developing the most efficient solution to the difficult task of when and how much river water to draw.
The city was running desperately short of fresh water, which it would source from the river that flowed through it and into the sea, and then refine. But because the tide would turn and rainfall varied, sometimes the water was saltier than at others. Despite the water department's best efforts, if there was a run of dry weather the saltiness would seep into the public supply.
People were starting to complain. If you hopped in a taxi, the cab driver would harp on about the poor water. Citizens were reduced to buying bottled water simply to have a shower.
Professor Lee's job was to develop a computer program to help the water department manage the amount of water it claimed from the river, at the right time, and control the flow of water between its various reservoirs.
The city, which Professor Lee can't identify because of a confidentiality agreement, had been using a spreadsheet and manually inputting the data. That system required both an experienced staffer familiar with the issues involved with water supply, and a computer staffer to deal with the information. It was highly inefficient.
Professor Lee, a professor in CUHK's department of computer sciences and engineering, was able to create a computer program that saved all those man hours and solved the water scheduling much more simply. "If you are not careful it could take you days or months or years for a simple problem," he says. "I want to be able to push a button and do it immediately."
Normal practice to solve such issues used to be to develop just one solution to a problem, and use that. But Professor Lee realized there could be many ways to solve a particular issue. So he developed a mathematical concept known as channeling constraints. Instead of just finding the single "best" way to solve the problem, this kind of redundant modelling runs as many of the possible solutions as possible by computer, at the same time. The different ways of solving the problem end up communicating with each other and sharing useful information, making for quicker, better answers to a problem.
To ensure the city had sufficient water consistently, it was necessary to factor in the forecast for the salinity for the water, the forecast of the weather, the necessary water intake at any given point, and the distribution system. And of course you have to plan for every eventuality to make sure the water is always in sufficient supply.
"It's a really complex task mixing scheduling and routing," Lee said. "If the size of the input data is twice as big, it doesn't mean just twice as much information to solve the problem. Normally an algorithm is exponential," in the amount of time it would take to run a solution.
Another complication was that rainfall was declining, making it harder and harder to extract the fresh water. So the project became longer-term than expected, significantly complicating the issue. The larger the system and timeframe, the larger the problem, increasing the difficulty much more than might initially be clear.
"When we first got the project we only had to solve the problem for the winter," Lee says. "But then they said the climate is becoming dry at the end of fall and the start of spring. So we had to optimize for 180 days, half a year, which makes it really, really difficult."
Using artificial intelligence, Lee was able to create a computer system that solved the scheduling issue. Where it was taking hours if not days to solve the problem by hand, and often with hit or miss results, Lee's system produced the perfect answer within minutes. It even guaranteed as much as an extra month of salt-free water per year for the city.
The city's residents could once again be sure the water in their taps and showers was "sweet" again. Professor Lee has also developed programs that help schedule nursing rosters and subway systems.
"At the click of an eye you get a solution," Lee says. "Without inventing new algorithms, even by just cleverly modelling the problem we are able to solve it better."
This article was originally published on CUHK Homepage in Dec 2013.