Search Results

Documents authored by Guns, Tias

Document
Tool Paper
DOI: 10.4230/LIPIcs.SAT.2026.42
Unified Programmatic Access to CO Benchmarks, to Connect Constraint Solving Communities (Tool Paper)

Authors: Thomas Sergeys, Ignace Bleukx, and Tias Guns

Published in: LIPIcs, Volume 377, 29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026)

Abstract
Many communities within Combinatorial Optimization (CO) maintain benchmark sets in heterogeneous formats, often tied to specific competitions and solver technologies. Whilst this diversity is of practical and historical importance, it also creates barriers to use and compare methods from different communities. Inspired by the more unified software ecosystem from the ML community, we propose a programmatic abstraction for CO benchmark sets. A unified programmatic interface for downloading, reading and converting datasets across formats. This includes solver-oriented benchmarks such as XCSP3, MIPLib, PB, MaxSATEval, SAT and application-oriented benchmarks such as Nurse rostering, PSPLib (RCSP), and JSPlib. To enable cross-formalism conversions, we provide loaders that bring these dataset instances into CPMpy, a modelling library for constraint programming. CPMpy provides a transformation stack; an extensive set of rewrite operations such as constraint decomposition, linearization, and Boolean encodings, that allow transforming between different constraint formalisms. Based on this, we implement file writers to multiple solver-oriented formats, including MiniZinc, LP file format (ILP), OPB, and DIMACS (W)CNF ((Max)SAT). We demonstrate that this unified abstraction facilitates cross-community access to benchmarks and systematic comparisons of solvers across paradigms.
Cite as

Thomas Sergeys, Ignace Bleukx, and Tias Guns. Unified Programmatic Access to CO Benchmarks, to Connect Constraint Solving Communities (Tool Paper). In 29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 377, pp. 42:1-42:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{sergeys_et_al:LIPIcs.SAT.2026.42,
  author =	{Sergeys, Thomas and Bleukx, Ignace and Guns, Tias},
  title =	{{Unified Programmatic Access to CO Benchmarks, to Connect Constraint Solving Communities}},
  booktitle =	{29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026)},
  pages =	{42:1--42:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-431-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{377},
  editor =	{Ignatiev, Alexey and Szeider, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2026.42},
  URN =		{urn:nbn:de:0030-drops-263485},
  doi =		{10.4230/LIPIcs.SAT.2026.42},
  annote =	{Keywords: CPMpy, datasets, benchmarking, constraint solving}
}
Artifact
Software
DOI: 10.4230/artifacts.26917
Table Constraints for Integer Programming

Authors: Hendrik Bierlee, Wout Piessens, Tias Guns, and Peter J. Stuckey

Abstract
Cite as

Hendrik Bierlee, Wout Piessens, Tias Guns, Peter J. Stuckey. Table Constraints for Integer Programming (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-26917,
   title = {{Table Constraints for Integer Programming}}, 
   author = {Bierlee, Hendrik and Piessens, Wout and Guns, Tias and Stuckey, Peter J.},
   note = {Software, https://wms.cs.kuleuven.be/chat-opt, https://www.fwo.be/, https://optima.org.au/, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:1b22a434c54cd6bb28794cf6c9771f6a002e07f0;origin=https://github.com/ML-KULeuven/table-constraints-for-integer-programming;visit=swh:1:snp:993c9810181126cd29c2384d17d88d3c58cbdc58;anchor=swh:1:rev:3a9a6ff8e84d1d4ea474c2da6cf466a6be923128}{\texttt{swh:1:dir:1b22a434c54cd6bb28794cf6c9771f6a002e07f0}} (visited on 2026-07-13)},
   url = {https://github.com/ML-KULeuven/table-constraints-for-integer-programming},
   doi = {10.4230/artifacts.26917},
}
Artifact
Software
DOI: 10.4230/artifacts.26899
ML-KULeuven/HMLV

Authors: Marco Foschini, Emilio Gamba, Lucas Kletzander, and Tias Guns

Abstract
Cite as

Marco Foschini, Emilio Gamba, Lucas Kletzander, Tias Guns. ML-KULeuven/HMLV (Software, Source Code & Data). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-26899,
   title = {{ML-KULeuven/HMLV}}, 
   author = {Foschini, Marco and Gamba, Emilio and Kletzander, Lucas and Guns, Tias},
   note = {Software (visited on 2026-07-13)},
   url = {https://github.com/ML-KULeuven/HMLV},
   doi = {10.4230/artifacts.26899},
}
Document
DOI: 10.4230/LIPIcs.CP.2026.6
Table Constraints for Integer Programming

Authors: Hendrik Bierlee, Wout Piessens, Tias Guns, and Peter J. Stuckey

Published in: LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)

Abstract
Global constraints are a central concept in Constraint Programming (CP), which allow modellers to compactly express complex relations, and which allow solvers to efficiently handle them. Table constraints have especially been well-studied as they can express arbitrary finite relations, and are extensively used in CP benchmarks. In this paper we study how to best deal with table constraints when using Integer Linear Programming (ILP) solvers. We study two paradigms: linear encodings, and a lazy cut generation approach. For the encoding we propose a novel MDD-based flow encoding. For the cut generation, in which lazy constraints are generated on-demand during branch-and-cut search, we investigate different ways of generating such integer and fractional cuts as well as how to strengthen them through shrinking and cut lifting. We experimentally compare the different approaches on CP competition instances with a wide variety of table constraints, showing clear benefits over the standard integer encoding.
Cite as

Hendrik Bierlee, Wout Piessens, Tias Guns, and Peter J. Stuckey. Table Constraints for Integer Programming. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bierlee_et_al:LIPIcs.CP.2026.6,
  author =	{Bierlee, Hendrik and Piessens, Wout and Guns, Tias and Stuckey, Peter J.},
  title =	{{Table Constraints for Integer Programming}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-432-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{379},
  editor =	{Beldiceanu, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.6},
  URN =		{urn:nbn:de:0030-drops-266397},
  doi =		{10.4230/LIPIcs.CP.2026.6},
  annote =	{Keywords: Table constraints, integer programming, cut generation, modelling}
}
Document
DOI: 10.4230/LIPIcs.CP.2026.25
From CP Modeling to Preference Elicitation in HMLV Assembly Problems

Authors: Marco Foschini, Emilio Gamba, Lucas Kletzander, and Tias Guns

Published in: LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)

Abstract
High Mix Low Volume (HMLV) assembly problems involve producing a variety of items in small quantities, each of which requires scheduling a sequence of actions performed by machines or human operators. For the production process, companies are increasingly adopting reconfigurable manufacturing systems (RMS) where they choose which machines to deploy. Importantly, the selection of machines can substantially influence overall production time. For this reason, we present a CP model for solving HMLV for RMS. However, solely minimizing makespan does not necessarily yield the most desirable solution from a managerial perspective. For example, it may heavily rely on human operators. Since determining preferred solutions is challenging, incorporating Decision Maker (DM) feedback becomes essential. Therefore, to support DMs in selecting solutions that better reflect their preferences, we adapt pairwise preference elicitation methods for this industrial multi-objective combinatorial problem, while also comparing with trade-off-based methods.
Cite as

Marco Foschini, Emilio Gamba, Lucas Kletzander, and Tias Guns. From CP Modeling to Preference Elicitation in HMLV Assembly Problems. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 25:1-25:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{foschini_et_al:LIPIcs.CP.2026.25,
  author =	{Foschini, Marco and Gamba, Emilio and Kletzander, Lucas and Guns, Tias},
  title =	{{From CP Modeling to Preference Elicitation in HMLV Assembly Problems}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{25:1--25:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-432-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{379},
  editor =	{Beldiceanu, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.25},
  URN =		{urn:nbn:de:0030-drops-266579},
  doi =		{10.4230/LIPIcs.CP.2026.25},
  annote =	{Keywords: Job Shop Scheduling Problem, Multi-objective, Preference Elicitation}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.CP.2026.62
Towards Step-Wise Explanations of Large Search Trees (Short Paper)

Authors: Ignace Bleukx, Peter J. Stuckey, and Tias Guns

Published in: LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)

Abstract
Modern constraint solvers solve combinatorial problems through search with branching, propagation, and nogood learning. Although effective, the resulting search trees are hard to interpret: many branches and low-level inferences obscure why a conclusion is reached. Step-wise explanations provide an inference-based alternative, but prior successes were mainly for puzzle-style problems that required little or no search when solved by a CP-solver. We investigate whether step-wise explanations can be extended to search-heavy combinatorial problems. We study explanation sequences with only user-level constraints, ideally just one per step, and construct them from solver proof logs through nested explanations of complex steps. Our results indicate that concise user-level explanations are often achievable, even when solving requires many search nodes, while also highlighting open challenges such as deep nesting in some instances and dependence on proof generation. This motivates future work on explanation-aware solving and richer explanation languages.
Cite as

Ignace Bleukx, Peter J. Stuckey, and Tias Guns. Towards Step-Wise Explanations of Large Search Trees (Short Paper). In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 62:1-62:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bleukx_et_al:LIPIcs.CP.2026.62,
  author =	{Bleukx, Ignace and Stuckey, Peter J. and Guns, Tias},
  title =	{{Towards Step-Wise Explanations of Large Search Trees}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{62:1--62:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-432-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{379},
  editor =	{Beldiceanu, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.62},
  URN =		{urn:nbn:de:0030-drops-266958},
  doi =		{10.4230/LIPIcs.CP.2026.62},
  annote =	{Keywords: Explanation, search, propagation, proof}
}
Document
DOI: 10.4230/LIPIcs.CP.2025.6
Modeling and Explaining an Industrial Workforce Allocation and Scheduling Problem

Authors: Ignace Bleukx, Ryma Boumazouza, Tias Guns, Nadine Laage, and Guillaume Poveda

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
We present an industrial case on workforce allocation and scheduling in the aircraft manufacturing industry, where available teams need to be assigned to logistical operations. This application presents several challenges such as the scale of the problem, the need for fair workload distribution, and the need for methods for mitigating unforeseen disruptions due to technical malfunctions or incompatible weather conditions. We compare different Constraint Programming (CP) models for the allocation and scheduling problems, with extra focus on modeling the workload balancing component. Additionally, we investigate different techniques for explaining infeasibility of a disrupted schedule, such as conflict computation using Minimal Unsatisfiable Subsets (MUSes) and feasibility restoration using Minimal Correction Subsets (MCSes) or constraint relaxations. Our experimental results show that by using appropriate modeling techniques, the problem can be solved in reasonable time, thereby producing fair schedules. Additionally, we show how invalidated schedules can be explained and restored efficiently to help human operators in solving disruptions to the schedule.
Cite as

Ignace Bleukx, Ryma Boumazouza, Tias Guns, Nadine Laage, and Guillaume Poveda. Modeling and Explaining an Industrial Workforce Allocation and Scheduling Problem. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 6:1-6:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bleukx_et_al:LIPIcs.CP.2025.6,
  author =	{Bleukx, Ignace and Boumazouza, Ryma and Guns, Tias and Laage, Nadine and Poveda, Guillaume},
  title =	{{Modeling and Explaining an Industrial Workforce Allocation and Scheduling Problem}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{6:1--6:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.6},
  URN =		{urn:nbn:de:0030-drops-238670},
  doi =		{10.4230/LIPIcs.CP.2025.6},
  annote =	{Keywords: modeling, scheduling, fairness, explanations, feasibility restoration}
}
Artifact
Dataset
DOI: 10.4230/artifacts.24089
ML-KULeuven/SAT25_PB_reductions_experiments

Authors: Orestis Lomis, Jo Devriendt, Hendrik Bierlee, and Tias Guns

Abstract
Cite as

Orestis Lomis, Jo Devriendt, Hendrik Bierlee, Tias Guns. ML-KULeuven/SAT25_PB_reductions_experiments (Dataset, Experimental Results). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-24089,
   title = {{ML-KULeuven/SAT25\underlinePB\underlinereductions\underlineexperiments}}, 
   author = {Lomis, Orestis and Devriendt, Jo and Bierlee, Hendrik and Guns, Tias},
   note = {Dataset, This research was partly funded by the European Research Council (ERC) under the EU Horizon 2020 research and innovation programme (Grant No 101002802, CHAT-Opt)., swhId: \href{https://archive.softwareheritage.org/swh:1:dir:650c2f9b37926504a59a11a6dbf319620b311dc3;origin=https://github.com/ML-KULeuven/SAT25_PB_reductions_experiments;visit=swh:1:snp:c9843bb9ce4bf323c83b69edd5820bdb654e19be;anchor=swh:1:rev:d5b602b4b96833a077bd379b2803314349cb8548}{\texttt{swh:1:dir:650c2f9b37926504a59a11a6dbf319620b311dc3}} (visited on 2025-08-07)},
   url = {https://github.com/ML-KULeuven/SAT25_PB_reductions_experiments},
   doi = {10.4230/artifacts.24089},
}
Document
DOI: 10.4230/LIPIcs.SAT.2025.21
Improving Reduction Techniques in Pseudo-Boolean Conflict Analysis

Authors: Orestis Lomis, Jo Devriendt, Hendrik Bierlee, and Tias Guns

Published in: LIPIcs, Volume 341, 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)

Abstract
Recent pseudo-Boolean (PB) solvers leverage the cutting planes proof system to perform SAT-style conflict analysis during search. This process learns implied PB constraints, which can prune later parts of the search tree and is crucial to a PB solver’s performance. A key step in PB conflict analysis is the reduction of a reason constraint, which caused a variable propagation that contributed to the conflict. While necessary, reduction generally makes the reason constraint less strong. Consequently, different approaches to reduction have been proposed, broadly categorised as division- or saturation-based, with the aim of preserving the strength of the reason constraint as much as possible. This paper proposes two novel techniques in each reduction category. We theoretically show how each technique yields reason constraints which are at least as strong as those obtained from existing reduction methods. We then evaluate the empirical effectiveness of the reduction techniques on hard knapsack instances and the most recent PB'24 competition benchmarks.
Cite as

Orestis Lomis, Jo Devriendt, Hendrik Bierlee, and Tias Guns. Improving Reduction Techniques in Pseudo-Boolean Conflict Analysis. In 28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 341, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lomis_et_al:LIPIcs.SAT.2025.21,
  author =	{Lomis, Orestis and Devriendt, Jo and Bierlee, Hendrik and Guns, Tias},
  title =	{{Improving Reduction Techniques in Pseudo-Boolean Conflict Analysis}},
  booktitle =	{28th International Conference on Theory and Applications of Satisfiability Testing (SAT 2025)},
  pages =	{21:1--21:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-381-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{341},
  editor =	{Berg, Jeremias and Nordstr\"{o}m, Jakob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2025.21},
  URN =		{urn:nbn:de:0030-drops-237551},
  doi =		{10.4230/LIPIcs.SAT.2025.21},
  annote =	{Keywords: Constraint Programming, Pseudo-Boolean Reasoning, Conflict Analysis}
}
Document
DOI: 10.4230/DagRep.14.10.76
Machine Learning Augmented Algorithms for Combinatorial Optimization Problems (Dagstuhl Seminar 24441)

Authors: Deepak Ajwani, Bistra Dilkina, Tias Guns, and Ulrich Carsten Meyer

Published in: Dagstuhl Reports, Volume 14, Issue 10 (2025)

Abstract
Combinatorial optimization problems are pervasive across critical domains, including business analytics, engineering, supply chain management, transportation, and bioinformatics. Many of these problems are NP-hard, posing significant challenges for even moderately sized instances. Moreover, even when polynomial-time algorithms exist, their practical implementation can be computationally expensive for real-world applications. This has driven decades of research across diverse fields, encompassing exact and approximation algorithms, parameterized algorithms, algorithm engineering, operations research, optimization solvers (such as mixed-integer linear programming and constraint programming solvers), and nature-inspired metaheuristics. Recently, there has been a surge in research exploring the synergistic integration of machine learning techniques with algorithmic insights and optimization solvers to enhance the scalability of solving combinatorial optimization problems. However, research efforts in this area are currently fragmented across several distinct communities, including those focused on "Learning to scale optimization solvers," "Algorithm Engineering," "Algorithms with predictions," and "Decision-focused learning." This seminar brought together researchers from these diverse communities, fostering a dialogue on effectively combining algorithm engineering techniques, optimization solvers, and machine learning to address these challenging problems. The seminar facilitated the development of a shared vocabulary, clarifying similarities and distinctions between concepts across different research areas. Furthermore, significant progress was made in identifying key research directions for the future advancement of this field. We anticipate that these outcomes will serve as a valuable roadmap for advancing this exciting research area.
Cite as

Deepak Ajwani, Bistra Dilkina, Tias Guns, and Ulrich Carsten Meyer. Machine Learning Augmented Algorithms for Combinatorial Optimization Problems (Dagstuhl Seminar 24441). In Dagstuhl Reports, Volume 14, Issue 10, pp. 76-100, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{ajwani_et_al:DagRep.14.10.76,
  author =	{Ajwani, Deepak and Dilkina, Bistra and Guns, Tias and Meyer, Ulrich Carsten},
  title =	{{Machine Learning Augmented Algorithms for Combinatorial Optimization Problems (Dagstuhl Seminar 24441)}},
  pages =	{76--100},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2025},
  volume =	{14},
  number =	{10},
  editor =	{Ajwani, Deepak and Dilkina, Bistra and Guns, Tias and Meyer, Ulrich Carsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.14.10.76},
  URN =		{urn:nbn:de:0030-drops-230216},
  doi =		{10.4230/DagRep.14.10.76},
  annote =	{Keywords: Algorithm Engineering, Combinatorial Optimization, Constraint Solvers, Machine Learning}
}
Artifact
Software
DOI: 10.4230/artifacts.22502
CP-LLMs-ICL

Authors: Kostis Michailidis, Dimos Tsouros, and Tias Guns

Abstract
Cite as

Kostis Michailidis, Dimos Tsouros, Tias Guns. CP-LLMs-ICL (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-22502,
   title = {{CP-LLMs-ICL}}, 
   author = {Michailidis, Kostis and Tsouros, Dimos and Guns, Tias},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:5e4383ad6c4329796c9f21c51bbff4882dca8271}{\texttt{swh:1:dir:5e4383ad6c4329796c9f21c51bbff4882dca8271}} (visited on 2024-11-28)},
   url = {https://github.com/kostis-init/CP-LLMs-ICL},
   doi = {10.4230/artifacts.22502},
}
Document
DOI: 10.4230/LIPIcs.CP.2024.20
Constraint Modelling with LLMs Using In-Context Learning

Authors: Kostis Michailidis, Dimos Tsouros, and Tias Guns

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
Constraint Programming (CP) allows for the modelling and solving of a wide range of combinatorial problems. However, modelling such problems using constraints over decision variables still requires significant expertise, both in conceptual thinking and syntactic use of modelling languages. In this work, we explore the potential of using pre-trained Large Language Models (LLMs) as coding assistants, to transform textual problem descriptions into concrete and executable CP specifications. We present different transformation pipelines with explicit intermediate representations, and we investigate the potential benefit of various retrieval-augmented example selection strategies for in-context learning. We evaluate our approach on 2 datasets from the literature, namely NL4Opt (optimisation) and Logic Grid Puzzles (satisfaction), and a heterogeneous set of exercises from a CP course. The results show that pre-trained LLMs have promising potential for initialising the modelling process, with retrieval-augmented in-context learning significantly enhancing their modelling capabilities.
Cite as

Kostis Michailidis, Dimos Tsouros, and Tias Guns. Constraint Modelling with LLMs Using In-Context Learning. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 20:1-20:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{michailidis_et_al:LIPIcs.CP.2024.20,
  author =	{Michailidis, Kostis and Tsouros, Dimos and Guns, Tias},
  title =	{{Constraint Modelling with LLMs Using In-Context Learning}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{20:1--20:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.20},
  URN =		{urn:nbn:de:0030-drops-207053},
  doi =		{10.4230/LIPIcs.CP.2024.20},
  annote =	{Keywords: Constraint Modelling, Constraint Acquisition, Constraint Programming, Large Language Models, In-Context Learning, Natural Language Processing, Named Entity Recognition, Retrieval-Augmented Generation, Optimisation}
}
Document
DOI: 10.4230/LIPIcs.CP.2024.29
Mutational Fuzz Testing for Constraint Modeling Systems

Authors: Wout Vanroose, Ignace Bleukx, Jo Devriendt, Dimos Tsouros, Hélène Verhaeghe, and Tias Guns

Published in: LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024)

Abstract
Constraint programming (CP) modeling languages, like MiniZinc, Essence and CPMpy, play a crucial role in making CP technology accessible to non-experts. Both solver-independent modeling frameworks and solvers themselves are complex pieces of software that can contain bugs, which undermines their usefulness. Mutational fuzz testing is a way to test complex systems by stochastically mutating input and verifying preserved properties of the mutated output. We investigate different mutations and verification methods that can be used on the constraint specifications directly. This includes methods proposed in the context of SMT problem specifications, as well as new methods related to global constraints, optimization, and solution counting/preservation. Our results show that such a fuzz testing approach improves the overall code coverage of a modeling system compared to only unit testing, and is able to find bugs in the whole toolchain, from the modeling language transformations themselves to the underlying solvers.
Cite as

Wout Vanroose, Ignace Bleukx, Jo Devriendt, Dimos Tsouros, Hélène Verhaeghe, and Tias Guns. Mutational Fuzz Testing for Constraint Modeling Systems. In 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 307, pp. 29:1-29:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{vanroose_et_al:LIPIcs.CP.2024.29,
  author =	{Vanroose, Wout and Bleukx, Ignace and Devriendt, Jo and Tsouros, Dimos and Verhaeghe, H\'{e}l\`{e}ne and Guns, Tias},
  title =	{{Mutational Fuzz Testing for Constraint Modeling Systems}},
  booktitle =	{30th International Conference on Principles and Practice of Constraint Programming (CP 2024)},
  pages =	{29:1--29:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-336-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{307},
  editor =	{Shaw, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.29},
  URN =		{urn:nbn:de:0030-drops-207149},
  doi =		{10.4230/LIPIcs.CP.2024.29},
  annote =	{Keywords: fuzz testing, Constraint modeling language, bugs, mutational testing, modeling, constraint reformulation}
}
Document
DOI: 10.4230/LIPIcs.CP.2023.11
Simplifying Step-Wise Explanation Sequences

Authors: Ignace Bleukx, Jo Devriendt, Emilio Gamba, Bart Bogaerts, and Tias Guns

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract
Explaining constraint programs is useful for debugging an unsatisfiable program, to understand why a given solution is optimal, or to understand how to find a unique solution. A recently proposed framework for explaining constraint programs works well to explain the unique solution to a problem step by step. It can also be used to step-wise explain why a model is unsatisfiable, but this may create redundant steps and introduce superfluous information into the explanation sequence. This paper proposes methods to simplify a (step-wise) explanation sequence, to generate simple steps that together form a short, interpretable sequence. We propose an algorithm to greedily construct an initial sequence and two filtering algorithms that eliminate redundant steps and unnecessarily complex parts of explanation sequences. Experiments on diverse benchmark instances show that our techniques can significantly simplify step-wise explanation sequences.
Cite as

Ignace Bleukx, Jo Devriendt, Emilio Gamba, Bart Bogaerts, and Tias Guns. Simplifying Step-Wise Explanation Sequences. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bleukx_et_al:LIPIcs.CP.2023.11,
  author =	{Bleukx, Ignace and Devriendt, Jo and Gamba, Emilio and Bogaerts, Bart and Guns, Tias},
  title =	{{Simplifying Step-Wise Explanation Sequences}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{11:1--11:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.11},
  URN =		{urn:nbn:de:0030-drops-190489},
  doi =		{10.4230/LIPIcs.CP.2023.11},
  annote =	{Keywords: explanation, deduction, constraint programming, propagation}
}
Document
DOI: 10.4230/LIPIcs.CP.2023.36
Guided Bottom-Up Interactive Constraint Acquisition

Authors: Dimosthenis C. Tsouros, Senne Berden, and Tias Guns

Published in: LIPIcs, Volume 280, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023)

Abstract
Constraint Acquisition (CA) systems can be used to assist in the modeling of constraint satisfaction problems. In (inter)active CA, the system is given a set of candidate constraints and posts queries to the user with the goal of finding the right constraints among the candidates. Current interactive CA algorithms suffer from at least two major bottlenecks. First, in order to converge, they require a large number of queries to be asked to the user. Second, they cannot handle large sets of candidate constraints, since these lead to large waiting times for the user. For this reason, the user must have fairly precise knowledge about what constraints the system should consider. In this paper, we alleviate these bottlenecks by presenting two novel methods that improve the efficiency of CA. First, we introduce a bottom-up approach named GrowAcq that reduces the maximum waiting time for the user and allows the system to handle much larger sets of candidate constraints. It also reduces the total number of queries for problems in which the target constraint network is not sparse. Second, we propose a probability-based method to guide query generation and show that it can significantly reduce the number of queries required to converge. We also propose a new technique that allows the use of openly accessible CP solvers in query generation, removing the dependency of existing methods on less well-maintained custom solvers that are not publicly available. Experimental results show that our proposed methods outperform state-of-the-art CA methods, reducing the number of queries by up to 60%. Our methods work well even in cases where the set of candidate constraints is 50 times larger than the ones commonly used in the literature.
Cite as

Dimosthenis C. Tsouros, Senne Berden, and Tias Guns. Guided Bottom-Up Interactive Constraint Acquisition. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{tsouros_et_al:LIPIcs.CP.2023.36,
  author =	{Tsouros, Dimosthenis C. and Berden, Senne and Guns, Tias},
  title =	{{Guided Bottom-Up Interactive Constraint Acquisition}},
  booktitle =	{29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-300-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{280},
  editor =	{Yap, Roland H. C.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.36},
  URN =		{urn:nbn:de:0030-drops-190734},
  doi =		{10.4230/LIPIcs.CP.2023.36},
  annote =	{Keywords: Constraint acquisition, Constraint learning, Active learning, Modelling}
}
Document
DOI: 10.4230/LIPIcs.CP.2022.8
Learning MAX-SAT Models from Examples Using Genetic Algorithms and Knowledge Compilation

Authors: Senne Berden, Mohit Kumar, Samuel Kolb, and Tias Guns

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract
Many real-world problems can be effectively solved by means of combinatorial optimization. However, appropriate models to give to a solver are not always available, and sometimes must be learned from historical data. Although some research has been done in this area, the task of learning (weighted partial) MAX-SAT models has not received much attention thus far, even though such models can be used in many real-world applications. Furthermore, most existing work is limited to learning models from non-contextual data, where instances are labeled as solutions and non-solutions, but without any specification of the contexts in which those labels apply. A recent approach named hassle-sls has addressed these limitations: it can jointly learn hard constraints and weighted soft constraints from labeled contextual examples. However, it is hindered by long runtimes, as evaluating even a single candidate MAX-SAT model requires solving as many models as there are contexts in the training data, which quickly becomes highly expensive when the size of the model increases. In this work, we address these runtime issues. To this end, we make two contributions. First, we propose a faster model evaluation procedure that makes use of knowledge compilation. Second, we propose a genetic algorithm named hassle-gen that decreases the number of evaluations needed to find good models. We experimentally show that both contributions improve on the state of the art by speeding up learning, which in turn allows higher-quality MAX-SAT models to be found within a given learning time budget.
Cite as

Senne Berden, Mohit Kumar, Samuel Kolb, and Tias Guns. Learning MAX-SAT Models from Examples Using Genetic Algorithms and Knowledge Compilation. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{berden_et_al:LIPIcs.CP.2022.8,
  author =	{Berden, Senne and Kumar, Mohit and Kolb, Samuel and Guns, Tias},
  title =	{{Learning MAX-SAT Models from Examples Using Genetic Algorithms and Knowledge Compilation}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.8},
  URN =		{urn:nbn:de:0030-drops-166373},
  doi =		{10.4230/LIPIcs.CP.2022.8},
  annote =	{Keywords: Machine learning, constraint learning, MAX-SAT}
}
Document
DOI: 10.4230/LIPIcs.CP.2022.29
Learning Constraint Programming Models from Data Using Generate-And-Aggregate

Authors: Mohit Kumar, Samuel Kolb, and Tias Guns

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

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

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)

Copy BibTex To Clipboard

@InProceedings{kumar_et_al:LIPIcs.CP.2022.29,
  author =	{Kumar, Mohit and Kolb, Samuel and Guns, Tias},
  title =	{{Learning Constraint Programming Models from Data Using Generate-And-Aggregate}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.29},
  URN =		{urn:nbn:de:0030-drops-166580},
  doi =		{10.4230/LIPIcs.CP.2022.29},
  annote =	{Keywords: Constraint Learning, Constraint Programming, Model Synthesis}
}
Document
DOI: 10.4230/LIPIcs.CP.2021.42
Data Driven VRP: A Neural Network Model to Learn Hidden Preferences for VRP

Authors: Jayanta Mandi, Rocsildes Canoy, Víctor Bucarey, and Tias Guns

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract
The traditional Capacitated Vehicle Routing Problem (CVRP) minimizes the total distance of the routes under the capacity constraints of the vehicles. But more often, the objective involves multiple criteria including not only the total distance of the tour but also other factors such as travel costs, travel time, and fuel consumption. Moreover, in reality, there are numerous implicit preferences ingrained in the minds of the route planners and the drivers. Drivers, for instance, have familiarity with certain neighborhoods and knowledge of the state of roads, and often consider the best places for rest and lunch breaks. This knowledge is difficult to formulate and balance when operational routing decisions have to be made. This motivates us to learn the implicit preferences from past solutions and to incorporate these learned preferences in the optimization process. These preferences are in the form of arc probabilities, i.e., the more preferred a route is, the higher is the joint probability. The novelty of this work is the use of a neural network model to estimate the arc probabilities, which allows for additional features and automatic parameter estimation. This first requires identifying suitable features, neural architectures and loss functions, taking into account that there is typically few data available. We investigate the difference with a prior weighted Markov counting approach, and study the applicability of neural networks in this setting.
Cite as

Jayanta Mandi, Rocsildes Canoy, Víctor Bucarey, and Tias Guns. Data Driven VRP: A Neural Network Model to Learn Hidden Preferences for VRP. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{mandi_et_al:LIPIcs.CP.2021.42,
  author =	{Mandi, Jayanta and Canoy, Rocsildes and Bucarey, V{\'\i}ctor and Guns, Tias},
  title =	{{Data Driven VRP: A Neural Network Model to Learn Hidden Preferences for VRP}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{42:1--42:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.42},
  URN =		{urn:nbn:de:0030-drops-153339},
  doi =		{10.4230/LIPIcs.CP.2021.42},
  annote =	{Keywords: Vehicle routing, Neural network, Preference learning}
}
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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact