The power of Constraint Logic Programming (CLP) is in its ability to deal with combinatorial complexity. While simulation calculates the effects of measures, CLP generates good sets of measures that comply with the set of constraints and goals set for the problem. CLP and simulation may be considered complementary.
The intention of this application is to support decision-making in flood prevention by deriving appropriate measure sets from targets and goals to be achieved in a system. It generates good combined measure sets from a database of precalculated effects of measures. Another project description shows the use an alternative CLP approach to design flood prevention measures.
Although the application deals with the consequences of extreme river discharges, the principles of the approach have a much wider scope.
Stacking up measures
Using a simulation model of the Dutch branches of the Rhine River, the effects of hundreds of measures were calculated. Our CLP application uses these calculated effects. Each measure lowers the water level in a part of the river but none of them is individually capable of compensating for the violations of the Maximum Water Levels (MWL, set by law) that occur under extreme discharge conditions. Any solution, therefore, must consist of a combination of measures.
Our CLP application generates sets of measures that together maintain the water levels everywhere under MWL. The heart of this application is the cumulative constraint that ensures that the sum of effects of measures in every section of the river should be greater than or equal to the amount of the violation. As a result, any solution generated is by definition consistent with this constraint. Moreover, the constraint applies 'forward-looking' strategies to direct choices from the remaining possible measures, to disable possibilities or to backtrack on choices made previously.
In cooperation with constraint propagation that maintains consistency between constraints and possible values for the variables (this is called a domain), intelligent search strategies select appropriate measures to include in the set. Finding a solution is followed by a new search for a solution with lower costs than the last one. In this way solutions are improved until the given search time is exhausted, or until the optimality of the last solution is proven. The proven optimality message indicates that better solutions can only be found after changing constraints or goals. Of course, an overly strict definition of a problem will generate a message that the problem is not solvable.
Solutions are generated rapidly by the application, especially after improvement of the solver in 2004.
For a river branch having 166 sections and 54 possible measures, it takes about 20 seconds (on a 1 GHz processor) to find a first solution, while the third solution appears after about 2.5 minutes. This one is proven optimal. The performance would be improved considerably if more information about the characteristics of the measures and more elaborate constraints on the wishes with respect to the solutions were available.
The software may be applied to other rivers by changing the data set. |
