zbMATH — the first resource for mathematics

Soft arc consistency revisited. (English) Zbl 1213.68580
Summary: The Valued Constraint Satisfaction Problem (VCSP) is a generic optimization problem defined by a network of local cost functions defined over discrete variables. It has applications in Artificial Intelligence, Operations Research, Bioinformatics and has been used to tackle optimization problems in other graphical models (including discrete Markov Random Fields and Bayesian Networks). The incremental lower bounds produced by local consistency filtering are used for pruning inside Branch and Bound search.
In this paper, we extend the notion of arc consistency by allowing fractional weights and by allowing several arc consistency operations to be applied simultaneously. Over the rationals and allowing simultaneous operations, we show that an optimal arc consistency closure can theoretically be determined in polynomial time by reduction to linear programming. This defines Optimal Soft Arc Consistency (OSAC).
To reach a more practical algorithm, we show that the existence of a sequence of arc consistency operations which increases the lower bound can be detected by establishing arc consistency in a classical Constraint Satisfaction Problem (CSP) derived from the original cost function network. This leads to a new soft arc consistency method, called, Virtual Arc Consistency which produces improved lower bounds compared with previous techniques and which can solve submodular cost functions.
These algorithms have been implemented and evaluated on a variety of problems, including two difficult frequency assignment problems which are solved to optimality for the first time. Our implementation is available in the open source toulbar2 platform.

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
MiniMaxSat; ToulBar2
Full Text: DOI
[1] M.S. Affane, H. Bennaceur, A weighted arc consistency technique for Max-CSP, in: Proc. of the 13th ECAI, Brighton, United Kingdom, 1998, pp. 209-213
[2] Ahuja, R.K.; Magnanti, T.; Orlin, J., Network flows: theory, algorithms, and applications, (1993), Prentice Hall · Zbl 1201.90001
[3] Apt, K., The essence of constraint propagation, Theoretical computer science, 221, 1-2, 179-210, (1999) · Zbl 0930.68164
[4] Bennaceur, H.; Osmani, A., Computing lower bounds for MAX-CSP problems, (), 217-240
[5] C. Bessière, Arc-consistency in dynamic constraint satisfaction problems, in: Proc. of AAAI’91, Anaheim, CA, 1991, pp. 221-226
[6] C. Bessière, J.-C. Régin, Refining the basic constraint propagation algorithm, in: Proc. IJCAI’2001, 2001, pp. 309-315
[7] Boros, E.; Hammer, P., Pseudo-Boolean optimization, Discrete appl. math., 123, 155-225, (2002) · Zbl 1076.90032
[8] Lecoutre, C.; Saïs, L.; Tabary, S.; Vidal, V., Reasoning from last conflict(s) in constraint programming, Artificial intelligence, 173, 18, 1592-1614, (2009) · Zbl 1185.68645
[9] Cabon, B.; de Givry, S.; Lobjois, L.; Schiex, T.; Warners, J., Radio link frequency assignment, Constraints, 4, 79-89, (1999) · Zbl 1020.94500
[10] Cohen, D.A.; Cooper, M.C.; Jeavons, P.G.; Krokhin, A.A., A maximal tractable class of soft constraints, Journal of artificial intelligence research, 22, 1-22, (2004) · Zbl 1080.68658
[11] Cohen, D.A.; Cooper, M.C.; Jeavons, P.G.; Krokhin, A.A., The complexity of soft constraint satisfaction, Artificial intelligence, 170, 11, 983-1016, (Aug. 2006)
[12] Cooper, M.C., Reduction operations in fuzzy or valued constraint satisfaction, Fuzzy sets and systems, 134, 3, 311-342, (2003) · Zbl 1031.90072
[13] Cooper, M.C., Cyclic consistency: a local reduction operation for binary valued constraints, Artificial intelligence, 155, 1-2, 69-92, (2004) · Zbl 1085.68671
[14] Cooper, M.C., High-order consistency in valued constraint satisfaction, Constraints, 10, 283-305, (2005) · Zbl 1112.68118
[15] Cooper, M.C., Minimization of locally-defined submodular functions by optimal soft arc consistency, Constraints, 13, 4, (2008) · Zbl 1180.90262
[16] M.C. Cooper, S. de Givry, T. Schiex, Optimal soft arc consistency, in: Proc. of IJCAI’2007, Hyderabad, India, Jan. 2007, pp. 68-73
[17] M.C. Cooper, M. de Roquemaurel, P. Régnier, A weighted CSP approach to cost-optimal planning. Tech. Rep. RR-2009-28-FR, IRIT, Toulouse, France, 2009
[18] M.C. Cooper, P. Jeavons, A. Salamon, Hybrid tractable CSPs which generalise tree structure, in: Proc. ECAI’08, 2008, pp. 530-534
[19] Cooper, M.C.; Schiex, T., Arc consistency for soft constraints, Artificial intelligence, 154, 1-2, 199-227, (2004) · Zbl 1085.68672
[20] Cunningham, W., Minimum cuts, modular functions, and matroid polyhedra, Networks, 15, 2, 205-215, (1985) · Zbl 0581.90059
[21] S. de Givry, Minorants de problèmes de minimisation de violation de contraintes : recherche de bonnes relaxations à l’aide de méthodes incomplètes, in: Proc. of JNPC-99, Lyon, France, 1999
[22] S. de Givry, F. Heras, J. Jarrosa, E. Rollon, T. Schiex, The SoftCSP and Max-SAT benchmarks and algorithms web site, 2003, carlit.toulouse.inra.fr/cgi-bin/awki.cgi/softcsp
[23] S. de Givry, T. Schiex, G. Verfaillie, Exploiting tree decomposition and soft local consistency in weighted CSP, in: Proc. of the National Conference on Artificial Intelligence, AAAI-2006, 2006, pp. 22-27
[24] S. de Givry, M. Zytnicki, F. Heras, J. Larrosa, Existential arc consistency: getting closer to full arc consistency in weighted CSPs, in: Proc. of IJCAI-05, Edinburgh, Scotland, 2005, pp. 84-89
[25] Festa, P.; Pardalos, P.; Resende, M., Feedback set problems, (), 209-258 · Zbl 1253.90193
[26] S. Fujishige, T. Hayashi, S. Isotani, The minimum-norm-point algorithm applied to submodular function minimization and linear programming, Tech. Rep., Research Institute for Mathematical Sciences, Kyoto, Japan, 2006
[27] Fujishige, S.; Isotani, S., New maximum flow algorithms by ma orderings and scaling, Journal of the operations research society of Japan, 46, 243-250, (2003) · Zbl 1042.90050
[28] Fujishige, S.; Patkar, S.B., Realization of set functions as cut functions of graphs and hypergraphs, Discrete math., 226, 199-210, (2001) · Zbl 0969.90015
[29] Goldfarb, D.; Grigoriadis, M.D., A computational comparison of the dinic and network simplex methods for maximum flow, Annals of oper. res., 13, 83-123, (1988)
[30] Hammer, P.; Hansen, P.; Simeone, B., Roof duality, complementation and persistency in quadratic 0-1 optimization, Math. programming, 28, 121-155, (1984) · Zbl 0574.90066
[31] F. Heras, J. Larrosa, A. Oliveras, MiniMaxSat: A new weighted Max-SAT solver, in: Proc. of SAT’2007, Lisbon, Portugal, May 2007, in: LNCS, vol. 4501, pp. 41-55 · Zbl 1183.68578
[32] Jeavons, P.; Cooper, M., Tractable constraints on ordered domains, Artificial intelligence, 79, 2, 327-339, (Dec. 1995)
[33] Karmarkar, N., A new polynomial time algorithm for linear programming, Combinatorica, 4, 4, 373-395, (1984) · Zbl 0557.90065
[34] L. Khatib, P. Morris, R. Morris, F. Rossi, Temporal constraint reasoning with preferences, in: Proc. of the 17th IJCAI, Seattle, WA, 2001, pp. 322-327
[35] Kolmogorov, V., Convergent tree-reweighted message passing for energy minimization, IEEE trans. on pattern analysis and machine intelligence, 28, 10, 1568-1583, (2006)
[36] Koster, A.; van Hoesel, S.; Kolen, A., The partial constraint satisfaction problem: facets and lifting theorems, Oper. res. lett., 23, 3-5, 89-97, (1998) · Zbl 0957.90095
[37] A. Koster, S. van Hoesel, A. Kolen, Solving frequency assignment problems via tree-decomposition, Tech. Rep. RM/99/011, Universiteit Maastricht, Maastricht, The Netherlands, 1999 · Zbl 1038.90086
[38] Koster, A.M.C.A., Frequency assignment: models and algorithms, (Nov. 1999), Ph.D. thesis, University of Maastricht, The Netherlands, available at
[39] Koval, V.K.; Schlesinger, M.I., Dvumernoe programmirovanie v zadachakh analiza izobrazheniy, USSR Academy of science automatics and telemechanics, 8, 149-168, (1976), (in Russian)
[40] Kratica, J.; Tosic, D.; Filipovic, V.; Ljubic, I., Solving the simple plant location problems by genetic algorithm, RAIRO operations research, 35, 127-142, (2001) · Zbl 0995.90055
[41] Krause, A.; Guestrin, C., IJCAI tutorial on intelligent information gathering and submodular function optimization, (2009), Caltech/CMU Pasadena, Tech. Rep. · Zbl 1192.68645
[42] J. Larrosa, Boosting search with variable elimination, in: Principles and Practice of Constraint Programming - CP 2000, Singapore, Sep. 2000, in: LNCS, vol. 1894, pp. 291-305 · Zbl 1044.68777
[43] J. Larrosa, S. de Givry, F. Heras, M. Zytnicki, Existential arc consistency: getting closer to full arc consistency in weighted CSPs, in: Proc. of the 19th IJCAI, Edinburgh, Scotland, Aug. 2005, pp. 84-89
[44] J. Larrosa, T. Schiex, In the quest of the best form of local consistency for weighted CSP, in: Proc. of the 18th IJCAI, Acapulco, Mexico, Aug. 2003, pp. 239-244
[45] C.M. Li, F. Manyà, J. Planes, Exploiting unit propagation to compute lower bounds in branch and bound Max-SAT solvers, in: Proc of CP’2005, Sitges, Spain, 2005, in: LNCS, vol. 3709, pp. 403-414 · Zbl 1153.68470
[46] R. Mohr, G. Masini, Good old discrete relaxation, in: Proc. of the 8th ECAI, Munchen, FRG, 1988, pp. 651-656
[47] Orlin, J.B., A faster strongly polynomial time algorithm for submodular function minimization, Mathematical programming ser. A, 118, 2, 237-251, (2009) · Zbl 1179.90290
[48] J.-C. Régin, T. Petit, C. Bessière, J.-F. Puget, New lower bounds of constraint violations for over-constrained problems, in: Proc. of CP-01, Paphos, Cyprus, Dec. 2001, in: LNCS, vol. 2239, pp. 332-345
[49] M. Sanchez, D. Allouche, S. de Givry, T. Schiex, Russian doll search with tree decomposition, in: Proc. of IJCAI’09, Pasadena, CA, USA, 2009
[50] Sanchez, M.; de Givry, S.; Schiex, T., Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques, Constraints, 13, 1, 130-154, (2008) · Zbl 1144.92324
[51] T. Schiex, Arc consistency for soft constraints, in: Principles and Practice of Constraint Programming - CP 2000, Singapore, Sep. 2000, in: LNCS, vol. 1894, pp. 411-424 · Zbl 1044.68797
[52] T. Schiex, H. Fargier, G. Verfaillie, Valued constraint satisfaction problems: hard and easy problems, in: Proc. of the 14th IJCAI, Montréal, Canada, Aug. 1995, pp. 631-637
[53] D. Schlesinger, Exact solution of permuted submodular MinSum problems, in: Energy Minimization Methods in Computer Vision and Pattern Recognition, in: LNCS, vol. 4679, Aug. 2007, pp. 28-38
[54] Schlesinger, M., Sintaksicheskiy analiz dvumernykh zritelnikh signalov v usloviyakh pomekh, Kibernetika, 4, 113-130, (1976)
[55] Wainwright, M.; Jaakkola, T.; Willsky, A., MAP estimation via agreement on (hyper)trees: message passing and linear programming approaches, IEEE trans. on information theory, 51, 11, 3697-3717, (2005) · Zbl 1318.94025
[56] Werner, T., A linear programming approach to MAX-sum problem: A review, IEEE trans. on pattern recognition and machine intelligence, 29, 7, 1165-1179, (Jul. 2007)
[57] Zytnicki, M.; Gaspin, C.; de Givry, S.; Schiex, T., Bounds arc consistency for weighted csps, Journal of artificial intelligence research, 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.