×

A branch and bound algorithm for numerical Max-CSP. (English) Zbl 1209.68095

Summary: The Constraint Satisfaction Problem (CSP) framework allows users to define problems in a declarative way, quite independently from the solving process. However, when the problem is over-constrained, the answer “no solution” is generally unsatisfactory. A Max-CSP \(\mathcal{P}_m = \langle V, \mathbf{D}, C \rangle\) is a triple defining a constraint problem whose solutions maximize the number of satisfied constraints. In this paper, we focus on numerical CSPs, which are defined on real variables represented as floating point intervals and which constraints are numerical relations defined in intension. Solving such a problem (i.e., exactly characterizing its solution set) is generally undecidable and thus consists in providing approximations. We propose a Branch and Bound algorithm that provides under and over approximations of a solution set that maximize the maximum number \({m_{\mathcal P}}\) of satisfied constraints. The technique is applied on three numeric applications and provides promising results.

MSC:

68N17 Logic programming
68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)

Software:

KNITRO; MINOS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Benhamou, F., Goualard, F., Granvilliers, L., & Puget, J.-F. (1999). Revising hull and box consistency. In Proceedings of the 1999 international conference on logic programming, ICLP’99 (pp. 230–244). Cambridge, MA, USA: Massachusetts Institute of Technology.
[2] Benhamou, F., Goualard, F., Languenou, E., & Christie, M. (2004). Interval constraint solving for camera control and motion planning. ACM Transactions on Computational Logic, 5(4), 732–767. · doi:10.1145/1024922.1024927
[3] Benhamou, F., McAllester, D., & van Hentenryck, P. (1994). CLP(intervals) revisited. In International logic programming symposium, ILPS ’94 (pp. 124–138). Cambridge: MIT.
[4] Benhamou, F., & Older, W. J. (1997). Applying interval arithmetic to real, integer and Boolean constraints. Journal of Logic Programming, 32(1), 1–24. · Zbl 0882.68032 · doi:10.1016/S0743-1066(96)00142-2
[5] Borning, A., Freeman-Benson, B., & Wilson, M. (1992). Constraint hierarchies. Lisp and Symbolic Computation, 5(3), 223–270. · doi:10.1007/BF01807506
[6] Byrd, R. H., Nocedal, J., & Waltz, R. A. (2006). KNITRO: An integrated package for nonlinear optimization. In Large-scale nonlinear optimization (pp. 35–59). New York: Springer. · Zbl 1108.90004
[7] Christie, M., & Normand, J.-M. (2005). A semantic space partitionning approach to virtual camera control. In Proceedings of the annual eurographics conference (Vol. 24, pp. 247–256).
[8] Christie, M., Normand, J.-M., & Truchet, C. (2006). Computing inner approximations of numerical MaxCSP. In Interval analysis, constraint propagation, applications, IntCP 2006.
[9] Collavizza, H., Delobel, F., & Rueher, M. (1999). Extending consistent domains of numeric CSP. In IJCAI ’99: Proceedings of the sixteenth international joint conference on artificial intelligence (pp. 406–413).
[10] de Givry, S., Larrosa, J., Meseguer, P., & Schiex, T. (2003). Solving Max-SAT as weighted CSP. In Principles and practice of constraint programming, CP 2003 (pp. 363–376). New York: Springer. · Zbl 1273.68368
[11] Delanoue, N., Jaulin, L., & Cottenceau, B. (2004). Counting the number of connected components of a set and its application to robotics. In PARA (pp. 93–101).
[12] Dongarra, J. (2007). Performance of various computers using standard linear equations software. Technical report CS-89-85, University of Tennessee.
[13] Drezner, Z., & Hamacher, H. W. (Eds.) (2002). Facility location. Applications and theory. New York: Springer. · Zbl 0988.00044
[14] Goldberg, D. (1991). What every computer scientist should know about floating-point arithmetic. Computing Surveys, 23(1), 5–48. · doi:10.1145/103162.103163
[15] Hayes, B. (2003). A lucid interval. American Scientist, 91(6), 484–488.
[16] Hirsch, M. J., Meneses, C. N., Pardalos, P. M., & Resende, M. G. C. (2007). Global optimization by continuous grasp. Optimization Letters, 1, 201–212. · Zbl 1149.90119 · doi:10.1007/s11590-006-0021-6
[17] Jaulin, L., & Walter, E. (1993). Guaranteed nonlinear parameter estimation from bounded-error data via interval analysis. Mathematics and Computers in Simulation, 35(2), 123–137. · Zbl 0829.65143 · doi:10.1016/0378-4754(93)90008-I
[18] Jaulin, L., & Walter, E. (2002). Guaranteed robust nonlinear minimax estimation. IEEE Transaction on Automatic Control, 47(11), 1857–1864. · Zbl 1364.93161 · doi:10.1109/TAC.2002.804479
[19] Jaulin, L., Walter, E., & Didrit, O. (1996). Guaranteed robust nonlinear parameter bounding. In CESA’96, IMACS multiconference (symposium on modelling, analysis and simulation) (pp. 1156–1161).
[20] Lhomme, O. (1993). Consistency techniques for numeric CSPs. In IJCAI ’93: Proceedings of the thirteenth international joint conference on artificial intelligence (pp. 232–238).
[21] Mackworth, A. K. (1977). Consistency in networks of relations. Artificial Intelligence, 8(1), 99–118. · Zbl 0341.68061 · doi:10.1016/0004-3702(77)90007-8
[22] Milanese, M., & Vicino, A. (1991). Estimation theory for nonlinear models and set membership uncertainty. Automatica, 27(2), 403–408. · Zbl 0729.93074 · doi:10.1016/0005-1098(91)90090-O
[23] Minton, S., Johnston, M. D., Philips, A. B., & Laird, P. (1992). Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems. Artificial Intelligence, 58(1–3), 161–205. · Zbl 0782.90054 · doi:10.1016/0004-3702(92)90007-K
[24] Moore, R. E. (1966). Interval analysis. Englewood Cliffs: Prentice-Hall. · Zbl 0176.13301
[25] Murtagh, B. A., & Saunders, M. A. (1998). Minos 5.5 user’s guide. Technical report, Systems Optimization Laboratory, Department of Operations Research, Stanford University.
[26] Neumaier, A. (1990). Interval methods for systems of equations. Cambridge: Cambridge University Press. · Zbl 0715.65030
[27] Normand, J.-M. (2008). Placement de caméra en environnements virtuels. PhD thesis, Université de Nantes.
[28] Petit, T., Régin, J.-C., & Bessière, C. (2002). Range-based algorithm for Max-CSP. In Principles and practice of constraint programming, CP 2002 (pp. 280–294). New York: Springer.
[29] Wallace, R. J. (1996). Analysis of heuristic methods for partial constraint satisfaction problems. In Principles and practice of constraint programming, CP 1996 (pp. 482–496). New York: Springer.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.