×

Generic incremental algorithms for local search. (English) Zbl 1211.68374

Summary: When a new (global) constraint is introduced in local search, measures for the penalty and variable conflicts of that constraint must be defined, and incremental algorithms for maintaining these measures must be implemented. These are complicated and time-consuming tasks, which clearly reduces the productivity of the local-search practitioner. We introduce a generic scheme that, from a description of a constraint in monadic existential second-order logic extended with counting, automatically gives penalty and variable-conflict measures for such a constraint, as well as incremental algorithms for maintaining these measures. We prove that our variable-conflict measure for a variable \(x\) is lower-bounded by the maximum penalty decrease that may be achieved by only changing the value of \(x\), as well as upper bounded by the penalty measure. Without these properties, the local search performance may degrade. We also demonstrate the usefulness of the approach by replacing a built-in global constraint by a modelled version, while still obtaining competitive results in terms of runtime and robustness. This is especially attractive when a particular (global) constraint is not built in.

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
03B15 Higher-order logic; type theory (MSC2010)
03B70 Logic in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aarts, E., & Lenstra, J. K. (Eds.) (1997). Local search in combinatorial optimization. New York: Wiley. · Zbl 0869.00019
[2] Ågren, M., Flener, P., & Pearson, J. (2005). Incremental algorithms for local search from existential second-order logic. In P. van Beek (Ed.), Proceedings of CP’05. LNCS (Vol. 3709, pp. 47–61). Berlin Heidelberg New York: Springer. · Zbl 1153.68441
[3] Ågren, M., Flener, P., & Pearson, J. (2005). Set variables and local search. In R. Barták & M. Milano (Eds.), Proceedings of CP-AI-OR’05. LNCS (Vol. 3524, pp. 19–33). Berlin Heidelberg New York: Springer. · Zbl 1133.68424
[4] Ågren, M., Flener, P., & Pearson, J. (2006). Inferring variable conflicts for local search. In F. Benhamou (Ed.), Proceedings of CP’06. LNCS (Vol. 4204, pp. 665–669). Berlin Heidelberg New York: Springer. · Zbl 1160.68536
[5] Azevedo, F., & Barahona, P. (2000). Applications of an extended set constraint solver. In Proceedings of the ERCIM / CompulogNet Workshop on Constraints. · Zbl 0983.68672
[6] Bohlin, M. (2004). Design and Implementation of a Graph-based Constraint Model for Local Search. PhL thesis, Mälardalen University, Västerås, Sweden.
[7] Galinier, P., & Hao, J.-K. (2000). A general approach for constraint solving by local search. In Proceedings of CP-AI-OR’00. · Zbl 1076.68071
[8] Gervet, C. (1997). Interval propagation to reason about sets: Definition and implementation of a practical language. Constraints, 1(3), 191–244. · Zbl 0870.68039 · doi:10.1007/BF00137870
[9] Glover, F., & Laguna, M. (1993). Tabu search. In Modern Heuristic Techniques for Combinatorial Problems (pp. 70–150). New York: Wiley. · Zbl 0774.90033
[10] Immerman, N. (1998). Descriptive complexity. Springer. · Zbl 0945.03546
[11] Michel, L., & Van Hentenryck, P. (1997). Localizer: A modeling language for local search. In G. Smolka (Ed.), Proceedings of CP’97. LNCS (Vol. 1330, pp. 237–251). Berlin Heidelberg New York: Springer. · Zbl 1092.90534
[12] Michel, L., & Van Hentenryck, P. (2002). A constraint-based architecture for local search. ACM SIGPLAN Not., 37(11), 101–110 (Proceedings of OOPSLA’02). · doi:10.1145/583854.582430
[13] Nareyek, A. (2001). Using global constraints for local search. In E. C. Freuder & R. J. Wallace (Eds.), Constraint programming and large scale discrete optimization. DIMACS: Series in discrete mathematics and theoretical computer science (Vol. 57, pp. 9–28). Providence, RI: American Mathematical Society. · Zbl 0983.90053
[14] Puget, J.-F. (1996). Finite set intervals. In Proceedings of CP’96 Workshop on Set Constraints.
[15] Smith, B. M., Brailsford, S. C., Hubbard, P. M., & Williams, H. P. (1996). The progressive party problem: Integer linear programming and constraint programming compared. Constraints, 1, 119–138. · Zbl 05475104 · doi:10.1007/BF00143880
[16] Tack, G., Schulte, C., & Smolka, G. (2006). Generating propagators for finite set constraints. In F. Benhamou (Ed.), Proceedings of CP’06. LNCS (Vol. 4204, pp. 575–589). Berlin Heidelberg New York: Springer. · Zbl 1160.68387
[17] Van Hentenryck, P., & Michel, L. (2005). Constraint-based local search. The MIT Press. · Zbl 1153.90582
[18] Van Hentenryck, P., & Michel, L. (2006). Differentiable invariants. In F. Benhamou (Ed.), Proceedings of CP’06. LNCS (Vol. 4204, pp. 604–619). Berlin Heidelberg New York: Springer. · Zbl 1160.68569
[19] Van Hentenryck, P., Michel, L., & Liu, L. (2004). Constraint-based combinators for local search. In M. Wallace (Ed.), Proceedings of CP’04. LNCS (Vol. 3258, pp. 47–61). Berlin Heidelberg New York: Springer. · Zbl 1152.68589
[20] Walser, J. P. (1999). Integer optimization by local search: A domain-independent approach. In LNCS (Vol. 1637). Berlin Heidelberg New York: Springer. · Zbl 0934.90053
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.