Skip to main content
SpringerLink
Log in

A New Approach for Weighted Constraint Satisfaction

  • Published:
Constraints Aims and scope Submit manuscript

Abstract

We consider the Weighted Constraint Satisfaction Problem which is an important problem in Artificial Intelligence. Given a set of variables, their domains and a set of constraints between variables, our goal is to obtain an assignment of the variables to domain values such that the weighted sum of satisfied constraints is maximized. In this paper, we present a new approach based on randomized rounding of semidefinite programming relaxation. Besides having provable worst-case bounds for domain sizes 2 and 3, our algorithm is simple and efficient in practice, and produces better solutions than some other polynomial-time algorithms such as greedy and randomized local search.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alizadeh, F. (1995). Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM Journal of Optimization, 5(1): 13–51.

    Google Scholar 

  2. Alon, N., & Spencer, J. (1992). The Probabilistic Method. Wiley Interscience Ser. Disc. Math. and Optimiz., Wiley, New York.

    Google Scholar 

  3. Freuder, E. C. (1989). Partial constraint satisfaction. In Proceedings of the International Joint Conference Artificial Intelligence (IJCAI), pages 278–283, Detroit, MI.

  4. Freuder, E. C., & Wallace, R. J. (1992). Partial constraint satisfaction. Artificial Intelligence, 58(1–3): 21–70.

    Google Scholar 

  5. Fujisawa, K., & Kojima, M. (1995). Sdpa (semidefinite programming algorithm) user's manual. Technical Report B-308, Dept. Information Science, Tokyo Inst. of Technology. Online implementation available at ftp.is.titech.ac.jpunder directory /pub/OpsRes/software/SDPA.

  6. Galinier, P., & Hao, J.-K. (1997). Tabu search for maximal constraint satisfaction problems. In Proceedings of the Third International Conference Principles and Practice of Constraint Programming (CP), pages 196–208. Springer Verlag Lecture Notes Comp. Sci. (1330).

  7. Goemans, M. X., & Williamson, D. P. (1994). Approximation algorithms for MAX CUT and MAX 2SAT. In Proceedings of the 26th ACM Symposium on Theory of Computing, pages 422–431. Full version in J. ACM, 42: 1115–1145.

    Google Scholar 

  8. Lancaster, P., & Tismenetsky, M. (1985). The Theory of Matrices. Academic Press, Orlando, FL.

    Google Scholar 

  9. Larrosa, J., & Meseguer, P. (1995). Optimization-based heuristics for maximal constraint satisfaction. In Proceedings of the First International Conference Principles and Practice of Constraint Programming (CP), pages 103–120. Springer Verlag, Lecture Notes Comp. Sci.

  10. Lau, H. C. (1995). Approximation ofconstraint satisfaction via local search. In Proceedings of the Fourth Workshop on Algorithms and Data Structures (WADS), pages 461–472. Springer Verlag Lecture Notes Comp. Sci. (955).

  11. Lau, H. C., & Watanabe, O. (1996). Randomized approximation ofthe constraint satisfaction probem. Nordic Journal of Computing, 3: 405–424.

    Google Scholar 

  12. Mahajan, S., & Ramesh, H. (1995). Derandomizing semidefinite programming based approximation algorithms. In Proceedings of the 36th IEEE Symposium on Found. of Comp. Sci., pages 162–168.

  13. Raghavan, P., & Thompson, C. D. (1987). Randomized rounding: A technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4): 365–374.

    Google Scholar 

  14. Tsang, E. (1993). Foundations of Constraint Satisfaction. Academic Press.

  15. van Beek, P. On-line C-programs available at http://ai.waterloo.ca/∼vanbeek/software/software.html.

  16. Voudouris, C., & Tsang, E. (1995). Partial constraint satisfaction problems and guided local search. Technical Report No. CSM-250, Dept. Computer Science, University ofEsse x.

  17. Wallace, R. J. (1995). Personal communication.

  18. Wallace, R. J. (1995). Directed arc consistency preprocessing as a strategy for maximal constraint satisfaction. In M. Meyer, ed., Constraint Processing, pages 121–138. Springer Verlag Lecture Notes Comp. Sci. (923).

  19. Wallace, R. J. (1996). Analysis ofheuristic methods for partial constraint satisfaction problems. In Proceedings of the Second International Conference Principles and Practice of Constraint Programming (CP), pages 482–496. Springer Verlag Lecture Notes Comp. Sci. (1118).

  20. Wallace, R. J., & Freuder, E. C. (1993). Conjunctive width heuristics for maximal constraint satisfaction. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 762–768.

  21. Wallace, R. J., & Freuder, E. C. (1995). Heuristic methods for over-constrained constraint satisfaction problems. In CP95 Workshop on Over-Constrained Systems.

Download references

Author information

Authors and Affiliations

  1. School of Computing, National University of Singapore, 3 Science Drive 2, Singapore, 117543

    Hoong Chuin Lau

Authors
  1. Hoong Chuin Lau
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lau, H.C. A New Approach for Weighted Constraint Satisfaction. Constraints 7, 151–165 (2002). https://doi.org/10.1023/A:1015157615164

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1015157615164

Search

Navigation