Document Open Access Logo

Learning Constraint Programming Models from Data Using Generate-And-Aggregate

Authors Mohit Kumar, Samuel Kolb, Tias Guns

PDF

File

Thumbnail PDF
PDF
LIPIcs.CP.2022.29.pdf
  • Filesize: 0.67 MB
  • 16 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Applied computing → Operations research
Keywords
  • Constraint Learning
  • Constraint Programming
  • Model Synthesis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Constraint programming (CP) is used widely for solving real-world problems. However, designing these models require substantial expertise. In this paper, we tackle this problem by synthesizing models automatically from past solutions. We introduce COUNT-CP, which uses simple grammars and a generate-and-aggregate approach to learn expressive first-order constraints typically used in CP as well as their parameters from data. The learned constraints generalize across instances over different sizes and can be used to solve unseen instances - e.g., learning constraints from a 4×4 Sudoku to solve a 9×9 Sudoku or learning nurse staffing requirements across hospitals. COUNT-CP is implemented using the CPMpy constraint programming and modelling environment to produce constraints with nested mathematical expressions. The method is empirically evaluated on a set of suitable benchmark problems and shows to learn accurate and compact models quickly.

Cite As Get BibTex

Mohit Kumar, Samuel Kolb, and Tias Guns. Learning Constraint Programming Models from Data Using Generate-And-Aggregate. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CP.2022.29

Author Details

Mohit Kumar
  • KU Leuven, Belgium
Samuel Kolb
  • KU Leuven, Belgium
Tias Guns
  • KU Leuven, Belgium

Funding

This project was partially funded by the Research Foundation - Flanders (FWO) project G0G3220N and FWO-S007318N, as well as the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant No. 101002802: CHAT-Opt, and 694980: SYNTH). Samuel Kolb is supported by the "Agentschap Innoveren & Ondernemen" (VLAIO) as part of the innovation mandate HBC.2021.0246.

Supplementary Materials

References

  1. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974. Google Scholar
  2. Nicolas Beldiceanu and Helmut Simonis. A Model Seeker: Extracting global constraint models from positive examples. In International Conference on Principles and Practice of Constraint Programming, 2012. Google Scholar
  3. Christian Bessiere, Remi Coletta, Abderrazak Daoudi, Nadjib Lazaar, Younes Mechqrane, and El-Houssine Bouyakhf. Boosting constraint acquisition via generalization queries. In ECAI, pages 99-104, 2014. Google Scholar
  4. Christian Bessiere, Remi Coletta, Eugene C. Freuder, and Barry O'Sullivan. Leveraging the learning power of examples in automated constraint acquisition. In Mark Wallace, editor, Principles and Practice of Constraint Programming - CP 2004, pages 123-137, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. Google Scholar
  5. Christian Bessiere, Remi Coletta, Frédéric Koriche, and Barry O'Sullivan. A sat-based version space algorithm for acquiring constraint satisfaction problems. In Machine Learning: ECML 2005, pages 23-34, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. Google Scholar
  6. Christian Bessiere, Remi Coletta, Barry O'Sullivan, and Mathias Paulin. Query-driven constraint acquisition. In Manuela M. Veloso, editor, IJCAI 2007, Proceedings of the 20th International Joint Conference on Artificial Intelligence, Hyderabad, India, January 6-12, 2007, pages 50-55, 2007. URL: http://ijcai.org/Proceedings/07/Papers/006.pdf.
  7. Abderrazak Daoudi, Nadjib Lazaar, Younes Mechqrane, Christian Bessiere, and El Houssine Bouyakhf. Detecting types of variables for generalization in constraint acquisition. In 2015 IEEE 27th International Conference on Tools with Artificial Intelligence (ICTAI), pages 413-420. IEEE, 2015. Google Scholar
  8. Luc De Raedt and Sašo Džeroski. First-order jk-clausal theories are PAC-learnable. Artificial Intelligence, 70(1-2):375-392, 1994. Google Scholar
  9. Tias Guns. Increasing modeling language convenience with a universal n-dimensional array, cppy as python-embedded example. In The 18th workshop on Constraint Modelling and Reformulation at CP, pages 1-8. ModRef, 2019. Google Scholar
  10. Samuel Kolb, Sergey Paramonov, Tias Guns, and Luc De Raedt. Learning constraints in spreadsheets and tabular data. Mach. Learn., 106(9-10):1441-1468, 2017. URL: https://doi.org/10.1007/s10994-017-5640-x.
  11. Mohit Kumar, Stefano Teso, Patrick De Causmaecker, and Luc De Raedt. Automating personnel rostering by learning constraints using tensors. In 2019 IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI), pages 697-704, 2019. URL: https://doi.org/10.1109/ICTAI.2019.00102.
  12. Arnaud Lallouet, Matthieu Lopez, Lionel Martin, and Christel Vrain. On learning constraint problems. In 22nd IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2010, Arras, France, 27-29 October 2010 - Volume 1, pages 45-52. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/ICTAI.2010.16.
  13. Fabio Massacci and Laura Marraro. Logical cryptanalysis as a sat problem. Journal of Automated Reasoning, 24(1):165-203, 2000. URL: https://doi.org/10.1023/A:1006326723002.
  14. Ralph Eric Mcgregor. Automated Theorem Proving Using Sat. PhD thesis, Clarkson University, USA, 2011. AAI3471671. Google Scholar
  15. Ilya Mironov and Lintao Zhang. Applications of sat solvers to cryptanalysis of hash functions. In Armin Biere and Carla P. Gomes, editors, Theory and Applications of Satisfiability Testing - SAT 2006, pages 102-115, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. Google Scholar
  16. Tomasz Pawlak. Synthesis of mathematical programming models with one-class evolutionary strategies. Swarm and Evolutionary Computation, 44, May 2018. URL: https://doi.org/10.1016/j.swevo.2018.04.007.
  17. Tomasz Pawlak and Krzysztof Krawiec. Automatic synthesis of constraints from examples using mixed integer linear programming. European Journal of Operational Research, 261, February 2017. URL: https://doi.org/10.1016/j.ejor.2017.02.034.
  18. Tomasz Pawlak and Krzysztof Krawiec. Automatic synthesis of constraints from examples using mixed integer linear programming. EJOR, 2017. Google Scholar
  19. Luc De Raedt, Andrea Passerini, and Stefano Teso. Learning constraints from examples. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence - AAAI 18, pages 7965-7970. AAAI Press, 2018. URL: https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/17229.
  20. Shubham Sharma, Rahul Gupta, Subhajit Roy, and Kuldeep S. Meel. Knowledge compilation meets uniform sampling. In Proceedings of International Conference on Logic for Programming Artificial Intelligence and Reasoning (LPAR), November 2018. Google Scholar
  21. L. G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134-1142, November 1984. URL: https://doi.org/10.1145/1968.1972.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact