nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Clique Cuts in Weighted Constraint Satisfaction

verfasst von : Simon de Givry, George Katsirelos

Erschienen in: Principles and Practice of Constraint Programming

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In integer programming, cut generation is crucial for improving the tightness of the linear relaxation of the problem. This is relevant for weighted constraint satisfaction problems (WCSPs) in which we use approximate dual feasible solutions to produce lower bounds during search. Here, we investigate using one class of cuts in WCSP: clique cuts. We show that clique cuts are likely to trigger suboptimal behavior in the specialized algorithms that are used in WCSP for generating dual bounds and show how these problems can be corrected. At the same time, the additional structure present in WCSP allows us to slightly generalize these cuts. Finally, we show that cliques exist in instances from several benchmark families and that exploiting them can lead to substantial performance improvement.

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 "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

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 Conjunctions of Among Constraints

Nächstes Kapitel Arc Consistency via Linear Programming

This is the micro-structure of the WCSP, restricted only to binary tuples with infinite cost.

In this case, triangle-based consistencies [31] achieve the same effect, but not in arbitrary arity cliques.

Version 4.4.0, using free search.

Using parameter -pe parallel_smp 2 on a SUN Grid Engine to ensure half-load of the cores on the cluster.

Allouche, D., de Givry, S., Katsirelos, G., Schiex, T., Zytnicki, M.: Anytime hybrid best-first search with tree decomposition for weighted CSP. In: Pesant, G. (ed.) CP 2015. LNCS, vol. 9255, pp. 12–29. Springer, Cham (2015). doi:10.1007/978-3-319-23219-5_2

Allouche, D., Bessière, C., Boizumault, P., de Givry, S., Gutierrez, P., Lee, J.H., Leung, K.L., Loudni, S., Métivier, J.P., Schiex, T., Wu, Y.: Tractability-preserving transformations of global cost functions. Artif. Intell. 238, 166–189 (2016)MathSciNetCrossRefMATH

Anstegui Gil, C.: Complete SAT solvers for many-valued CNF formulas. Ph.D. thesis, University of Lleida (2004)

Atamtürk, A., Nemhauser, G.L., Savelsbergh, M.W.: Conflict graphs in solving integer programming problems. Eur. J. Oper. Res. 121(1), 40–55 (2000)MathSciNetCrossRefMATH

Biere, A., Le Berre, D., Lonca, E., Manthey, N.: Detecting cardinality constraints in CNF. In: Sinz, C., Egly, U. (eds.) SAT 2014. LNCS, vol. 8561, pp. 285–301. Springer, Cham (2014). doi:10.1007/978-3-319-09284-3_22

Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575–577 (1973)CrossRefMATH

Chvatal, V.: A greedy heuristic for the set-covering problem. Math. Oper. Res. 4(3), 233–235 (1979)MathSciNetCrossRefMATH

Cooper, M., de Givry, S., Sanchez, M., Schiex, T., Zytnicki, M.: Virtual arc consistency for weighted CSP. In: Proceedings of AAAI-2008, Chicago, IL (2008)

Cooper, M., de Givry, S., Sanchez, M., Schiex, T., Zytnicki, M., Werner, T.: Soft arc consistency revisited. Artif. Intell. 174(7–8), 449–478 (2010)MathSciNetCrossRefMATH

10.

Davies, J., Bacchus, F.: Solving MAXSAT by solving a sequence of simpler SAT instances. In: Lee, J. (ed.) CP 2011. LNCS, vol. 6876, pp. 225–239. Springer, Heidelberg (2011). doi:10.1007/978-3-642-23786-7_19 CrossRef

11.

Davies, J., Bacchus, F.: Postponing optimization to speed up MAXSAT solving. In: Schulte, C. (ed.) CP 2013. LNCS, vol. 8124, pp. 247–262. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40627-0_21 CrossRef

12.

Dechter, R., Mateescu, R.: AND/OR search spaces for graphical models. Artif. Intell. 171(2), 73–106 (2007)MathSciNetCrossRefMATH

13.

Dixon, H.E.: Automating psuedo-Boolean inference within a DPLL framework. Ph.D. thesis, University of Oregon (2004)

14.

de Givry, S., Prestwich, S.D., O’Sullivan, B.: Dead-end elimination for weighted CSP. In: Schulte, C. (ed.) CP 2013. LNCS, vol. 8124, pp. 263–272. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40627-0_22 CrossRef

15.

de Givry, S., Schiex, T., Verfaillie, G.: Exploiting tree decomposition and soft local consistency in weighted CSP. In: Proceedings of AAAI-2006, Boston, MA (2006)

16.

de Givry, S., Zytnicki, M., Heras, F., Larrosa, J.: Existential arc consistency: getting closer to full arc consistency in weighted CSPs. In: Proceedings of IJCAI-2005, Edinburgh, Scotland, pp. 84–89 (2005)

17.

Globerson, A., Jaakkola, T.: Fixing max-product: convergent message passing algorithms for MAP LP-relaxations. In: Proceedings of NIPS, Vancouver, Canada (2007)

18.

van Hoeve, W.J., Pesant, G., Rousseau, L.: On global warming: flow-based soft global constraints. J. Heuristics 12(4–5), 347–373 (2006)CrossRefMATH

19.

Hurley, B., O’Sullivan, B., Allouche, D., Katsirelos, G., Schiex, T., Zytnicki, M., de Givry, S.: Multi-language evaluation of exact solvers in graphical model discrete optimization. Constraints 21(3), 413–434 (2016)MathSciNetCrossRefMATH

20.

Jégou, P., Terrioux, C.: Hybrid backtracking bounded by tree-decomposition of constraint networks. Artif. Intell. 146(1), 43–75 (2003)MathSciNetCrossRefMATH

21.

Kask, K., Dechter, R.: Branch and bound with mini-bucket heuristics. In: Proceedings of IJCAI-1999. vol. 99, pp. 426–433 (1999)

22.

Khemmoudj, M.O.I., Bennaceur, H.: Clique inference process for solving Max-CSP. Eur. J. Oper. Res. 199(3), 665–673 (2009)MathSciNetCrossRefMATH

23.

Kolmogorov, V.: Convergent tree-reweighted message passing for energy minimization. IEEE Pattern Anal. Mach. Intell. 28(10), 1568–1583 (2006)CrossRef

24.

Larrosa, J.: Boosting search with variable elimination. In: Dechter, R. (ed.) CP 2000. LNCS, vol. 1894, pp. 291–305. Springer, Heidelberg (2000). doi:10.1007/3-540-45349-0_22 CrossRef

25.

Larrosa, J., Schiex, T.: In the quest of the best form of local consistency for weighted CSP. In: Proceedings of 18th IJCAI, Acapulco, Mexico, pp. 239–244 (2003)

26.

Lecoutre, C., Roussel, O., Dehani, D.E.: WCSP integration of soft neighborhood substitutability. In: Milano, M. (ed.) CP 2012. LNCS, pp. 406–421. Springer, Heidelberg (2012). doi:10.1007/978-3-642-33558-7_31 CrossRef

27.

Lee, J.H.M., Leung, K.L.: Consistency techniques for global cost functions in weighted constraint satisfaction. J. Artif. Intell. R. 43, 257–292 (2012)MATH

28.

Lee, J.H., Leung, K.L.: A stronger consistency for soft global constraints in weighted constraint satisfaction. In: Proceedings of AAAI-2010, Atlanta, USA (2010)

29.

Marinescu, R., Dechter, R.: AND/OR branch-and-bound for graphical models. In: Proceedings of IJCAI-2005, Edinburgh, Scotland, UK, pp. 224–229 (2005)

30.

Narodytska, N., Bacchus, F.: Maximum satisfiability using core-guided MAXSAT resolution. In: Proceedings of AAAI-2014, Quebec City, Canada, pp. 2717–2723 (2014)

31.

Nguyen, H., Bessiere, C., de Givry, S., Schiex, T.: Triangle-based consistencies for cost function networks. Constraints 22(2), 230–264 (2016)MathSciNetCrossRef

32.

Prusa, D., Werner, T.: Universality of the local marginal polytope. In: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, pp. 1738–1743 (2013)

33.

Quimper, C.-G., Walsh, T.: Global grammar constraints. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 751–755. Springer, Heidelberg (2006). doi:10.1007/11889205_64 CrossRef

34.

Quimper, C., Walsh, T.: Decompositions of grammar constraints. CoRR abs/0903.0470 (2009)

35.

Sánchez, M., de Givry, S., Schiex, T.: Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques. Constraints 13(1), 130–154 (2008)MathSciNetCrossRefMATH

36.

Schlesinger, M.I.: Syntactic analysis of two-dimensional visual signals in noisy conditions. Kibernetika 4, 113–130 (1976). (in Russian)

37.

Sontag, D., Choe, D., Li, Y.: Efficiently searching for frustrated cycles in MAP inference. In: Proceedings of UAI, pp. 795–804 (2012)

38.

Sontag, D., Meltzer, T., Globerson, A., Weiss, Y., Jaakkola, T.: Tightening LP relaxations for MAP using message-passing. In: Proceedings of UAI, pp. 503–510 (2008)

39.

Werner, T.: A linear programming approach to max-sum problem: a review. IEEE Trans. Pattern Anal. Mach. Intell. 29(7), 1165–1179 (2007). https://doi.org/10.1109/TPAMI.2007.1036 CrossRef

Titel: Clique Cuts in Weighted Constraint Satisfaction
verfasst von: Simon de Givry
George Katsirelos
Verlag: Springer International Publishing
Buch: Principles and Practice of Constraint Programming
Print ISBN: 978-3-319-66157-5

Electronic ISBN: 978-3-319-66158-2

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-66158-2_7

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 "Technik"

Springer Professional "Wirtschaft"

Premium Partner