nach oben

Erschienen in:

2012 | OriginalPaper | Buchkapitel

22. Semidefinite Programming and Constraint Programming

verfasst von : Willem-Jan van Hoeve

Erschienen in: Handbook on Semidefinite, Conic and Polynomial Optimization

Verlag: Springer US

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Recently, semidefinite programming relaxations have been applied in constraint programming to take advantage of the high-quality bounds and precise heuristic guidance during the search for a solution. The purpose of this chapter is to present an overview of these developments, and to provide future research prospects.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel SDP Relaxations for Non-Commutative Polynomial Optimization

Nächstes Kapitel The State-of-the-Art in Conic Optimization Software

In the literature, domain consistency is also referred to as hyper-arc consistency or generalized arc consistency for historic reasons.

Anjos, M.F.: An improved semidefinite programming relaxation for the satisfiability problem. Mathematical Programming 102(3), 589–608 (2005)CrossRef

Anjos, M.F., Vannelli, A.: Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes. INFORMS Journal on Computing 20, 611–617 (2008)CrossRef

Apt, K.R.: The essence of constraint propagation. Theoretical Computer Science 221(1–2), 179–210 (1999)CrossRef

Apt, K.R.: Principles of Constraint Programming. Cambridge University Press, Cambridge (2003)CrossRef

Brand, S., Duck, G.J., Puchinger, J., Stuckey, P.J.: Flexible, Rule-Based Constraint Model Linearisation. In: Hudak, P., Warren, D.S. (eds.) Practical Aspects of Declarative Languages, 10th International Symposium (PADL 2008), San Francisco, January 2008. Lecture Notes in Computer Science, vol. 4902, pp. 68–83. Springer, Heidelberg (2008)

Charikar, M., Makarychev, K., Makarychev, Y.: Near-optimal algorithms for maximum constraint satisfaction problems. ACM Transactions on Algorithms 5(3), 32:1–32:14 (2009)CrossRef

Cheriyan, J., Cunningham, W.H., Tunçel, L., Wang, Y.: A Linear Programming and Rounding Approach to MAX 2-SAT. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 26, 395–414 (1996)CrossRef

Dechter, R.: Constraint Processing. Morgan Kaufmann, San Francisco (2003)

Faure, N., Chrétienne, P., Gourdin, E., Sourd, F.: Biclique completion problems for multicast network design. Discrete Optimization 4, 360–377 (2007)CrossRef

10.

FICO. Xpress-Kalis User guide, Fair Isaac Corporation (2009)

11.

Fischetti, M., Lodi, A.: Local Branching. Mathematical Programming 98(1–3), 23–47 (2003)CrossRef

12.

Fleischman, D., Poggi de Aragão, M.V.: Improved SDP Bounds on the Exact Solution of Unconstrained Binary Quadratic Programming. Paper presented at the 2010 Optimization Days, Montréal, 10-12 May 2010

13.

Focacci, F., Lodi, A., Milano, M.: Cost-based domain filtering. In: Jaffar, J. (ed.) Principles and Practice of Constraint Programming, 5th International Conference, CP’99, Alexandria, October 1999. Lecture Notes in Computer Science, vol. 1713, pp. 189–203. Springer, Heidelberg (1999)

14.

Focacci, F., Lodi, A., Milano, M.: Optimization-Oriented Global Constraints. Constraints 7(3–4), 351–365 (2002)

15.

Focacci, F., Lodi, A., Milano, M.: Embedding relaxations in global constraints for solving TSP and TSPTW. Annals of Mathematics and Artificial Intelligence 34(4), 291–311 (2002)CrossRef

16.

Focacci, F., Lodi, A., Milano, M.: A hybrid exact algorithm for the TSPTW. INFORMS Journal on Computing 14(4), 403–417 (2002)CrossRef

17.

Focacci, F., Lodi, A., Milano, M., Vigo, D.: Solving TSP through the integration of OR and CP techniques. Electronic Notes in Discrete Mathematics 1, 13–25 (1999)CrossRef

18.

Frieze A., Jerrum, M.: Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION. Algorithmica 18(1), 67–81 (1997)CrossRef

19.

Garey, M.R., Johnson, D.S.: Computers and Intractibility. Freeman, New York (1979)

20.

Gent, I.P., Petrie, K.E., Puget, J.-F.: Symmetry in Constraint Programming. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, pp. 329–376. Elsevier (2006)

21.

Gervet, C.: Conjunto: Constraint Logic Programming with Finite Set Domains. In: Bruynooghe, M. (ed.) Proceedings of the International Logic Programming Symposium (ILPS), pp. 339–358. MIT Press, Cambridge (1994)

22.

Goemans, M.X., Williamson, D.P.: New \(\frac{3} {4}\)-Approximation Algorithms for the Maximum Satisfiability Problem. SIAM Journal on Discrete Mathematics 7(4), 656–666 (1994)

23.

Goemans, M.X., Williamson, D.P.: Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. Journal of the ACM 42(6), 1115–1145 (1995)CrossRef

24.

Gomes, C.P., van Hoeve, W.J., Leahu, L.: The Power of Semidefinite Programming Relaxations for MAX-SAT. In: Beck, J.C., Smith, B. (eds.) Proceedings of the Third International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR), Ireland, May/June 2006. Lecture Notes in Computer Science, vol. 3990, pp. 104–118. Springer, Heidelberg (2006)

25.

Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Wiley (1988)

26.

Gruber, G., Rendl, F.: Computational experience with stable set relaxations. SIAM Journal on Optimization 13(4), 1014–1028 (2003)CrossRef

27.

Gualandi, S.: k-Clustering Minimum Biclique Completion via a Hybrid CP and SDP Approach. In: van Hoeve, W.-J., Hooker, J.N. (eds.) Proceedings of the 6th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR), Pittsburgh, May 2009. Lecture Notes in Computer Science, vol. 5547, pp. 87–101. Springer, Heidelberg (2009)

28.

Gualandi, S., Malucelli, F.: Weighted Biclique Completion via CP-SDP Randomized Rounding. In: Bonami, P., Liberti, L., Miller, A., Sartenaer, A. (eds.) Proceedings of the European Workshop on Mixed Integer Nonlinear Programming, Marseille (2010)

29.

Guruswami, V., Raghavendra, P.: Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness. In: Goel, A., Jansen, K., Rolim, J., Rubinfeld, R. (eds.) Proceedings of the 11th International Workshop on Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques (APPROX) Boston, August 2008. Lecture Notes in Computer Science, vol. 5171, pp. 77–90. Springer, Heidelberg (2008)

30.

Halperin, E., Zwick, U.: Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs. Journal of Algorithms 40, 184–211 (2001)CrossRef

31.

Harvey, W.D., Ginsberg, M.L.: Limited Discrepancy Search. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI), pp. 607–615. Morgan Kaufmann (1995)

32.

Helmberg, C.: Fixing Variables in Semidefinite Relaxations. SIAM Journal on Matrix Analysis and Applications 21(3), 952–969 (2000)CrossRef

33.

Hooker, J.: Logic-Based Methods for Optimization - Combining Optimization and Constraint Satisfaction. Wiley (2000)

34.

Hooker, J.N.: Operations Research Methods in Constraint Programming. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, pp. 527–570. Elsevier (2006)

35.

Hooker, J.N.: Integrated methods for optimization. Springer (2007)

36.

Joy, S., Mitchell, J., Borchers, B.: A branch and cut algorithm for MAX-SAT and weighted MAX-SAT. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 35, 519–536 (1997)CrossRef

37.

Karloff, H., Zwick, U.: A 7/8-approximation algorithm for MAX 3SAT? In: Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 406–415. IEEE Computer Society (1997)

38.

Katriel, I., Sellmann, M., Upfal, E., Van Hentenryck, P.: Propagating Knapsack Constraints in Sublinear Time. In: Proceedings of the 22nd National Conference on Artificial Intelligence (AAAI), pp. 231–236. AAAI Press (2007)

39.

de Klerk E., van Maaren, H.: On semidefinite programming relaxations of (2+p)-SAT. Annals of Mathematics and Artificial Intelligence 37, 285–305 (2003)CrossRef

40.

de Klerk, E., Warners, J.P.: Semidefinite Programming Approaches for MAX-2-SAT and MAX-3-SAT: computational perspectives. In: Pardalos, P.M., Migdalas, A., Burkard, R.E. (eds.) Combinatorial and Global Optimization, pp. 161–176. World Scientific (2002)

41.

de Klerk, E., van Maaren, H., Warners, J.P.: Relaxations of the Satisfiability Problem Using Semidefinite Programming. Journal of Automated Reasoning 24, 37–65 (2000)CrossRef

42.

Lau, H.C.: A New Approach for Weighted Constraint Satisfaction. Constraints 7, 151–165 (2002)CrossRef

43.

Laurent, M., Poljak, S., Rendl, F.: Connections between semidefinite relaxations of the max-cut and stable set problems. Mathematical Programming 77, 225–246 (1997)CrossRef

44.

Laurent, M., Rendl, F.: Semidefinite Programming and Integer Programming. In: Aardal, K., Nemhauser, G., Weismantel, R. (eds.) Discrete Optimization, Handbooks in Operations Research and Management Science, pp. 393–514. Elsevier (2005) Also available as Technical Report PNA-R0210, CWI, Amsterdam.

45.

Leahu, L., Gomes, C.P.: Quality of LP-based Approximations for Highly Combinatorial Problems. In: Wallace, M. (ed.) Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming (CP 2004), Toronto, September/October 2004. Lecture Notes in Computer Science, vol. 3258, pp. 377–392. Springer (2004)

46.

Lovász, L.: On the Shannon capacity of a graph. IEEE Transactions on Information Theory 25, 1–7, (1979)CrossRef

47.

Margot, F.: Symmetry in Integer Linear Programming. In: Jünger, M., Liebling, T.M., Naddef, D., Nemhauser, G.L., Pulleyblank, W.R., Reinelt, G., Rinaldi, G., Wolsey, L.A. (eds.) 50 Years of Integer Programming 1958–2008, pp. 647–686. Springer (2010)

48.

Milano, M. (ed.): Constraint and Integer Programming - Toward a Unified Methodology, Operations Research/Computer Science Interfaces, vol. 27. Kluwer Academic Publishers (2003)

49.

Milano, M., van Hoeve, W.J.: Reduced Cost-Based Ranking for Generating Promising Subproblems. In: Van Hentenryck, P. (ed.) Proceedings of the Eighth International Conference on Principles and Practice of Constraint Programming (CP), Ithaca, September 2002. Lecture Notes in Computer Science, vol. 2470, pp. 1–16. Springer (2002)

50.

Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley (1988)

51.

Puget, J.F.: PECOS: a high level constraint programming language. In: Proceedings of the Singapore International Conference on Intelligent Systems (SPICIS’92), Singapore, 28 September- 1 October 1992

52.

Raghavendra, P.: Optimal Algorithms and Inapproximability Results for Every CSP? In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), Victoria, May 2008. pp. 245–254. ACM (2008)

53.

Raghavendra, P., Steurer, D.: Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Atlanta, October 2009. pp. 575–585. IEEE Computer Society (2009)

54.

Raghavendra, P., Steurer, D.: How to Round Any CSP. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Atlanta, October 2009. pp. 586–594. IEEE Computer Society (2009)

55.

Refalo, P.: Linear Formulation of Constraint Programming Models and Hybrid Solvers. In: Dechter, R. (ed.) Proceedings of the Sixth International Conference on Principles and Practice of Constraint Programming (CP), Singapore, September 2000. Lecture Notes in Computer Science, vol. 1894, pp. 369–383. Springer (2000)

56.

Régin, J.-C.: A Filtering Algorithm for Constraints of Difference in CSPs. In: Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI), vol. 1, pp. 362–367. AAAI Press (1994)

57.

Régin, J.-C.: Cost-Based Arc Consistency for Global Cardinality Constraints. Constraints 7, 387–405 (2002)CrossRef

58.

Régin, J.-C.: Global Constraints and Filtering Algorithms. In: Milano, M. (ed.) Constraint and Integer Programming - Toward a Unified Methodology, Series Operations Research/Computer Science Interfaces, vol. 27, 88–136. Kluwer Academic Publishers (2004)

59.

Régin, J.-C.: Modélisation et Contraintes Globales en Programmation par Contraintes. Habilitation thesis, University of Nice (2004)

60.

Rossi, F., van Beek, P., Walsh, T. (eds.): Handbook of Constraint Programming. Elsevier (2006)

61.

Sadler, A., Gervet, C.: Global Filtering for the Disjointness Constraint on Fixed Cardinality Sets. Technical Report TR-IC-PARC-04-02, IC-PARC, Imperial College (2004)

62.

Sellmann, M., Gellermann, T., Wright, R.: Cost-Based Filtering for Shorter Path Constraints. Constraints 12(2), 207–238 (2007)CrossRef

63.

van Beek, P.: Backtracking search algorithms. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, pp. 85–134. Elsevier, 2006.

64.

Van Hentenryck, P., Perron, L., Puget, J.-F.: Search and strategies in OPL. ACM Transactions on Computational Logic 1(2), 285–320 (2000)CrossRef

65.

van Hoeve, W.-J.: A hybrid constraint programming and semidefinite programming approach for the stable set problem. In: Rossi, F. (ed.) Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP 2003), Kinsale, September 2003. Lecture Notes in Computer Science, vol. 2833, pp. 407–421. Springer (2003)

66.

van Hoeve, W.-J.: Exploiting Semidefinite Relaxations in Constraint Programming. Computers and Operations Research 33(10), 2787–2804 (2006)CrossRef

67.

van Hoeve, W.-J., Katriel, I.: Global Constraints. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, pp. 169–208. Elsevier, 2006.

68.

van Hoeve, W.-J., Pesant, G., Rousseau, L.-M.: On global warming: Flow-based soft global constraints. Journal of Heuristics 12(4), 347–373 (2006)CrossRef

69.

Warners, J.: Nonlinear Approaches to Satisfiability Problems. Ph.D. thesis, Technische Universiteit Eindhoven (1999)

70.

Xing, Z., Zhang, W.: MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability. Artificial Intelligence 164(1–2), 47–80 (2005)CrossRef

71.

Zwick, U.: Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables per Constraint. In: Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, 25-27 January 1998

Titel: Semidefinite Programming and Constraint Programming
verfasst von: Willem-Jan van Hoeve
Verlag: Springer US
Buch: Handbook on Semidefinite, Conic and Polynomial Optimization
Print ISBN: 978-1-4614-0768-3

Electronic ISBN: 978-1-4614-0769-0

Copyright-Jahr: 2012
DOI: https://doi.org/10.1007/978-1-4614-0769-0_22

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Premium Partner