Tractability-preserving transformations of global cost functions. (English) Zbl 1385.68040

Summary: Graphical model processing is a central problem in artificial intelligence. The optimization of the combined cost of a network of local cost functions federates a variety of famous problems including CSP, SAT and Max-SAT but also optimization in stochastic variants such as Markov Random Fields and Bayesian networks. Exact solving methods for these problems typically include branch and bound and local inference-based bounds.
In this paper we are interested in understanding when and how dynamic programming based optimization can be used to efficiently enforce soft local consistencies on Global Cost Functions, defined as parameterized families of cost functions of unbounded arity. Enforcing local consistencies in cost function networks is performed by applying so-called Equivalence Preserving Transformations (EPTs) to the cost functions. These EPTs may transform global cost functions and make them intractable to optimize.
We identify as tractable projection-safe those global cost functions whose optimization is and remains tractable after applying the EPTs used for enforcing arc consistency. We also provide new classes of cost functions that are tractable projection-safe thanks to dynamic programming.
We show that dynamic programming can either be directly used inside filtering algorithms, defining polynomially DAG-filterable cost functions, or emulated by arc consistency filtering on a Berge-acyclic network of bounded-arity cost functions, defining Berge-acyclic network-decomposable cost functions. We give examples of such cost functions and we provide a systematic way to define decompositions from existing decomposable global constraints. These two approaches to enforcing consistency in global cost functions are then embedded in a solver for extensive experiments that confirm the feasibility and efficiency of our proposal.


68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q25 Analysis of algorithms and problem complexity
90C27 Combinatorial optimization
90C39 Dynamic programming


SLIDE; ToulBar2
Full Text: DOI arXiv


[1] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network flows: theory, algorithms and applications, (2011), Prentice Hall
[2] Allouche, D.; André, I.; Barbe, S.; Davies, J.; de Givry, S.; Katsirelos, G.; O’Sullivan, B.; Prestwich, S.; Schiex, T.; Traoré, S., Computational protein design as an optimization problem, Artif. Intell., 212, 59-79, (2014) · Zbl 1407.92099
[3] Allouche, D.; Bessière, C.; Boizumault, P.; de Givry, S.; Gutierrez, P.; Lee, J. H.M.; Leung, K.; Loudni, S.; Metivier, J.; Schiex, T.; Yi, W., Tractability and decompositions of global cost functions, (2015), The Chinese University of Hong Kong, Technical report
[4] Allouche, D.; Bessière, C.; Boizumault, P.; de Givry, S.; Gutierrez, P.; Loudni, S.; Metivier, J.; Schiex, T., Decomposing global cost functions, (Proceedings of AAAI’12, (2012)), 407-413
[5] Allouche, D.; de Givry, S.; Katsirelos, G.; Schiex, T.; Zytnicki, M., Anytime hybrid best-first search with tree decomposition for weighted CSP, (Proc. of CP-15, Cork, Ireland, (2015)), 12-28
[6] Beeri, C.; Fagin, R.; Maier, D.; Yannakakis, M., On the desirability of acyclic database schemes, J. ACM, 30, 479-513, (1983) · Zbl 0624.68087
[7] Beldiceanu, N., Pruning for the minimum constraint family and for the number of distinct values constraint family, (Proceedings of CP’01, (2001)), 211-224 · Zbl 1067.68611
[8] Beldiceanu, N.; Carlsson, M.; Debruyne, R.; Petit, T., Reformulation of global constraints based on constraints checkers, Constraints, 10, 339-362, (2005) · Zbl 1103.68804
[9] Beldiceanu, N.; Carlsson, M.; Rampon, J., Global constraint catalog, (2005), Swedish Institute of Computer Science, available at
[10] Beldiceanu, N.; Contejean, E., Introducing global constraints in CHIP, Math. Comput. Model., 20, 97-123, (1994) · Zbl 0816.68048
[11] Beldiceanu, N.; Katriel, I.; Thiel, S., Filtering algorithms for the same constraints, (Proceedings of CPAIOR’04, (2004)), 65-79 · Zbl 1094.68637
[12] Bertelé, U.; Brioshi, F., Nonserial dynamic programming, (1972), Academic Press · Zbl 0244.49007
[13] Bessière, C., Constraint propagation, (Rossi, F.; van Beek, P.; Walsh, T., Handbook of Constraint Programming, (2006), Elsevier), 29-84, Chapter 3
[14] Bessière, C.; Hebrard, E.; Hnich, B.; Kiziltan, Z.; Quimper, C.; Walsh, T., Reformulating global constraints: the SLIDE and REGULAR constraints, (Abstraction, Reformulation, and Approximation, (2007)), 80-92
[15] Bessière, C.; Hebrard, E.; Hnich, B.; Kiziltan, Z.; Walsh, T., SLIDE: a useful special case of the CARDPATH constraint, (Proceedings of ECAI’08, (2008)), 475-479
[16] Bessière, C.; Van Hentenryck, P., To be or not to be ... a global constraint, (Proceedings of CP’03, (2003)), 789-794 · Zbl 1273.68334
[17] Boussemart, F.; Hemery, F.; Lecoutre, C.; Sais, L., Boosting systematic search by weighting constraints, (ECAI, (2004)), 146-150
[18] Cabon, B.; de Givry, S.; Lobjois, L.; Schiex, T.; Warners, J., Radio link frequency assignment, Constraints J., 4, 79-89, (1999) · Zbl 1020.94500
[19] Cooper, M.; de Givry, S.; Sánchez, M.; Schiex, T.; Zytnicki, M.; Werner, T., Soft arc consistency revisited, Artif. Intell., 174, 449-478, (2010) · Zbl 1213.68580
[20] Cooper, M.; Schiex, T., Arc consistency for soft constraints, Artif. Intell., 154, 199-227, (2004) · Zbl 1085.68672
[21] Cooper, M. C., Reduction operations in fuzzy or valued constraint satisfaction, Fuzzy Sets Syst., 134, 311-342, (2003) · Zbl 1031.90072
[22] Cooper, M. C., High-order consistency in valued constraint satisfaction, Constraints, 10, 283-305, (2005) · Zbl 1112.68118
[23] Cornuéjols, G.; Dawande, M., A class of hard small 0-1 programs, (Proceedings of Integer Programming and Combinatorial Optimization, (1998)), 284-293 · Zbl 0910.90220
[24] Culik, K.; Kari, J., Image compression using weighted finite automata, (Borzyszkowski, A. M.; Sokolowski, S., MFCS, (1993), Springer), 392-402
[25] Dasgupta, S.; Papadimitriou, C. H.; Vazirani, U. V., Algorithms, (2007), McGraw-Hill
[26] Dechter, R.; Rish, I., Mini-buckets: a general scheme for bounded inference, J. ACM, 50, 107-153, (2003) · Zbl 1326.68335
[27] Desmet, J.; De Maeyer, M.; Hazes, B.; Lasters, I., The dead-end elimination theorem and its use in protein side-chain positioning, Nature, 356, 539-542, (1992)
[28] Dibangoye, J. S.; Amato, C.; Buffet, O.; Charpillet, F., Optimally solving dec-pomdps as continuous-state mdps, (Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, (2013), AAAI Press), 90-96
[29] Ermon, S.; Gomes, C. P.; Sabharwal, A.; Selman, B., Embed and project: discrete sampling with universal hashing, (Advances in Neural Information Processing Systems, (2013)), 2085-2093
[30] Favier, A.; de Givry, S.; Legarra, A.; Schiex, T., Pairwise decomposition for combinatorial optimization in graphical models, (Proc. of IJCAI-11, (2011)), 2126-2132
[31] Flum, J.; Grohe, M., Parameterized complexity theory, (2006), Springer-Verlag New York Inc.
[32] de Givry, S.; Heras, F.; Zytnicki, M.; Larrosa, J., Existential arc consistency: getting closer to full arc consistency in weighted csps, (Proceedings of IJCAI’05, (2005)), 84-89
[33] de Givry, S.; Prestwich, S.; O’Sullivan, B., Dead-end elimination for weighted CSP, (Proceedings of CP’13, (2013)), 263-272
[34] van Hoeve, W. J.; Pesant, G.; Rousseau, L. M., On global warming: flow-based soft global constraints, J. Heuristics, 12, 347-373, (2006) · Zbl 1100.68623
[35] Hurley, B.; O’Sullivan, B.; Allouche, D.; Katsirelos, G.; Schiex, T.; Zytnicki, M.; de Givry, S., Multi-language evaluation in graphical model optimization, Constraints, (2016), initially submitted to CP-AI-OR’2016 · Zbl 1368.90107
[36] Ishida, N., Game “NONOGRAM”, Math. Seminar, 10, 21-22, (1994), (in Japanese)
[37] Kadioglu, S.; Sellmann, M., Grammar constraints, Constraints, 15, 117-144, (2010) · Zbl 1191.68364
[38] Katsirelos, G.; Narodytska, N.; Walsh, T., The weighted GRAMMAR constraints, Ann. Oper. Res., 184, 179-207, (2011) · Zbl 1230.68110
[39] Krom, M., The decision problem for a class of first-order formulas in which all disjunctions are binary, Math. Log. Q., 13, 15-20, (1967) · Zbl 0162.31601
[40] Larrosa, J., Boosting search with variable elimination, (Proceedings of CP’00, (2000)), 291-305 · Zbl 1044.68777
[41] Larrosa, J.; Schiex, T., In the quest of the best form of local consistency for weighted CSP, (Proceedings of IJCAI’03, (2003)), 239-244
[42] Larrosa, J.; Schiex, T., Solving weighted CSP by maintaining arc consistency, Artif. Intell., 159, 1-26, (2004) · Zbl 1086.68592
[43] Lauriere, J. L., A language and a program for stating and solving combinatorial problems, Artif. Intell., 10, 29-127, (1978) · Zbl 0374.68060
[44] Lecoutre, C.; Roussel, O.; Dehani, D. E., Wcsp integration of soft neighborhood substitutability, (Proceedings of CP’12, (2012)), 406-421
[45] Lecoutre, C.; Saïs, L.; Tabary, S.; Vidal, V., Reasoning from last conflict(s) in constraint programming, Artif. Intell., 173, 1592-1614, (2009) · Zbl 1185.68645
[46] Lee, J. H.M.; Leung, K. L., Towards efficient consistency enforcement for global constraints in weighted constraint satisfaction, (Proceedings of IJCAI’09, (2009)), 559-565
[47] Lee, J. H.M.; Leung, K. L., A stronger consistency for soft global constraints in weighted constraint satisfaction, (Proceedings of AAAI’10, (2010)), 121-127
[48] Lee, J. H.M.; Leung, K. L., Consistency techniques for global cost functions in weighted constraint satisfaction, J. Artif. Intell. Res., 43, 257-292, (2012) · Zbl 1237.68188
[49] Lee, J. H.M.; Leung, K. L.; Shum, Y. W., Consistency techniques for polytime linear global cost functions in weighted constraint satisfaction, Constraints, 19, 270-308, (2014) · Zbl 1316.90027
[50] Lee, J. H.M.; Leung, K. L.; Wu, Y., Polynomially decomposable global cost functions in weighted constraint satisfaction, (Proceedings of AAAI’12, (2012)), 507-513
[51] Lee, J. H.M.; Shum, Y. W., Modeling soft global constraints as linear programs in weighted constraint satisfaction, (Proceedings of ICTAI’11, (2011)), 305-312
[52] Oplobedu, A.; Marcovitch, J.; Tourbier, Y., CHARME: un langage industriel de programmation par contraintes, illustré par une application chez renault, (Proceedings of the Ninth International Workshop on Expert Systems and Their Applications: General Conference, (1989)), 55-70
[53] Papadimitriou, C.; Yannakakis, M., Optimization, approximation, and complexity classes, J. Comput. Syst. Sci., 43, 425-440, (1991) · Zbl 0765.68036
[54] Parrello, B.; Kabat, W.; Wos, L., Job-shop scheduling using automated reasoning: a case study of the car-sequence problem, J. Autom. Reason., 2, 1-42, (1986)
[55] Pesant, G., A regular language membership constraint for finite sequences of variables, (Proceedings of CP’04, (2004)), 482-495 · Zbl 1152.68573
[56] Petit, T.; Régin, J. C.; Bessière, C., Specific filtering algorithm for over-constrained problems, (Proceedings of CP’01, (2001)), 451-463 · Zbl 1067.68663
[57] Petit, T.; Régin, J. C.; Bessiere, C., Specific filtering algorithms for over-constrained problems, (CP, (2001)), 451-463 · Zbl 1067.68663
[58] Régin, J. C., Generalized arc consistency for global cardinality constraints, (Proceedings of AAAI’96, (1996)), 209-215
[59] Rossi, F.; van Beek, P.; Walsh, T., Handbook of constraint programming, (2006), Elsevier · Zbl 1175.90011
[60] Sánchez, M.; de Givry, S.; Schiex, T., Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques, Constraints, 13, 130-154, (2008) · Zbl 1144.92324
[61] Schiex, T., Arc consistency for soft constraints, (Principles and Practice of Constraint Programming - CP 2000, (2000)), 411-424 · Zbl 1044.68797
[62] Schiex, T.; Fargier, H.; Verfaillie, G., Valued constraint satisfaction problems: hard and easy problems, (Proceedings of IJCAI’95, (1995)), 631-637
[63] Simoncini, D.; Allouche, D.; de Givry, S.; Delmas, C.; Barbe, S.; Schiex, T., Guaranteed discrete energy optimization on large protein design problems, J. Chem. Theory Comput., (2015)
[64] Trick, M. A., A dynamic programming approach for consistency and propagation for knapsack constraints, Ann. Oper. Res., 118, 73-84, (2003) · Zbl 1027.90075
[65] Zytnicki, M.; Gaspin, C.; Schiex, T., Bounds arc consistency for weighted csps, J. Artif. Intell. Res., 35, 593-621, (2009) · Zbl 1192.68656
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.