Abstract
Solvers for constraint optimisation problems exploit variable and value ordering heuristics. Numerous expert-designed heuristics exist, while recent research learns novel, customised heuristics from past problem instances. This article addresses unseen problems for which no historical data is available. We propose one-shot learning of customised, problem instance-specific heuristics. To do so, we introduce the concept of deep heuristics, a data-driven approach to learn extended versions of a given variable ordering heuristic online. First, for a problem instance, an initial online probing phase collects data, from which a deep heuristic function is learned. The learned heuristics can look ahead arbitrarily-many levels in the search tree instead of a ‘shallow’ localised lookahead of classical heuristics. A restart-based search strategy allows for multiple learned models to be acquired and exploited in the solver’s optimisation. We demonstrate deep variable ordering heuristics based on the smallest, anti first-fail, and maximum regret heuristics. Results on instances from the MiniZinc benchmark suite show that deep heuristics solve 20% more problem instances while improving on overall runtime for the Open Stacks and Evilshop benchmark problems.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Gent, I.P., MacIntyre, E., Prosser, P., Smith, B.M., Walsh, T.: An empirical study of dynamic variable ordering heuristics for the constraint satisfaction problem. In: Proceedings of 2nd International Conference on Principles and Practice of Constraint Programming (CP’96), pp. 179–193 (1996)
Haralick, R.M., Elliott, G.L.: Increasing tree search efficiency for constraint satisfaction problems. Artif. Intell. 14(3), 263–313 (1980)
Boussemart, F., Hemery, F., Lecoutre, C., Sais, L.: Boosting systematic search by weighting constraints. In: Proceedings of 16th European Conference on Artificial Intelligence (ECAI’04), pp. 146–150 (2004)
Refalo, P.: Impact-based search strategies for constraint programming. In: Proceedings of 10th International Conference on the Principles and Practice of Constraint Programming (CP’04), pp. 557–571 (2004)
Alanazi, F., Lehre, P.K.: Limits to learning in reinforcement learning hyper-heuristics. In: Proceedings of 16th European Conference on Evolutionary Computation in Combinatorial Optimization (EvoCOP’16), pp. 170–185 (2016)
Xia, W., Yap, R.H.C.: Learning robust search strategies using a bandit-based approach. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI’18), pp. 6657–6665 (2018)
Khalil, E.B., Dilkina, B., Nemhauser, G.L., Ahmed, S., Shao, Y.: Learning to run heuristics in tree search. In: Proceedings of 26th International Joint Conference on Artificial Intelligence (IJCAI’17), pp. 659–666 (2017)
Cappart, Q., Moisan, T., Rousseau, L., Prémont-Schwarz, I., Ciré, A.A.: Combining reinforcement learning and constraint programming for combinatorial optimization. CoRR arXiv:abs/2006.01610 (2020)
Schulte, C., Tack, G., Lagerkvist, M.Z.: Modeling and Programming with Gecode 6.2.0. www.gecode.org (2019)
Chu, G., Stuckey, P.J.: Learning value heuristics for constraint programming. In: Proceedings of 12th International Conference on the Integration of AI and OR Techniques in Constraint Programming (CPAIOR’15), pp. 108–123 (2015)
Rossi, F., van Beek, P., Walsh, T. (eds.): Handbook of Constraint Programming. Foundations of Artificial Intelligence, vol. 2. Elsevier, Amsterdam (2006)
Ortiz-Bayliss, J.C., Amaya, I., Conant-Pablos, S.E., Terashima-Marín, H.: Exploring the impact of early decisions in variable ordering for constraint satisfaction problems. Computational Intelligence and Neuroscience 2018, 6103726–1610372614 (2018)
The MiniZinc Benchmark Suite. MiniZinc: https://github.com/MiniZinc/minizinc-benchmarks (2016)
Blazewicz, J., Lenstra, J.K., Kan, A.H.G.R.: Scheduling subject to resource constraints: classification and complexity. Discret. Appl. Math. 5(1), 11–24 (1983). https://doi.org/10.1016/0166-218X(83)90012-4
Hartmann, S., Briskorn, D.: A survey of variants and extensions of the resource-constrained project scheduling problem. Eur. J. Oper. Res. 207 (1), 1–14 (2010). https://doi.org/10.1016/j.ejor.2009.11.005
Chu, G., Stuckey, P.J.: Minimizing the maximum number of open stacks by customer search. In: Proceedings of the 15th International Conference on the Principles and Practice of Constraint Programming (CP’09), Springer, pp. 242–257. (2009).https://doi.org/10.1007/978-3-642-04244-7∖_21
Bello, I., Pham, H., Le, Q.V., Norouzi, M., Bengio, S.: Neural combinatorial optimization with reinforcement learning. coRR (2016)
Chalumeau, F., Coulon, I., Cappart, Q., Rousseau, L.: Seapearl: A constraint programming solver guided by reinforcement learning. CoRR arXiv:abs/2102.09193 (2021)
Deudon, M., Cournut, P., Lacoste, A., Adulyasak, Y., Rousseau, L.: Learning heuristics for the TSP by policy gradient. In: Proceedings of the 15th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR’18), pp. 170–181 (2018)
Kool, W., van Hoof, H., Welling, M.: Attention, learn to solve routing problems!. CoRR arXiv:abs/1803.08475 (2018)
Hottung, A., Tanaka, S., Tierney, K.: Deep learning assisted heuristic tree search for the container pre-marshalling problem. CoRR arXiv:abs/1709.09972 (2017)
Song, W., Cao, Z., Zhang, J., Xu, C., Lim, A.: Learning variable ordering heuristics for solving constraint satisfaction problems. Eng. Appl. Artif. Intel. 109, 104603 (2022). https://doi.org/10.1016/j.engappai.2021.104603
Mandi, J., Demirovic, E., Stuckey, P.J., Guns, T.: Smart predict-and-optimize for hard combinatorial optimization problems. In: Proceedings of 34th AAAI Conference on Artificial Intelligence (AAAI’20), pp. 1603–1610 (2020)
Anderson, D., Hendel, G., Bodic, P.L., Viernickel, M.: Clairvoyant restarts in branch-and-bound search using online tree-size estimation. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI’19), pp. 1427–1434. (2019). https://doi.org/10.1609/aaai.v33i01.33011427
Petrovic, S., Epstein, S.L.: Tailoring a mixture of search heuristics. Constraint Programming Letters 4, 15–38 (2009)
Wallace, R.J.: Determining the principles underlying performance variation in CSP heuristics. International Journal of Artificial Intelligence Tools 17(5), 857–880 (2008)
Frost, D., Dechter, R.: Look-ahead value ordering for constraint satisfaction problems. In: Proceedings of 14th International Joint Conference on Artificial Intelligence (IJCAI’95), pp. 572–578 (1995)
Glankwamdee, W., Linderoth, J.: Lookahead Branching for Mixed Integer Programming. Technical Report, Lehigh University. Department of Industrial and Systems Engineering (2006)
Cox, J.L., Lucci, S., Pay, T.: Effects of dynamic variable–value ordering heuristics on the search space of sudoku modeled as a constraint satisfaction problem. Intel. Artif. 22(63), 1–15 (2019)
Acknowledgments
The authors thank the anonymous reviewers for their suggestions. We thank the late C. Schulte, and G. Tack, for assistance with Gecode and MiniZinc. Thanks to the participants of the IJCAI’21 DSO workshop, the CP’21 PTHG workshop and BNAIC’21, where earlier versions of this work were presented. Thanks to E. Freuder and H. Simonis for their suggestions. This research was partially supported by TAILOR, a project funded by EU Horizon 2020 research and innovation programme under grant number 952215.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Competing interests
None
Additional information
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Doolaard, F., Yorke-Smith, N. Online learning of variable ordering heuristics for constraint optimisation problems. Ann Math Artif Intell (2022). https://doi.org/10.1007/s10472-022-09816-z
Accepted:
Published:
DOI: https://doi.org/10.1007/s10472-022-09816-z