×

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.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization

Software:

MiniMaxSat; ToulBar2
PDFBibTeX XMLCite
Full Text: DOI

References:

[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, (Developments in Applied Artificial Intelligence, vol. 22718 (2003), Springer), 217-240
[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
[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
[25] Festa, P.; Pardalos, P.; Resende, M., Feedback set problems, (Handbook of Combinatorial Optimization (1999), Kluwer Academic Publishers), 209-258 · Zbl 1253.90193
[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
[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
[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
[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: Caltech/CMU Pasadena, Tech. Rep. · Zbl 1192.68645
[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
[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
[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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.