AllDiff-LS: solving alldifferent constraints with efficient local search

Abstract

The alldifferent constraint is one of the most essential global constraints that has been used to model many classic Constraint Satisfaction Problems (CSPs). To tackle this constraint, previous work generally focuses on proposing filtering algorithms to reduce the value domain of variables, thereby pruning the backtracking search. However, due to the inherent complexity of alldifferent constraints, it remains challenging to solve CSPs containing large-scale alldifferent constraints for the existing search-based solvers. In this paper, we propose an efficient local search algorithm, called AllDiff-LS. We first represent the set of alldifferent constraints as graphs and simplify the graphs by two polynomial-time reduction rules. Afterward, we propose a new two-step strategy for selecting moves, as well as the carefully crafted tabu and restart strategies, to enable the algorithm to explore the search space more efficiently. Experiments on a representative set of benchmarks show that AllDiff-LS successfully solves more instances compared with state-of-the-art complete and heuristic methods, especially on large-scale instances, with much less running time.

Graphical abstract

Keywords

alldifferent constraints / local search / constraint satisfaction problems

References

[1] Lauriere J L . A language and a program for stating and solving combinatorial problems. Artificial Intelligence, 1978, 10( 1): 29–127

[2] Kumar S R, Russell A, Sundaram R . Approximating Latin square extensions. Algorithmica, 1999, 24( 2): 128–138

[3] Colbourn C J, Klove T, Ling A C H . Permutation arrays for powerline communication and mutually orthogonal Latin squares. IEEE Transactions on Information Theory, 2004, 50( 6): 1289–1291

[4] Barnier N, Brisset P . Graph coloring for air traffic flow management. Annals of Operations Research, 2004, 130( 1−4): 163–178

[5] Apt K R . The essence of constraint propagation. Theoretical Computer Science, 1999, 221( 1−2): 179–210

[6] Van Hoeve W J. The alldifferent constraint: a survey. 2001, arXiv preprint arXiv: cs/0105015

[7] Régin J C. A filtering algorithm for constraints of difference in CSPs. In: Proceedings of the 12th National Conference on Artificial Intelligence. 1994, 362–367

[8] Zhang X, Li Q, Zhang W. A fast algorithm for generalized arc consistency of the alldifferent constraint. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence. 2018, 1398–1403

[9] Zhang X, Gao J, Lv Y, Zhang W. Early and efficient identification of useless constraint propagation for alldifferent constraints. In: Proceedings of the 29th International Conference on International Joint Conferences on Artificial Intelligence. 2021, 157

[10] Li Z, Wang Y, Li Z. A bitwise GAC algorithm for alldifferent constraints. In: Proceedings of the 32nd International Joint Conference on Artificial Intelligence. 2023, 221

[11] Zhen L, Li Z, Li Y, Li H. Eliminating the computation of strongly connected components in generalized arc consistency algorithm for alldifferent constraint. In: Proceedings of the 32nd International Joint Conference on Artificial Intelligence. 2023, 228

[12] Codognet P, Diaz D. Yet another local search method for constraint solving. In: Steinhöfel K, ed. Stochastic Algorithms: Foundations and Applications: International Symposium. Berlin, Heidelberg: Springer, 2001, 73–90

[13] Hoos H H, Tsang E . Local search methods. Foundations of Artificial Intelligence, 2006, 2: 135–167

[14] Liu B, Yuan M, You H . A hybrid-order local search algorithm for set k-cover problem in wireless sensor networks. Frontiers of Computer Science, 2023, 17( 3): 173402

[15] Jiang L, Ouyang D, Zhang Q, Zhang L . DeciLS-PBO: an effective local search method for pseudo-Boolean optimization. Frontiers of Computer Science, 2024, 18( 2): 182326

[16] Björdal G, Monette J N, Flener P, Pearson J . A constraint-based local search backend for MiniZinc. Constraints, 2015, 20( 3): 325–345

[17] Glover F, Laguna M. Tabu Search. New York: Springer, 1997, 2093–2229

[18] Wang Y, Cai S, Yin M. Two efficient local search algorithms for maximum weight clique problem. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence. 2016, 805–811

[19] Pan S, Wang Y, Yin M. A fast local search algorithm for the Latin square completion problem. In: Proceedings of the 36th AAAI Conference on Artificial Intelligence. 2022, 10327–10335

[20] Dong X, Chen P, Huang H, Nowak M . A multi-restart iterated local search algorithm for the permutation flow shop problem minimizing total flow time. Computers & Operations Research, 2013, 40( 2): 627–632

[21] Simonis H. Sudoku as a constraint problem. In: Proceedings of the 4th Workshop on Modeling & Reformulating Constraint Satisfaction Problems. 2005, 13–27

[22] Rivin I, Vardi I, Zimmermann P . The n-queens problem. The American Mathematical Monthly, 1994, 101( 7): 629–639

[23] Crawford K D. Solving the n-queens problem using genetic algorithms. In: Proceedings of 1992 ACM/SIGAPP Symposium on Applied Computing: Technological Challenges of the 1990’s. 1992, 1039–1047

[24] Morris R, Starr D . The structure of all-interval series. Journal of Music Theory, 1974, 18( 2): 364–389

[25] Nguyen V H, Son M T. Solving the all-interval series problem: SAT vs CP. In: Proceedings of the 5th Symposium on Information and Communication Technology. 2014, 65–74

[26] Colbourn C J, Dinitz J H . Mutually orthogonal Latin squares: a brief survey of constructions. Journal of Statistical Planning and Inference, 2001, 95( 1−2): 9–48

[27] Appa G, Magos D, Mourtos I . Searching for mutually orthogonal Latin squares via integer and constraint programming. European Journal of Operational Research, 2006, 173( 2): 519–530

[28] Ma F, Zhang J . Finding orthogonal Latin squares using finite model searching tools. Science China Information Sciences, 2013, 56( 3): 1–9

[29] Mantere T, Koljonen J. Solving and analyzing Sudokus with cultural algorithms. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC). 2008, 4053–4060

[30] Lewis R . Metaheuristics can solve Sudoku puzzles. Journal of Heuristics, 2007, 13( 4): 387–401

[31] Musliu N, Winter F . A hybrid approach for the Sudoku problem: using constraint programming in iterated local search. IEEE Intelligent Systems, 2017, 32( 2): 52–62

[32] Benoist T, Estellon B, Gardi F, Megel R, Nouioua K . LocalSolver 1. x: a black-box local-search solver for 0-1 programming. 4OR, 2011, 9( 3): 299–316

[33] Prud’homme C, Fages J G, Lorca X. Choco-solver. See Choco-solver.org/ website, 2019

[34] Biere A, Fazekas K, Fleury M, Heisinger M. CaDiCal, Kissat, Paracooba, Plingeling and Treengeling entering the SAT competition 2020. In: Proceedings of SAT Competition 2020-Solver and Benchmark Descriptions. 2020, 50–53

[35] Lloyd H, Amos M . Solving Sudoku with ant colony optimization. IEEE Transactions on Games, 2020, 12( 3): 302–311

[36] Dorne R, Hao J K. Tabu search for graph coloring, T-Colorings and set T-Colorings. In: Voß S, Martello S, Osman I H, Roucairol C, eds. Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization. Boston: Springer, 1999, 77–92

RIGHTS & PERMISSIONS

Higher Education Press