Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-19T07:08:25.896Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal placement of valves in a water distribution network with CLP(FD)

Published online by Cambridge University Press:  06 July 2011

MASSIMILIANO CATTAFI ,
MARCO GAVANELLI ,
MADDALENA NONATO ,
STEFANO ALVISI  and
MARCO FRANCHINI
MASSIMILIANO CATTAFI
Affiliation:
Department of Engineering, University of Ferrara, Via Saragat, 1 44122 Ferrara, Italy
MARCO GAVANELLI
Affiliation:
Department of Engineering, University of Ferrara, Via Saragat, 1 44122 Ferrara, Italy
MADDALENA NONATO
Affiliation:
Department of Engineering, University of Ferrara, Via Saragat, 1 44122 Ferrara, Italy
STEFANO ALVISI
Affiliation:
Department of Engineering, University of Ferrara, Via Saragat, 1 44122 Ferrara, Italy
MARCO FRANCHINI
Affiliation:
Department of Engineering, University of Ferrara, Via Saragat, 1 44122 Ferrara, Italy
Get access Rights & Permissions [Opens in a new window]

Abstract

This paper presents a new application of logic programming to a real-life problem in hydraulic engineering. The work is developed as a collaboration of computer scientists and hydraulic engineers, and applies Constraint Logic Programming to solve a hard combinatorial problem. This application deals with one aspect of the design of a water distribution network, i.e., the valve isolation system design. We take the formulation of the problem by Giustolisi and Savić (2008 Optimal design of isolation valve system for water distribution networks. In Proceedings of the 10th Annual Water Distribution Systems Analysis Conference WDSA2008, J. Van Zyl, A. Ilemobade, and H. Jacobs, Eds.) and show how, thanks to constraint propagation, we can get better solutions than the best solution known in the literature for the Apulian distribution network. We believe that the area of the so-called hydroinformatics can benefit from the techniques developed in Constraint Logic Programming and possibly from other areas of logic programming, such as Answer Set Programming.

Keywords

constraint logic programminghydraulic engineeringvalve placementgraph partitioning
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 11 , Special Issue 4-5: 27th International Conference on Logic Programming , July 2011 , pp. 731 - 747
Copyright
Copyright © Cambridge University Press 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Apt, K. R. and Wallace, M. 2006. Constraint Logic Programming using ECLiPSe. Cambridge University Press.CrossRefGoogle Scholar
Boussemart, F., Hemery, F., Lecoutre, C. and Sais, L. 2004. Boosting systematic search by weighting constraints. In Proc. of 16th European Conference on Artificial Intelligence (ECAI '04), de Mántaras, R. L. and Saitta, L., Eds. IOS Press, 146–150.Google Scholar
Cattafi, M. and Gavanelli, M. 2011. A CLP(FD) program for the optimal placement of valves in a water distribution network [online]. URL: http://www.ing.unife.it/docenti/MarcoGavanelli/software/vp/CrossRefGoogle Scholar
Chung, F. R. K. 1994. Spectral Graph Theory. American Mathematical Society.Google Scholar
Creaco, E., Franchini, M. and Alvisi, S. 2010. Optimal placement of isolation valves in water distribution systems based on valve cost and weighted average demand shortfall. Journal of Water Resources Planning and Management 24 (15), 4317–4338.Google Scholar
Dal Palù, A., Dovier, A., Fogolari, F. and Pontelli, E. 2010. CLP-based protein fragment assembly. Theory and Practice of Logic Programming 10 (4–6), 709–724.CrossRefGoogle Scholar
Dechter, R. 2003. Constraint Processing. Morgan Kaufmann.Google Scholar
Dovier, A., Formisano, A. and Pontelli, E. 2005. A comparison of CLP(FD) and ASP solutions to NP-complete problems. In Proc. of 21st International Conference on Logic Programming (ICLP '05), Gabbrielli, M. and Gupta, G., Eds. Lecture Notes in Computer Science, vol. 3668. Springer, 67–82.Google Scholar
Faber, W., Pfeifer, G., Leone, N., Dell'Armi, T. and Ielpa, G. 2008. Design and implementation of aggregate functions in the DLV system. Theory and Practice of Logic Programming 8 (5–6), 545–580.CrossRefGoogle Scholar
Fages, F. 1996. From constraint minimization to goal optimization in CLP languages. In Proc. of 2nd International Conference on Principles and Practice of Constraint Programming (CP '96), Freuder, E. C., Ed. Lecture Notes in Computer Science, vol. 1118. Springer, 537–538.Google Scholar
Fiduccia, C. M. and Mattheyses, R. M. 1982. A linear-time heuristic for improving network partitions. In Proc. of 19th Design Automation Conference (DAC '82). IEEE, Piscataway, NJ, USA, 175–181.Google Scholar
Fiedler, M. 1973. Algebraic connectivity of graphs. Czechoslovak Mathematical Journal 23 (98), 298–305.CrossRefGoogle Scholar
Focacci, F., Lodi, A. and Milano, M. 1999. Cost-based domain filtering. In Proc. of 5th International Conference on Principles and Practice of Constraint Programming (CP '99), Jaffar, J., Ed. Lecture Notes in Computer Science, vol. 1713. Springer, 189–203.Google Scholar
Focacci, F., Lodi, A. and Milano, M. 2002. A hybrid exact algorithm for the TSPTW. INFORMS Journal on Computing 14 (4) (fall), 403–417.CrossRefGoogle Scholar
Frühwirth, T. and Abdennadher, S. 2003. Essentials of Constraint Programming. Springer.CrossRefGoogle Scholar
Garey, M. R. and Johnson, D. S. 1990. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman, New York.Google Scholar
Gavanelli, M. 2002. An algorithm for multi-criteria optimization in CSPs. In Proc. of 15th European Conference on Artificial Intelligence (ECAI '02), van Harmelen, F., Ed. IOS Press, Lyon, France, 136–140.Google Scholar
Gervet, C., Caseau, Y. and Montaut, D. 1999. On refining ill-defined constraint problems: A case study in iterative prototyping. In Proc. of Practical Application of Constraint Technologies and Logic Programming (PACLP '99) The Practical Application Company Ltd., London, 255–275.Google Scholar
Giustolisi, O. and Savić, D. A. 2008. Optimal design of isolation valve system for water distribution networks. In Proc. of 10th Annual Water Distribution Systems Analysis Conference (WDSA '08), Van Zyl, J., Ilemobade, A. and Jacobs, H., Eds., 1–13.Google Scholar
Giustolisi, O. and Savić, D. A. 2010. Identification of segments and optimal isolation valve system design in water distribution networks. Urban Water Journal 7 (1), 1–15.CrossRefGoogle Scholar
Gomes, C. P., Selman, B. and Crato, N. 1997. Heavy-tailed distributions in combinatorial search. In Proc. of International Conference on Principles and Practice of Constraint Programming (CP '97), Smolka, G., Ed. Lecture Notes in Computer Science, vol. 1330. Springer, 121–135.Google Scholar
Hendrickson, B. and Leland, R. 1995a. An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM Journal on Scientific Computing 16, 452–469.CrossRefGoogle Scholar
Hendrickson, B. and Leland, R. 1995b. A multilevel algorithm for partitioning graphs. In Proc. of 1995 ACM/IEEE Conference on Supercomputing (CDROM '95). ACM, New York.Google Scholar
Hopcroft, J. and Tarjan, R. 1973. Algorithm 447: Efficient algorithms for graph manipulation. Communications of the ACM 16, 372–378.CrossRefGoogle Scholar
Jaffar, J. and Maher, M. J. 1994. Constraint logic programming: A survey. Journal of Logic Programming 19/20, 503–581.CrossRefGoogle Scholar
Jun, H. and Loganathan, G. V. March/April 2007. Valve-controlled segments in water distribution systems. Journal of Water Resources Planning and Management 133 (2), 145–155.CrossRefGoogle Scholar
Kao, J.-J. and Li, P.-H. 2007. A segment-based optimization model for water pipeline replacement. Journal of the American Water Works Association 99 (7), 83–95.CrossRefGoogle Scholar
Karypis, G. and Kumar, V. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal of Scientific Computing 20, 359–392.CrossRefGoogle Scholar
Kernigan, B. and Lin, S. 1970. An efficient heuristic procedure for partitioning graphs. Bell Systems Technical Journal 49, 291–307.CrossRefGoogle Scholar
Lipton, R. J. and Tarjan, R. E. 1979. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics 36 (2), 177–189.CrossRefGoogle Scholar
Mancini, T., Micaletto, D., Patrizi, F. and Cadoli, M. 2008. Evaluating ASP and commercial solvers on the CSPLib. Constraints 13 (4), 407–436.CrossRefGoogle Scholar
Marriot, K. and Stuckey, P. J. 1998. Programming with constraints: An introduction. MIT Press.CrossRefGoogle Scholar
Marriott, K. and Stuckey, P. 1994. Semantics of constraint logic programs with optimization. In Proc. of ICLP Workshop: Integration of Declarative Paradigms, Aït-Kaci, H., Hanus, M. and Moreno-Navarro, J., Eds., 23–35.Google Scholar
Pichler, R., Rümmele, S. and Woltran, S. 2010. Multicut algorithms via tree decompositions. In Proc. of 7th International Conference on Algorithms and Complexity (CIAC '10), Calamoneri, T. and Díaz, J., Eds. Lecture Notes in Computer Science, vol. 6078. Springer, 167–179.Google Scholar
Prestwich, S. 1996. Three implementations of branch-and-bound in CLP. In Proc. of 4th Compulog-Net Workshop on Parallelism and Implementation Technologies. Bonn, Germany, 183–194.Google Scholar
Russell, S. J. and Norvig, P. 2003. Artificial Intelligence: A Modern Approach, 2 ed. Prentice Hall.Google Scholar
Schimpf, J. 2002. Logical loops. In Proc. of 18th International Conference on Logic Programming (ICLP '02), Stuckey, P. J., Ed. Lecture Notes in Computer Science, vol. 2401. Springer, 224–238.Google Scholar
Schimpf, J. 2009. ECLiPSe 6.0 Reference Manual, library(graph_algorithms) [online]. URL: http://www.eclipseclp.org/doc/bips/lib/graph_algorithms/Google Scholar
Spielman, A. and Teng, S.-H. 1996. Spectral partitioning works: Planar graphs and finite element meshes. Technical Report. University of California, Berkeley, CA.CrossRefGoogle Scholar
Van Wassenhove, L. and Gelders, L. 1980. Solving a bicriterion scheduling problem. European Journal of Operational Research 4 (1), 42–48.CrossRefGoogle Scholar
Warren, D. S. 1992. Memoing for logic programs. Communications of the ACM 35 (3), 93–111.CrossRefGoogle Scholar
Zhou, N.-F. 2011. The language features and architecture of B-Prolog. Theory and Practice of Logic Programming. In pressCrossRefGoogle Scholar
Zhou, N.-F., Sato, T. and Shen, Y.-D. 2008. Linear tabling strategies and optimizations. Theory and Practice of Logic Programming 8 (1), 81–109.CrossRefGoogle Scholar