Volume
LIPIcs, Volume 280
29th International Conference on Principles and Practice of Constraint Programming (CP 2023)
Event
CP 2023, August 27-31, 2023, Toronto, CanadaEditor
Publication Details
- published at: 2023-09-22
- Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- ISBN: 978-3-95977-300-3
- DBLP: db/conf/cp/cp2023
Access Numbers
- Detailed Access Statistics available here
-
Total Document Accesses (updated on a weekly basis):
0PDF Downloads
Documents
No documents found matching your filter selection.
Document
Complete Volume
LIPIcs, Volume 280, CP 2023, Complete Volume
Abstract
LIPIcs, Volume 280, CP 2023, Complete Volume
Cite as
29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 1-808, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@Proceedings{yap:LIPIcs.CP.2023,
title = {{LIPIcs, Volume 280, CP 2023, Complete Volume}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {1--808},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023},
URN = {urn:nbn:de:0030-drops-190365},
doi = {10.4230/LIPIcs.CP.2023},
annote = {Keywords: LIPIcs, Volume 280, CP 2023, Complete Volume}
}
Document
Front Matter
Front Matter, Table of Contents, Preface, Conference Organization
Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as
29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{yap:LIPIcs.CP.2023.0,
author = {Yap, Roland H. C.},
title = {{Front Matter, Table of Contents, Preface, Conference Organization}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {0:i--0:xx},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.0},
URN = {urn:nbn:de:0030-drops-190372},
doi = {10.4230/LIPIcs.CP.2023.0},
annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
Invited Talk
Beyond Optimal Solutions for Real-World Problems (Invited Talk)
Abstract
Combinatorial optimisation technology has come a long way. We now have mature high-level modelling languages in which to specify a model of the particular problem of interest [Nethercote et al., 2007; Frisch et al., 2008; Van Hentenryck, 1999; Fourer et al., 1990]; robust complete solvers in each major constraint paradigm, including Constraint Programming (CP), MaxSAT [Jessica Davies and Fahiem Bacchus, 2011; Alexey Ignatiev et al., 2019], and Mixed Integer Programming (MIP); effective incomplete search techniques that can easily be combined with complete solvers to speed up the search such as Large Neighbourhood Search [Paul Shaw, 1998]; and enough general knowledge about modelling techniques to understand the need for our models to incorporate components such as global constraints [Willem-Jan van Hoeve and Irit Katriel, 2006], symmetry constraints [Ian P. Gent et al., 2006], and more. All this has significantly reduced the amount of knowledge required to apply this technology successfully to the many different combinatorial optimisation problems that permeate our society.
And yet, not many organisations use such advanced optimisation technology; instead, they often rely on the solutions provided by problem-specific algorithms that are implemented in traditional imperative languages and lack any of the above advances. Further, while advanced optimisation technology is particularly suitable for the kind of complex human-in-the-loop decision-making problems that occur in critical sectors of our society, including health, transport, energy, disaster management, environment and finance, these decisions are often still made by people with little or no technological support. In this extended abstract I argue that to change this state of affairs, our research focus needs to change from improving the technology on its own, to improving it so that users can better trust, use, and maintain the optimisation systems that we develop with it. The rest of this extended abstract discusses my personal experiences and opinion on these three points.
Trust
I highlight trust (which focuses on the user’s point of view) rather than trustworthiness (which is a characteristic of the software itself) because I think it is the former rather than the latter that is at stake for the adoption of optimisation technology.
One of the biggest hurdles I have found for trust in the context of optimisation systems is for the domain experts to (feel like they) understand the underlying model. While many users will never do (or have to), I believe it is key for domain experts to have a high-level understanding of the constraints in the model, since their (dis)trust will likely spread through the organisation, impacting the adoption of the system. Thanks to the use of high-level modelling languages in CP, our group has achieved this [Matthias Klapperstueck et al., 2023] by documenting the constraints in a language the user knows (mathematics) and linking each constraint to the particular part of the model that implements it (via comments). While domain experts do not completely understand the model, the similarity between the format they understand (mathematics) and the model constraint has helped them verify our perception of their problem and improved their trust in the model. However, more needs to be done in this direction via the development of formal techniques. For example, our group is exploring the use of domain-specific languages [Hudak, 1997] as a bridge between domain experts and modellers that helps both trust and maintenance (see later). This [Sameela Suharshani Wijesundara et al., 2023] and other approaches need to be explored.
A very significant source of trust for our domain experts (and of trustworthiness for the software) has been the development of two different models implemented by two different people for the same problem [Matthias Klapperstueck et al., 2023]. While this can be seen as a prohibitively expensive exercise, it did not take that long once the first model was mature, is a good way to onboard new optimisation team members, and has helped up detect not only bugs but also differences in the interpretation of domain expert information. For optimisation problems where it is not possible to verify the optimality (or even correctness) of the solution, we see such redundant modelling as the only solution for now. Interestingly, a significant step forward in obtaining the trust of our domain experts has been the generation of an optimality gap whenever an optimal solution could not be found due to time constraints. While explaining this concept took time, once understood it has boosted their trust, particularly when tackling problems where the solution is not easy verifiable or when approximated models/data are used (needed for speed, see later). This makes it difficult to work with CP and SAT solvers, as they usually lack tight lower bounds. Finally, trust is often developed through the use of the system, which I discuss below.
Use
Usability is known to be key for the deployment of software systems. By "system" in our context, I refer to the combination of the problem model(s), the associated solver(s) and, importantly, the User Interface (UI) that often integrates them and is fundamental to their success. In addition to the traditional usability characteristics of software systems, I believe an optimisation system requires particular care in the following areas. Interaction, i.e., the system must allow users to interact with the UI not only to provide and modify the input data, but also to modify the constraints (at the very least by turning some on/off) as well as explore and compare solutions, as argued in [David Meignan et al., 2015; Jie Liu et al., 2021]. Incremental compilers and solvers would significantly help in making this easier, as well as generic ways for the UIs to communicate with them. Conflict resolution, that is, ensuring the system can not only detect infeasible instances, but also support users in understanding the data/constraints that cause infeasibility and how to modify the instance to make it feasible. Any interactive optimisation system that has users, will likely have conflicts. Thus, it is mandatory for CP to improve its conflict resolution technology which, while existent [João Marques-Silva and Alessandro Previti, 2014; Lauffer and Topcu, 2019; Ilankaikone Senthooran et al., 2023], is not widespread and it is often still problem-dependent, overwhelming (in the number of constraints shown to the user) and slow. Without it, users will be "stumped" when (rather than if) infeasibility is reached. Solution diversity, that is, supporting users in obtaining a diverse set of (close-to-optimal) solutions, where diversity is measured by a user-provided metric modelled somehow. While some solver-independent technology has been developed and implemented for this [Emmanuel Hebrard et al., 2005; Thierry Petit and Andrew C. Trapp, 2015; Linnea Ingmar et al., 2020], it should be easier to use and more widespread. Further, it requires sophisticated solution comparison capabilities and, importantly, for optimal solutions to be found in seconds rather than hours. This brings me to speed, an area where CP solvers are falling behind. Most of our research group applications now use MIP solvers due to the need for floats (which precludes us from using learning solvers such as Chuffed [Geoffrey Chu, 2013]), but also to the lack of effective warm-start processes that are available in MIP solvers. Interestingly, data and model approximations have been proved to achieve orders of magnitude speedups with small reductions in optimality [Matthias Klapperstueck et al., 2023]. Developing generic (i.e., problem independent) accurate approximations would be extremely useful for complex decision systems. Other areas where I think generic CP methods are worth investigating more include dealing with uncertainty and online problems, ensuring solution fairness (even if it is over time), and studying predict + optimise approaches.
Maintain
I know very few papers devoted to the issue of maintenance in optimisation technology. While this may be due to my lack of knowledge, I suspect it is also due to the limited adoption of optimisation technology. While the issues in this area are again common to other software systems, I believe the solutions for CP require special attention. For example, the issue of changes in user requirements (that our research group calls problem drift) seems particularly prevalent in decision-making systems, as such problems can evolve rapidly due to unforeseen circumstances. This can make optimisation systems obsolete faster than expected. Our research group has proposed to tackle problem drift by developing a requirements model implemented in the above-mentioned MDSLs and created by both domain experts and modellers that, when modified re-generates parts of the model to support the modifications [Sameela Suharshani Wijesundara et al., 2023]. This and other approaches such as the creation of reusable models components [Sophia Saller and Jana Koehler, 2022; Toby Walsh, 2003], or instantiatable classes for common problem domains, are worth investigating.
Cite as
Maria Garcia de la Banda. Beyond Optimal Solutions for Real-World Problems (Invited Talk). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 1:1-1:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{garciadelabanda:LIPIcs.CP.2023.1,
author = {Garcia de la Banda, Maria},
title = {{Beyond Optimal Solutions for Real-World Problems}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {1:1--1:4},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.1},
URN = {urn:nbn:de:0030-drops-190384},
doi = {10.4230/LIPIcs.CP.2023.1},
annote = {Keywords: Combinatorial optimisation systems, usability, trust, maintenance}
}
Document
Invited Talk
A Tale of Two Cities: Teaching CP with Story-Telling (Invited Talk)
Abstract
This presentation is all about story-telling. It tells the story, the pedagogical innovations and experience of the co-development of three MOOCs on the subject of "Modeling and Solving Discrete Optimization Problems” by The Chinese University of Hong Kong (CUHK) and the University of Melbourne, each with unique culture and tradition. The MOOCs feature the Fable-based Learning approach, which is a form of problem-based learning encapsulated in a story plot. Each MOOC video begins with an animation that follows a story adapted from a Chinese classic. The heroes of the story encounter various optimization problems requiring technical assistance from two professors from modern time via a magical tablet granted to the heroes by a genie old man. The animation thus sets the stage for lecturing modeling and solving techniques. The new pedagogy provides a movie-like immersive experience to the learners, and aims at increasing learners’ motivation and interests as well as situating them in a coherent learning context. In addition to scriptwriting, animation production and embedding the teaching materials in the story plot, another challenge of the project is the remote distance between the two institutions as well as the need to produce all teaching materials in both (Mandarin) Chinese and English to cater for different geographic learning needs. The project and production spanned across 2016 and 2017. The MOOCs have been running recurrently on Coursera since January, 2017. We present learner statistics and feedback, and discuss our experience and preliminary observations of adopting the online materials in a Flipped Classroom setting at CUHK.
Cite as
Jimmy H.M. Lee. A Tale of Two Cities: Teaching CP with Story-Telling (Invited Talk). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{lee:LIPIcs.CP.2023.2,
author = {Lee, Jimmy H.M.},
title = {{A Tale of Two Cities: Teaching CP with Story-Telling}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {2:1--2:1},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.2},
URN = {urn:nbn:de:0030-drops-190395},
doi = {10.4230/LIPIcs.CP.2023.2},
annote = {Keywords: Constraint Programming, MOOCs, Fable-based Learning}
}
Document
Invited Talk
The CP-SAT-LP Solver (Invited Talk)
Abstract
The CP-SAT-LP solver is developed by the Operations Research team at Google and is part of the OR-Tools [Laurent Perron and Vincent Furnon, 2023] open-source optimization suite. It is an implementation of a purely integral Constraint Programming solver on top of a SAT solver using Lazy Clause Generation [Stuckey, 2010]. It draws its inspiration from the chuffed solver [Geoffrey Chu et al., 2023], and from the CP 2013 plenary by Peter Stuckey on Lazy Clause Generation [Stuckey, 2013].
The CP-SAT-LP solver improves upon the chuffed solver [Geoffrey Chu et al., 2023] in two main directions. First, it uses a simplex alongside the SAT engine. Second, it implements and relies upon a portfolio of diverse workers for its search part.
The use of the simplex brings the obvious advantages of a linear relaxation on the linear part of the full model. It also started the integration of MIP technology into CP-SAT-LP. This is a huge endeavour, as MIP solvers are mature and complex. It includes presolve - which was already a part of CP-SAT -, dual reductions, specific branching rules, cuts, reduced cost fixing, and more advanced techniques. It also allows to integrate tightly the research from the Scheduling on MIP community [Balas, 1985; Applegate and Cook, 1991; Maurice Queyranne, 1993] along with the most advanced scheduling algorithms [Vilím, 2011]. This has enabled breakthroughs in solving and proving hard scheduling instances of the Job-Shop problems [Ding et al., 2019] and Resource Constraint Project Scheduling Problems [Rainer Kolisch and Arno Sprecher, 1997; Artigues et al., 2008].
Using a portfolio of different workers makes it easier to try new ideas and to incorporate orthogonal techniques with little complication, except controlling the explosion of potential workers. These workers can be categorized along multiple criteria like finding primal solutions - either using complete solvers, Local Search [Luteberget and Sartor, 2023] or Large Neighborhood Search [Paul Shaw, 1998] -, improving dual bounds, trying to reduce the problem with the help of continuous probing. This diversity of behaviors has increased the robustness of the solver, while the continuous sharing of information between workers has produced massive speedups when running multiple workers in parallel.
All in all, CP-SAT-LP is a state-of-the-art solver, with unsurpassed performance in the Constraint Programming community, breakthrough results on Scheduling benchmarks (with the closure of many open problems), and competitive results with the best MIP solvers (on purely integral problems).
Cite as
Laurent Perron, Frédéric Didier, and Steven Gay. The CP-SAT-LP Solver (Invited Talk). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 3:1-3:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{perron_et_al:LIPIcs.CP.2023.3,
author = {Perron, Laurent and Didier, Fr\'{e}d\'{e}ric and Gay, Steven},
title = {{The CP-SAT-LP Solver}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {3:1--3:2},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.3},
URN = {urn:nbn:de:0030-drops-190405},
doi = {10.4230/LIPIcs.CP.2023.3},
annote = {Keywords: Constraint Programming, Operations Research, Sat Solver}
}
Document
Invited Talk
Coupling CP with Deep Learning for Molecular Design and SARS-CoV2 Variants Exploration (Invited Talk)
Abstract
The use of discrete optimization, including Constraint Programming, for designing objects that we completely understand is quite usual. In this talk, I'll show how designing specific biomolecules (proteins) raises new challenges, requiring solving problems that combine precise design targets, approximate laws, and design rules that can be deep-learned from data.
Cite as
Thomas Schiex. Coupling CP with Deep Learning for Molecular Design and SARS-CoV2 Variants Exploration (Invited Talk). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 4:1-4:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{schiex:LIPIcs.CP.2023.4,
author = {Schiex, Thomas},
title = {{Coupling CP with Deep Learning for Molecular Design and SARS-CoV2 Variants Exploration}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {4:1--4:3},
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.4},
URN = {urn:nbn:de:0030-drops-190415},
doi = {10.4230/LIPIcs.CP.2023.4},
annote = {Keywords: graphical models, deep learning, constraint programming, cost function networks, random Markov fields, decision-focused learning, protein design}
}
Document
Invited Talk
CP Solver Design for Maximum CPU Utilization (Invited Talk)
Abstract
In this talk, I explain how to improve the performance of a solver without focusing on algorithms, search, propagation or parallelism. Performance is achieved instead with better CPU utilization, efficient code and more precise design of the solver itself.
In the words of Fedor G. Pikus [Pikus, 2021], the time of "performance taking care of itself" is over. In today’s hardware the number of cores is increasing while the CPU clock speed has reached a plateau. Main memory access is slow in comparison to the CPU. And despite multiple memory cache levels, the CPU can easily become idle waiting for data from the memory, slowing down the computation considerably. Unfortunately, those trends are probably not going to change in the near future.
For those reasons we are witnessing revived interest in efficient code and performance-centered software design, especially in areas where the performance is critical: computer games, compilers, internet browsers, language interpreters (e.g. JavaScript or Python), etc.
The good news is that many of the tricks used in the above-mentioned areas, can be used in constraint programming as well. The bad news is that the performance has to be taken into account from the very beginning of the design. It is not possible to add it easily later. Sometimes, better performance can be achieved only by radical shifts in the design such as from object-oriented to data-oriented programming.
The design of a CP solver is not an exception in this regard. Without the efficient core of the CP solver, it is not possible to write truly efficient propagation or search algorithms. On the other hand, all algorithms in the solver must take the design of the solver into account and leverage it.
In this talk, I will describe what I consider the most important aspects of the design of ScheduleOpt Optal solver. I will concentrate on the performance, but I will also mention other aspects such as ease of use, maintainability, and testing.
Cite as
Petr Vilím. CP Solver Design for Maximum CPU Utilization (Invited Talk). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, p. 5:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{vilim:LIPIcs.CP.2023.5,
author = {Vil{\'\i}m, Petr},
title = {{CP Solver Design for Maximum CPU Utilization}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {5:1--5:1},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.5},
URN = {urn:nbn:de:0030-drops-190425},
doi = {10.4230/LIPIcs.CP.2023.5},
annote = {Keywords: Constraint Programming, Software Design, Efficient Code}
}
Document
Optimization of Short-Term Underground Mine Planning Using Constraint Programming
Abstract
Short-term underground mine planning problems are often difficult to solve due to the large number of activities and diverse machine types to be scheduled, as well as multiple operational constraints. This paper presents a Constraint Programming (CP) model to optimize short-term scheduling for the Meliadine underground gold mine in Nunavut, Canada, taking into consideration operational constraints and the daily development and production targets of the mine plan. To evaluate the efficacy of the developed CP short-term planning model, we compare schedules generated by the CP model with the ones created manually by the mine planner for two real data sets. Results demonstrate that the CP model outperforms the manual approach by generating more efficient schedules with lower makespans.
Cite as
Younes Aalian, Gilles Pesant, and Michel Gamache. Optimization of Short-Term Underground Mine Planning Using Constraint Programming. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{aalian_et_al:LIPIcs.CP.2023.6,
author = {Aalian, Younes and Pesant, Gilles and Gamache, Michel},
title = {{Optimization of Short-Term Underground Mine Planning Using Constraint Programming}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {6:1--6:16},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.6},
URN = {urn:nbn:de:0030-drops-190430},
doi = {10.4230/LIPIcs.CP.2023.6},
annote = {Keywords: Mine planning, Constraint Programming, Short-term planning, Underground mine, Scheduling}
}
Document
Exploiting Configurations of MaxSAT Solvers
Abstract
In this paper, we describe how we can effectively exploit alternative parameter configurations to a MaxSAT solver. We describe how these configurations can be computed in the context of MaxSAT. In particular, we experimentally show how to easily combine configurations of a non-competitive solver to obtain a better solving approach.
Cite as
Josep Alòs, Carlos Ansótegui, Josep M. Salvia, and Eduard Torres. Exploiting Configurations of MaxSAT Solvers. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{alos_et_al:LIPIcs.CP.2023.7,
author = {Al\`{o}s, Josep and Ans\'{o}tegui, Carlos and Salvia, Josep M. and Torres, Eduard},
title = {{Exploiting Configurations of MaxSAT Solvers}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {7:1--7:16},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.7},
URN = {urn:nbn:de:0030-drops-190443},
doi = {10.4230/LIPIcs.CP.2023.7},
annote = {Keywords: maximum satisfiability, maxsat evaluation, automatic configuration}
}
Document
Symmetries for Cube-And-Conquer in Finite Model Finding
Abstract
The cube-and-conquer paradigm enables massive parallelization of SAT solvers, which has proven to be crucial in solving highly combinatorial problems. In this paper, we apply the paradigm in the context of finite model finding, where we show that isomorphic cubes can be discarded since they lead to isomorphic models. However, we are faced with the complication that a well-known technique, the Least Number Heuristic (LNH), already exists in finite model finders to effectively prune (some) isomorphic models from the search. Therefore, it needs to be shown that isomorphic cubes still can be discarded when the LNH is used. The presented ideas are incorporated into the finite model finder Mace4, where we demonstrate significant improvements in model enumeration.
Cite as
João Araújo, Choiwah Chow, and Mikoláš Janota. Symmetries for Cube-And-Conquer in Finite Model Finding. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{araujo_et_al:LIPIcs.CP.2023.8,
author = {Ara\'{u}jo, Jo\~{a}o and Chow, Choiwah and Janota, Mikol\'{a}\v{s}},
title = {{Symmetries for Cube-And-Conquer in Finite Model Finding}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {8:1--8:19},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.8},
URN = {urn:nbn:de:0030-drops-190455},
doi = {10.4230/LIPIcs.CP.2023.8},
annote = {Keywords: finite model enumeration, cube-and-conquer, symmetry-breaking, parallel algorithm, least number heuristic}
}
Document
Guiding Backtrack Search by Tracking Variables During Constraint Propagation
Abstract
It is well-known that variable ordering heuristics play a central role in solving efficiently Constraint Satisfaction Problem (CSP) instances. From the early 80’s, and during more than two decades, the dynamic variable ordering heuristic selecting the variable with the smallest domain was clearly prevailing. Then, from the mid 2000’s, some adaptive heuristics have been introduced: their principle is to collect some useful information during the search process in order to take better informed decisions. Among those adaptive heuristics, wdeg/dom (and its variants) remains particularly robust. In this paper, we introduce an original heuristic based on the midway processing of failing executions of constraint propagation: this heuristic called pick/dom tracks the variables that are directly involved in the process of constraint propagation, when ending with a conflict. The robustness of this new heuristic is demonstrated from a large experimentation conducted with the constraint solver ACE. Interestingly enough, one can observe some complementary between the early, midway and late forms of processing of conflicts.
Cite as
Gilles Audemard, Christophe Lecoutre, and Charles Prud'homme. Guiding Backtrack Search by Tracking Variables During Constraint Propagation. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{audemard_et_al:LIPIcs.CP.2023.9,
author = {Audemard, Gilles and Lecoutre, Christophe and Prud'homme, Charles},
title = {{Guiding Backtrack Search by Tracking Variables During Constraint Propagation}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {9:1--9:17},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.9},
URN = {urn:nbn:de:0030-drops-190461},
doi = {10.4230/LIPIcs.CP.2023.9},
annote = {Keywords: Variable Ordering Heuristics, Variable Weighting}
}
Document
Incremental Constrained Clustering by Minimal Weighted Modification
Abstract
Clustering is a well-known task in Data Mining that aims at grouping data instances according to their similarity. It is an exploratory and unsupervised task whose results depend on many parameters, often requiring the expert to iterate several times before satisfaction. Constrained clustering has been introduced for better modeling the expectations of the expert. Nevertheless constrained clustering is not yet sufficient since it usually requires the constraints to be given before the clustering process. In this paper we address a more general problem that aims at modeling the exploratory clustering process, through a sequence of clustering modifications where expert constraints are added on the fly. We present an incremental constrained clustering framework integrating active query strategies and a Constraint Programming model to fit the expert expectations while preserving the stability of the partition, so that the expert can understand the process and apprehend its impact. Our model supports instance and group-level constraints, which can be relaxed. Experiments on reference datasets and a case study related to the analysis of satellite image time series show the relevance of our framework.
Cite as
Aymeric Beauchamp, Thi-Bich-Hanh Dao, Samir Loudni, and Christel Vrain. Incremental Constrained Clustering by Minimal Weighted Modification. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{beauchamp_et_al:LIPIcs.CP.2023.10,
author = {Beauchamp, Aymeric and Dao, Thi-Bich-Hanh and Loudni, Samir and Vrain, Christel},
title = {{Incremental Constrained Clustering by Minimal Weighted Modification}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {10:1--10:22},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.10},
URN = {urn:nbn:de:0030-drops-190478},
doi = {10.4230/LIPIcs.CP.2023.10},
annote = {Keywords: Incremental constrained clustering, Constrained optimization problem, User feedback}
}
Document
Simplifying Step-Wise Explanation Sequences
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-dev.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
Towards More Efficient Local Search for Pseudo-Boolean Optimization
Abstract
Pseudo-Boolean (PB) constraints are highly expressive, and many combinatorial optimization problems can be modeled using pseudo-Boolean optimization (PBO). It is recognized that stochastic local search (SLS) is a powerful paradigm for solving combinatorial optimization problems, but the development of SLS for solving PBO is still in its infancy. In this paper, we develop an effective SLS algorithm for solving PBO, dubbed NuPBO, which introduces a novel scoring function for PB constraints and a new weighting scheme. We conduct experiments on a broad range of six public benchmarks, including three real-world benchmarks, a benchmark from PB competition, an integer linear programming optimization benchmark, and a crafted combinatorial benchmark, to compare NuPBO against five state-of-the-art competitors, including a recently-proposed SLS PBO solver LS-PBO, two complete PB solvers PBO-IHS and RoundingSat, and two mixed integer programming (MIP) solvers Gurobi and SCIP. NuPBO has been exhibited to perform best on these three real-world benchmarks. On the other three benchmarks, NuPBO shows competitive performance compared to state-of-the-art competitors, and it significantly outperforms LS-PBO, indicating that NuPBO greatly advances the state of the art in SLS for solving PBO.
Cite as
Yi Chu, Shaowei Cai, Chuan Luo, Zhendong Lei, and Cong Peng. Towards More Efficient Local Search for Pseudo-Boolean Optimization. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{chu_et_al:LIPIcs.CP.2023.12,
author = {Chu, Yi and Cai, Shaowei and Luo, Chuan and Lei, Zhendong and Peng, Cong},
title = {{Towards More Efficient Local Search for Pseudo-Boolean Optimization}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {12:1--12:18},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.12},
URN = {urn:nbn:de:0030-drops-190490},
doi = {10.4230/LIPIcs.CP.2023.12},
annote = {Keywords: Pseudo-Boolean Optimization, Stochastic Local Search, Scoring Function, Weighting Scheme}
}
Document
Boosting Decision Diagram-Based Branch-And-Bound by Pre-Solving with Aggregate Dynamic Programming
Abstract
Discrete optimization problems expressible as dynamic programs can be solved by branch-and-bound with decision diagrams. This approach dynamically compiles bounded-width decision diagrams to derive both lower and upper bounds on unexplored parts of the search space, until they are all enumerated or discarded. Assuming a minimization problem, relaxed decision diagrams provide lower bounds through state merging while restricted decision diagrams obtain upper bounds by excluding states to limit their size. As the selection of states to merge or delete is done locally, it is very myopic to the global problem structure. In this paper, we propose a novel way to proceed that is based on pre-solving a so-called aggregate version of the problem with a limited number of states. The compiled decision diagram of this aggregate problem is tractable and can fit in memory. It can then be exploited by the original branch-and-bound to generate additional pruning and guide the compilation of restricted decision diagrams toward good solutions. The results of the numerical study we conducted on three combinatorial optimization problems show a clear improvement in the performance of DD-based solvers when blended with the proposed techniques. These results also suggest an approach where the aggregate dynamic programming model could be used in replacement of the relaxed decision diagrams altogether.
Cite as
Vianney Coppé, Xavier Gillard, and Pierre Schaus. Boosting Decision Diagram-Based Branch-And-Bound by Pre-Solving with Aggregate Dynamic Programming. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{coppe_et_al:LIPIcs.CP.2023.13,
author = {Copp\'{e}, Vianney and Gillard, Xavier and Schaus, Pierre},
title = {{Boosting Decision Diagram-Based Branch-And-Bound by Pre-Solving with Aggregate Dynamic Programming}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {13:1--13:17},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.13},
URN = {urn:nbn:de:0030-drops-190500},
doi = {10.4230/LIPIcs.CP.2023.13},
annote = {Keywords: Discrete Optimization, Decision Diagrams, Aggregate Dynamic Programming}
}
Document
Fast Matrix Multiplication Without Tears: A Constraint Programming Approach
Abstract
It is known that the multiplication of an N × M matrix with an M × P matrix can be performed using fewer multiplications than what the naive NMP approach suggests. The most famous instance of this is Strassen’s algorithm for multiplying 2× 2 matrices in 7 instead of 8 multiplications. This gives rise to the constraint satisfaction problem of fast matrix multiplication, where a set of R < NMP multiplication terms must be chosen and combined such that they satisfy correctness constraints on the output matrix. Despite its highly combinatorial nature, this problem has not been exhaustively examined from that perspective, as evidenced for example by the recent deep reinforcement learning approach of AlphaTensor. In this work, we propose a simple yet novel Constraint Programming approach to find algorithms for fast matrix multiplication or provide proof of infeasibility otherwise. We propose a set of symmetry-breaking constraints and valid inequalities that are particularly helpful in proving infeasibility. On the feasible side, we find that exploiting solver performance variability in conjunction with a sparsity-based problem decomposition enables finding solutions for larger (feasible) instances of fast matrix multiplication. Our experimental results using CP Optimizer demonstrate that we can find fast matrix multiplication algorithms for matrices up to 3× 3 with R = 23 in a short amount of time.
Cite as
Arnaud Deza, Chang Liu, Pashootan Vaezipoor, and Elias B. Khalil. Fast Matrix Multiplication Without Tears: A Constraint Programming Approach. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{deza_et_al:LIPIcs.CP.2023.14,
author = {Deza, Arnaud and Liu, Chang and Vaezipoor, Pashootan and Khalil, Elias B.},
title = {{Fast Matrix Multiplication Without Tears: A Constraint Programming Approach}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {14:1--14:15},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.14},
URN = {urn:nbn:de:0030-drops-190518},
doi = {10.4230/LIPIcs.CP.2023.14},
annote = {Keywords: fast matrix multiplication, computer-assisted proofs, constraint programming, constraint satisfaction problem}
}
Document
Probabilistic Inference by Projected Weighted Model Counting on Horn Clauses
Abstract
Weighted model counting, that is, counting the weighted number of satisfying assignments of a propositional formula, is an important tool in probabilistic reasoning. Recently, the use of projected weighted model counting (PWMC) has been proposed as an approach to formulate and answer probabilistic queries. In this work, we propose a new simplified modeling language based on PWMC in which probabilistic inference tasks are modeled using a conjunction of Horn clauses and a particular weighting scheme for the variables. We show that the major problems of inference for Bayesian Networks, network reachability and probabilistic logic programming can be modeled in this language. Subsequently, we propose a new, relatively simple solver that is specifically optimized to solve the PWMC problem for such formulas. Our experiments show that our new solver is competitive with state-of-the-art solvers on the major problems studied.
Cite as
Alexandre Dubray, Pierre Schaus, and Siegfried Nijssen. Probabilistic Inference by Projected Weighted Model Counting on Horn Clauses. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{dubray_et_al:LIPIcs.CP.2023.15,
author = {Dubray, Alexandre and Schaus, Pierre and Nijssen, Siegfried},
title = {{Probabilistic Inference by Projected Weighted Model Counting on Horn Clauses}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {15:1--15:17},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.15},
URN = {urn:nbn:de:0030-drops-190520},
doi = {10.4230/LIPIcs.CP.2023.15},
annote = {Keywords: Model Counting, Bayesian Networks, Probabilistic Networks}
}
Document
A CP Approach for the Liner Shipping Network Design Problem
Abstract
The liner shipping network design problem consists, for a shipowner, in determining, on the one hand, which maritime lines (in the form of rotations serving a set of ports) to open, and, on the other hand, the assignment of ships (container ships) with the adapted sizes for the different lines to carry all the container flows. In this paper, we propose a modeling of this problem using constraint programming. Then, we present a preliminary study of its solving using a state-of-the-art solver, namely the OR-Tools CP-SAT solver.
Cite as
Yousra El Ghazi, Djamal Habet, and Cyril Terrioux. A CP Approach for the Liner Shipping Network Design Problem. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 16:1-16:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{elghazi_et_al:LIPIcs.CP.2023.16,
author = {El Ghazi, Yousra and Habet, Djamal and Terrioux, Cyril},
title = {{A CP Approach for the Liner Shipping Network Design Problem}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {16:1--16:21},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.16},
URN = {urn:nbn:de:0030-drops-190532},
doi = {10.4230/LIPIcs.CP.2023.16},
annote = {Keywords: Constraint optimization problem, modeling, solving, industrial application}
}
Document
Optimization Models for Pickup-And-Delivery Problems with Reconfigurable Capacities
Abstract
When a transportation service accommodates both people and goods, operators sometimes opt for vehicles that can be dynamically reconfigured for different demands. Motivated by air service in remote communities in Canada’s north, we define a pickup-and-delivery problem in which aircraft can add or remove seats during a multi-stop trip to accommodate varying demands. Given the demand for people and cargo as well as a seat inventory at each location, the problem consists in finding a tour that picks up and delivers all demand while potentially reconfiguring the vehicle capacity at each location by adding or removing seats. We develop a total of six models using three different approaches: constraint programming, mixed integer programming, and domain-independent dynamic programming. Our numerical experiments indicate that domain-independent dynamic programming is able to substantially outperform the other technologies on both solution quality and run-time on a set of randomly generated instances spanning the size of real problems in northern Canada.
Cite as
Arnoosh Golestanian, Giovanni Lo Bianco, Chengyu Tao, and J. Christopher Beck. Optimization Models for Pickup-And-Delivery Problems with Reconfigurable Capacities. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{golestanian_et_al:LIPIcs.CP.2023.17,
author = {Golestanian, Arnoosh and Bianco, Giovanni Lo and Tao, Chengyu and Beck, J. Christopher},
title = {{Optimization Models for Pickup-And-Delivery Problems with Reconfigurable Capacities}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {17:1--17:17},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.17},
URN = {urn:nbn:de:0030-drops-190542},
doi = {10.4230/LIPIcs.CP.2023.17},
annote = {Keywords: Pickup and delivery, Dial-a-ride problem, Optimization}
}
Document
Preprocessing in SAT-Based Multi-Objective Combinatorial Optimization
Abstract
Building on Boolean satisfiability (SAT) and maximum satisfiability (MaxSAT) solving algorithms, several approaches to computing Pareto-optimal MaxSAT solutions under multiple objectives have been recently proposed. However, preprocessing in (Max)SAT-based multi-objective optimization remains so-far unexplored. Generalizing clause redundancy to the multi-objective setting, we establish provably-correct liftings of MaxSAT preprocessing techniques for multi-objective MaxSAT in terms of computing Pareto-optimal solutions. We also establish preservation of Pareto-MCSes - the multi-objective lifting of minimal correction sets tightly connected to optimal MaxSAT solutions - as a distinguishing feature between different redundancy notions in the multi-objective setting. Furthermore, we provide a first empirical evaluation of the effect of preprocessing on instance sizes and multi-objective MaxSAT solvers.
Cite as
Christoph Jabs, Jeremias Berg, Hannes Ihalainen, and Matti Järvisalo. Preprocessing in SAT-Based Multi-Objective Combinatorial Optimization. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{jabs_et_al:LIPIcs.CP.2023.18,
author = {Jabs, Christoph and Berg, Jeremias and Ihalainen, Hannes and J\"{a}rvisalo, Matti},
title = {{Preprocessing in SAT-Based Multi-Objective Combinatorial Optimization}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {18:1--18: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.18},
URN = {urn:nbn:de:0030-drops-190553},
doi = {10.4230/LIPIcs.CP.2023.18},
annote = {Keywords: maximum satisfiability, multi-objective combinatorial optimization, preprocessing, redundancy}
}
Document
An Efficient Constraint Programming Approach to Preemptive Job Shop Scheduling
Abstract
Constraint Programming has been widely, and very successfully, applied to scheduling problems. However, the focus has been on uninterruptible tasks, and preemptive scheduling problems are typically harder for existing constraint solvers. Indeed, one usually needs to represent all potential task interruptions thus introducing many variables and symmetrical or dominated choices.
In this paper, building on mostly known results, we observe that a large class of preemptive disjunctive scheduling problems do not require an explicit model of task interruptions. We then introduce a new constraint programming approach for this class of problems that significantly outperforms state-of-the-art dedicated approaches in our experimental results.
Cite as
Carla Juvin, Emmanuel Hebrard, Laurent Houssin, and Pierre Lopez. An Efficient Constraint Programming Approach to Preemptive Job Shop Scheduling. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{juvin_et_al:LIPIcs.CP.2023.19,
author = {Juvin, Carla and Hebrard, Emmanuel and Houssin, Laurent and Lopez, Pierre},
title = {{An Efficient Constraint Programming Approach to Preemptive Job Shop Scheduling}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {19:1--19:16},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.19},
URN = {urn:nbn:de:0030-drops-190568},
doi = {10.4230/LIPIcs.CP.2023.19},
annote = {Keywords: Constraint Programming, Scheduling, Preemptive Resources}
}
Document
Horizontally Elastic Edge Finder Rule for Cumulative Constraint Based on Slack and Density
Abstract
In this paper, we propose an enhancement of the filtering power of the edge finding rule, based on the Profile and the TimeTable data structures. The minimal slack and the maximum density criteria are used to select potential task intervals for the edge finding rule. The strong detection rule of the horizontally elastic edge finder of Fetgo and Tayou is then applied on those intervals, which results in a new filtering rule, named Slack-Density Horizontally Elastic Edge Finder. The new rule subsumes the edge finding rule and it is not comparable to the Gingras and Quimper horizontally elastic edge finder rule and the TimeTable edge finder rule. A two-phase filtering algorithm of complexity 𝒪(n²) (where n is the number of tasks sharing the resource) is proposed for the new rule. Improvements based on the TimeTable are obtained by considering fix part of external tasks which overlap with the potential task intervals. The detection and the adjustment of the improve algorithm are further increased, while the algorithm remains quadratic. Experimental results, on a well-known suite of benchmark instances of Resource-Constrained Project Scheduling Problems, show that the propounded algorithms are competitive with the state-of-the-art algorithms, in terms of running time and tree search reduction.
Cite as
Roger Kameugne, Sévérine Fetgo Betmbe, Thierry Noulamo, and Clémentin Tayou Djamegni. Horizontally Elastic Edge Finder Rule for Cumulative Constraint Based on Slack and Density. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{kameugne_et_al:LIPIcs.CP.2023.20,
author = {Kameugne, Roger and Betmbe, S\'{e}v\'{e}rine Fetgo and Noulamo, Thierry and Djamegni, Cl\'{e}mentin Tayou},
title = {{Horizontally Elastic Edge Finder Rule for Cumulative Constraint Based on Slack and Density}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {20:1--20:17},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.20},
URN = {urn:nbn:de:0030-drops-190574},
doi = {10.4230/LIPIcs.CP.2023.20},
annote = {Keywords: Horizontally Elastic Scheduling, Edge Finder Rule, Profile, TimeTable, Resource-Constrained Project Scheduling Problem}
}
Document
Exploring Hydrogen Supply/Demand Networks: Modeller and Domain Expert Views
Abstract
Energy companies are considering producing renewable fuels such as hydrogen/ammonia. Setting up a production network means deciding where to build production plants, and how to operate them at minimum electricity and transport costs. These decisions are complicated by many factors including the difficulty in obtaining accurate current data (e.g., electricity price and transport costs) for potential supply locations, the accuracy of data predictions (e.g., for demand and costs), and the need for some decisions to be made due to external (not modelled) factors. Thus, decision-makers need access to a user-centric decision system that helps them visualise, explore, interact and compare the many possible solutions of many different scenarios. This paper describes the system we have built to support our energy partner in making such decisions, and shows the advantages of having a graphical user-focused interactive tool, and of using a high-level constraint modelling language (MiniZinc) to implement the underlying model.
Cite as
Matthias Klapperstueck, Frits de Nijs, Ilankaikone Senthooran, Jack Lee-Kopij, Maria Garcia de la Banda, and Michael Wybrow. Exploring Hydrogen Supply/Demand Networks: Modeller and Domain Expert Views. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{klapperstueck_et_al:LIPIcs.CP.2023.21,
author = {Klapperstueck, Matthias and de Nijs, Frits and Senthooran, Ilankaikone and Lee-Kopij, Jack and Garcia de la Banda, Maria and Wybrow, Michael},
title = {{Exploring Hydrogen Supply/Demand Networks: Modeller and Domain Expert Views}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {21:1--21:18},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.21},
URN = {urn:nbn:de:0030-drops-190584},
doi = {10.4230/LIPIcs.CP.2023.21},
annote = {Keywords: Facility Location, Hydrogen Supply Chain, Human-Centric Optimisation}
}
Document
Binary Constraint Trees and Structured Decomposability
Abstract
A binary constraint tree (BCT, Wang and Yap 2022) is a normalized binary CSP whose constraint graph is a tree. A BCT constraint is a constraint represented with a BCT where some of the variables may be hidden (i.e. existentially quantified and used only for internal representation). Structured decomposable negation normal forms (SDNNF) were introduced by Pipatsrisawat and Darwiche (2008) as a restriction of decomposable negation normal forms (DNNF). Both DNNFs and SDNNFs were studied in the area of knowledge compilation. In this paper we show that the BCT constraints are polynomially equivalent to SDNNFs. In particular, a BCT constraint can be represented with an SDNNF of polynomial size and, on the other hand, a constraint that can be represented with an SDNNF, can be represented as a BCT constraint of polynomial size. This generalizes the result of Wang and Yap (2022) that shows that a multivalued decision diagram (MDD) can be represented with a BCT . Moreover, our result provides a full characterization of binary constraint trees using a language that is well studied in the area of knowledge compilation. It was shown by Wang and Yap (2023) that a CSP on n variables of domain sizes bounded by d that has treewidth k can be encoded as a BCT on O(n) variables with domain sizes O(d^{k+1}). We provide an alternative reduction for the case of binary CSPs. This allows us to compile any binary CSP to an SDNNF of size that is parameterized by d and k.
Cite as
Petr Kučera. Binary Constraint Trees and Structured Decomposability. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{kucera:LIPIcs.CP.2023.22,
author = {Ku\v{c}era, Petr},
title = {{Binary Constraint Trees and Structured Decomposability}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {22:1--22:19},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.22},
URN = {urn:nbn:de:0030-drops-190595},
doi = {10.4230/LIPIcs.CP.2023.22},
annote = {Keywords: Binary CSP, Binary Constraint Tree, Structured Decomposability, Strucured DNNF, Polynomial Equivalence}
}
Document
Large Neighborhood Beam Search for Domain-Independent Dynamic Programming
Abstract
Large neighborhood search (LNS) is an algorithmic framework that removes a part of a solution and performs search in the induced search space to find a better solution. While LNS shows strong performance in constraint programming, little work has combined LNS with state space search. We propose large neighborhood beam search (LNBS), a combination of LNS and state space search. Given a solution path, LNBS removes a partial path between two states and then performs beam search to find a better partial path. We apply LNBS to domain-independent dynamic programming (DIDP), a recently proposed generic framework for combinatorial optimization based on dynamic programming. We empirically show that LNBS finds better quality solutions than a state-of-the-art DIDP solver in five out of nine benchmark problem types with a total of 8570 problem instances. In particular, LNBS shows a significant improvement over the existing state-of-the-art DIDP solver in routing and scheduling problems.
Cite as
Ryo Kuroiwa and J. Christopher Beck. Large Neighborhood Beam Search for Domain-Independent Dynamic Programming. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{kuroiwa_et_al:LIPIcs.CP.2023.23,
author = {Kuroiwa, Ryo and Beck, J. Christopher},
title = {{Large Neighborhood Beam Search for Domain-Independent Dynamic Programming}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {23:1--23:22},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.23},
URN = {urn:nbn:de:0030-drops-190605},
doi = {10.4230/LIPIcs.CP.2023.23},
annote = {Keywords: Large Neighborhood Search, Dynamic Programming, State Space Search, Combinatorial Optimization}
}
Document
MDD Archive for Boosting the Pareto Constraint
Abstract
Multi-objective problems are frequent in the real world. In general they involve several incomparable objectives and the goal is to find a set of Pareto optimal solutions, i.e. solutions that are incomparable two by two. In order to better deal with these problems in CP the global constraint Pareto was developed by Schaus and Hartert to handle the relations between the objective variables and the current set of Pareto optimal solutions, called the archive. This constraint handles three operations: adding a new solution to the archive, removing solutions from the archive that are dominated by a new solution, and reducing the bounds of the objective variables. The complexity of these operations depends on the size of the archive. In this paper, we propose to use a multi-valued Decision Diagram (MDD) to represent the archive of Pareto optimal solutions. MDDs are a compressed representation of solution sets, which allows us to obtain a compressed and therefore smaller archive. We introduce several algorithms to implement the above operations on compressed archives with a complexity depending on the size of the archive. We show experimentally on bin packing and multi-knapsack problems the validity of our approach.
Cite as
Steve Malalel, Arnaud Malapert, Marie Pelleau, and Jean-Charles Régin. MDD Archive for Boosting the Pareto Constraint. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{malalel_et_al:LIPIcs.CP.2023.24,
author = {Malalel, Steve and Malapert, Arnaud and Pelleau, Marie and R\'{e}gin, Jean-Charles},
title = {{MDD Archive for Boosting the Pareto Constraint}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {24:1--24:15},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.24},
URN = {urn:nbn:de:0030-drops-190610},
doi = {10.4230/LIPIcs.CP.2023.24},
annote = {Keywords: Constraint Programming, Global Constraint, MDD, Multi-Objective Problem, Pareto Constraint}
}
Document
Learning a Generic Value-Selection Heuristic Inside a Constraint Programming Solver
Abstract
Constraint programming is known for being an efficient approach to solving combinatorial problems. Important design choices in a solver are the branching heuristics, designed to lead the search to the best solutions in a minimum amount of time. However, developing these heuristics is a time-consuming process that requires problem-specific expertise. This observation has motivated many efforts to use machine learning to automatically learn efficient heuristics without expert intervention. Although several generic variable-selection heuristics are available in the literature, the options for value-selection heuristics are more scarce. We propose to tackle this issue by introducing a generic learning procedure that can be used to obtain a value-selection heuristic inside a constraint programming solver. This has been achieved thanks to the combination of a deep Q-learning algorithm, a tailored reward signal, and a heterogeneous graph neural network. Experiments on graph coloring, maximum independent set, and maximum cut problems show that this framework competes with the well-known impact-based and activity-based search heuristics and can find solutions close to optimality without requiring a large number of backtracks.
Cite as
Tom Marty, Tristan François, Pierre Tessier, Louis Gautier, Louis-Martin Rousseau, and Quentin Cappart. Learning a Generic Value-Selection Heuristic Inside a Constraint Programming Solver. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{marty_et_al:LIPIcs.CP.2023.25,
author = {Marty, Tom and Fran\c{c}ois, Tristan and Tessier, Pierre and Gautier, Louis and Rousseau, Louis-Martin and Cappart, Quentin},
title = {{Learning a Generic Value-Selection Heuristic Inside a Constraint Programming Solver}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {25:1--25:19},
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.25},
URN = {urn:nbn:de:0030-drops-190625},
doi = {10.4230/LIPIcs.CP.2023.25},
annote = {Keywords: Branching heuristic, Deep reinforcement learning}
}
Document
Proof Logging for Smart Extensional Constraints
Abstract
Proof logging provides an auditable way of guaranteeing that a solver has produced a correct answer using sound reasoning. This is standard practice for Boolean satisfiability solving, but for constraint programming, a challenge is that every propagator must be able to justify all inferences it performs. Here we demonstrate how to support proof logging for a wide range of previously uncertified global constraints. We do this by showing how to justify every inference that could be performed by the propagation algorithms for two families of generalised extensional constraint: "Smart Table" and "Regular Language Membership".
Cite as
Matthew J. McIlree and Ciaran McCreesh. Proof Logging for Smart Extensional Constraints. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{mcilree_et_al:LIPIcs.CP.2023.26,
author = {McIlree, Matthew J. and McCreesh, Ciaran},
title = {{Proof Logging for Smart Extensional Constraints}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {26:1--26:17},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.26},
URN = {urn:nbn:de:0030-drops-190633},
doi = {10.4230/LIPIcs.CP.2023.26},
annote = {Keywords: Constraint programming, proof logging, extensional constraints}
}
Document
Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning
Abstract
Conflict analysis has been successfully generalized from Boolean satisfiability (SAT) solving to mixed integer programming (MIP) solvers, but although MIP solvers operate with general linear inequalities, the conflict analysis in MIP has been limited to reasoning with the more restricted class of clausal constraint. This is in contrast to how conflict analysis is performed in so-called pseudo-Boolean solving, where solvers can reason directly with 0-1 integer linear inequalities rather than with clausal constraints extracted from such inequalities.
In this work, we investigate how pseudo-Boolean conflict analysis can be integrated in MIP solving, focusing on 0-1 integer linear programs (0-1 ILPs). Phrased in MIP terminology, conflict analysis can be understood as a sequence of linear combinations and cuts. We leverage this perspective to design a new conflict analysis algorithm based on mixed integer rounding (MIR) cuts, which theoretically dominates the state-of-the-art division-based method in pseudo-Boolean solving.
We also report results from a first proof-of-concept implementation of different pseudo-Boolean conflict analysis methods in the open-source MIP solver SCIP. When evaluated on a large and diverse set of 0-1 ILP instances from MIPLIB2017, our new MIR-based conflict analysis outperforms both previous pseudo-Boolean methods and the clause-based method used in MIP. Our conclusion is that pseudo-Boolean conflict analysis in MIP is a promising research direction that merits further study, and that it might also make sense to investigate the use of such conflict analysis to generate stronger no-goods in constraint programming.
Cite as
Gioni Mexi, Timo Berthold, Ambros Gleixner, and Jakob Nordström. Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{mexi_et_al:LIPIcs.CP.2023.27,
author = {Mexi, Gioni and Berthold, Timo and Gleixner, Ambros and Nordstr\"{o}m, Jakob},
title = {{Improving Conflict Analysis in MIP Solvers by Pseudo-Boolean Reasoning}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {27:1--27:19},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.27},
URN = {urn:nbn:de:0030-drops-190641},
doi = {10.4230/LIPIcs.CP.2023.27},
annote = {Keywords: Integer programming, pseudo-Boolean solving, conflict analysis, cutting planes proof system, mixed integer rounding, division, saturation}
}
Document
Using Canonical Codes to Efficiently Solve the Benzenoid Generation Problem with Constraint Programming
Abstract
The Benzenoid Generation Problem (BGP) aims at generating all benzenoid molecules that satisfy some given properties. This problem has important applications in chemistry, and Carissan et al (2021) have shown us that Constraint Programming (CP) is well suited for modelling this problem because properties defined by chemists are easy to express by means of constraints. Benzenoids are described by hexagon graphs and a key point for an efficient enumeration of these graphs is to be invariant to rotations and symmetries. In this paper, we introduce canonical codes that uniquely characterise hexagon graphs while being invariant to rotations and symmetries. We show that these codes may be defined by means of constraints. We also introduce a global constraint for ensuring that codes are canonical, and a global constraint for ensuring that a pattern is included in a code. We experimentally compare our new CP model with the CP-based approach of Carissan et al (2021), and we show that it has better scale-up properties.
Cite as
Xiao Peng and Christine Solnon. Using Canonical Codes to Efficiently Solve the Benzenoid Generation Problem with Constraint Programming. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{peng_et_al:LIPIcs.CP.2023.28,
author = {Peng, Xiao and Solnon, Christine},
title = {{Using Canonical Codes to Efficiently Solve the Benzenoid Generation Problem with Constraint Programming}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {28:1--28:17},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.28},
URN = {urn:nbn:de:0030-drops-190650},
doi = {10.4230/LIPIcs.CP.2023.28},
annote = {Keywords: Benzenoid Generation Problem, Canonical Code, Hexagon Graph}
}
Document
Distribution Optimization in Constraint Programming
Abstract
Stochastic Constraint Programming introduces stochastic variables following a probability distribution to model uncertainty. In the classical setting, probability distributions are given and constant. We propose a framework in which random variables are given a set of possible distributions and only one should be selected. A solution is obtained when all variable distributions are assigned, and all decision variables are assigned too. In such a setting, a constraint on random variables limits the possible distributions its random variables may take. We generalize the notion of chance as the probability of satisfaction of a constraint, called probabilization, given variable distributions. Probabilization can be seen as a generalization of reification in a random setting whose result is a random variable. We define minimal arithmetic to work with stochastic variables having a variable distribution. Using the introduced representation, our framework can in theory save an exponential number of decisions, and represents problems that were previously not representable with finite integer domains. Finally, we model and solve two industrial problems that require this extension - virtual network configuration and assignment of chemical delivery - and show improvement in terms of quality of solution and speed.
Cite as
Guillaume Perez, Gaël Glorian, Wijnand Suijlen, and Arnaud Lallouet. Distribution Optimization in Constraint Programming. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 29:1-29:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{perez_et_al:LIPIcs.CP.2023.29,
author = {Perez, Guillaume and Glorian, Ga\"{e}l and Suijlen, Wijnand and Lallouet, Arnaud},
title = {{Distribution Optimization in Constraint Programming}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {29:1--29:19},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.29},
URN = {urn:nbn:de:0030-drops-190664},
doi = {10.4230/LIPIcs.CP.2023.29},
annote = {Keywords: Constraint Programming, Optimization, Stochastic Optimization}
}
Document
The p-Dispersion Problem with Distance Constraints
Abstract
In the (maxmin) p-dispersion problem we seek to locate a set of facilities in an area so that the minimum distance between any pair of facilities is maximized. We study a variant of this problem where there exist constraints specifying the minimum allowed distances between the facilities. This type of problem, which we call PDDP, has not received much attention within the literature on location and dispersion problems, despite its relevance to real scenarios. We propose both ILP and CP methods to solve the PDDP. Regarding ILP, we give two formulations derived from a classic and a state-of-the-art model for p-dispersion, respectively. Regarding CP, we first give a generic model that can be implemented within any standard CP solver, and we then propose a specialized heuristic Branch&Bound method. Experiments demonstrate that the ILP formulations are more efficient than the CP model, as the latter is unable to prove optimality in reasonable time, except for small problems, and is usually slower in finding solutions of the same quality than the ILP models. However, although the ILP approach displays good performance on small to medium size problems, it cannot efficiently handle larger ones. The heuristic CP-based method can be very efficient on larger problems and is able to quickly discover solutions to problems that are very hard for an ILP solver.
Cite as
Nikolaos Ploskas, Kostas Stergiou, and Dimosthenis C. Tsouros. The p-Dispersion Problem with Distance Constraints. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 30:1-30:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{ploskas_et_al:LIPIcs.CP.2023.30,
author = {Ploskas, Nikolaos and Stergiou, Kostas and Tsouros, Dimosthenis C.},
title = {{The p-Dispersion Problem with Distance Constraints}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {30:1--30:18},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.30},
URN = {urn:nbn:de:0030-drops-190679},
doi = {10.4230/LIPIcs.CP.2023.30},
annote = {Keywords: Facility location, distance constraints, optimization}
}
Document
Partially Preemptive Multi Skill/Mode Resource-Constrained Project Scheduling with Generalized Precedence Relations and Calendars
Abstract
Multi skill resource-constrained project scheduling Problems (MS-RCPSP) have been object of studies from many years. Also, preemption is an important feature of real-life scheduling models. However, very little research has been investigated concerning MS-RCPSPs including preemption, and even less research moving out from academic benchmarks to real problem solving. In this paper we present a solution to those problems based on a hybrid method derived from large neighborhood search incorporating constraint programming components tailored to deal with complex scheduling constraints. We also present a constraint programming model adapted to preemption. The methods are implemented in a new open source python library allowing to easily reuse existing modeling languages and solvers. We evaluate the methods on an industrial case study from aircraft manufacturing including additional complicating constraints such as generalized precedence relations, resource calendars and partial preemption on which the standard CP Optimizer solver, even with the preemption-specific model, is unable to provide solutions in reasonable times. The large neighborhood search method is also able to find new best solutions on standard multi-skill project scheduling instances, performing better than a reference method from the literature.
Cite as
Guillaume Povéda, Nahum Alvarez, and Christian Artigues. Partially Preemptive Multi Skill/Mode Resource-Constrained Project Scheduling with Generalized Precedence Relations and Calendars. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 31:1-31:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{poveda_et_al:LIPIcs.CP.2023.31,
author = {Pov\'{e}da, Guillaume and Alvarez, Nahum and Artigues, Christian},
title = {{Partially Preemptive Multi Skill/Mode Resource-Constrained Project Scheduling with Generalized Precedence Relations and Calendars}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {31:1--31:21},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.31},
URN = {urn:nbn:de:0030-drops-190689},
doi = {10.4230/LIPIcs.CP.2023.31},
annote = {Keywords: Large-scale scheduling problem, partial preemption, multi-skill, multi-mode, resource calendars, constraint programming, large neighborhood search}
}
Document
Assembly Line Preliminary Design Optimization for an Aircraft
Abstract
In the aeronautics industry, each aircraft family has a dedicated manufacturing system. This system is classically designed once the aircraft design is completely finished, which might lead to poor performance. To mitigate this issue, a strategy is to take into account the production system as early as possible in the aircraft design process. In this work, we define the Assembly Line Preliminary Design Problem, which consists in defining, for a given aircraft design, the best assembly line layout and the type and number of machines equipping each workstation. We propose a Constraint Programming encoding for that problem, along with an algorithm based on epsilon constraint for exploring the set of Pareto solutions. We present experiments run on a set of real industrial data. The results show that the approach is promising and offers support to experts in order to compare aircraft designs with each other.
Cite as
Stéphanie Roussel, Thomas Polacsek, and Anouck Chan. Assembly Line Preliminary Design Optimization for an Aircraft. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 32:1-32:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{roussel_et_al:LIPIcs.CP.2023.32,
author = {Roussel, St\'{e}phanie and Polacsek, Thomas and Chan, Anouck},
title = {{Assembly Line Preliminary Design Optimization for an Aircraft}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {32:1--32:19},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.32},
URN = {urn:nbn:de:0030-drops-190690},
doi = {10.4230/LIPIcs.CP.2023.32},
annote = {Keywords: Assembly line design, Constraint Programming, Multi-objective, Industry 4.0}
}
Document
SAT-Based Learning of Compact Binary Decision Diagrams for Classification
Abstract
Decision trees are a popular classification model in machine learning due to their interpretability and performance. However, the number of splits in decision trees grow exponentially with their depth which can incur a higher computational cost, increase data fragmentation, hinder interpretability, and restrict their applicability to memory-constrained hardware. In constrast, binary decision diagrams (BDD) utilize the same split across each level, leading to a linear number of splits in total. Recent work has considered optimal binary decision diagrams (BDD) as compact and accurate classification models, but has only focused on binary datasets and has not explicitly optimized the compactness of the resulting diagrams. In this work, we present a SAT-based encoding for a multi-terminal variant of BDDs (MTBDDs) that incorporates a state-of-the-art direct encoding of numerical features. We then develop and evaluate different approaches to explicitly optimize the compactness of the diagrams. In one family of approaches, we learn a tree BDD first and model the size of the diagram the tree will be reduced to as a secondary objective, in a one-stage or two-stage optimization scheme. Alternatively, we directly learn diagrams that support multi-dimensional splits for improved expressiveness. Our experiments show that direct encoding of numerical features leads to better performance. Furthermore, we show that exact optimization of size leads to more compact solutions while maintaining higher accuracy. Finally, our experiments show that multi-dimensional splits are a viable approach to achieving higher expressiveness with a lower computational cost.
Cite as
Pouya Shati, Eldan Cohen, and Sheila McIlraith. SAT-Based Learning of Compact Binary Decision Diagrams for Classification. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{shati_et_al:LIPIcs.CP.2023.33,
author = {Shati, Pouya and Cohen, Eldan and McIlraith, Sheila},
title = {{SAT-Based Learning of Compact Binary Decision Diagrams for Classification}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {33:1--33:19},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.33},
URN = {urn:nbn:de:0030-drops-190700},
doi = {10.4230/LIPIcs.CP.2023.33},
annote = {Keywords: Binary Decision Diagram, Classification, Compactness, Numeric Data, MaxSAT}
}
Document
Constraint Programming with External Worst-Case Traversal Time Analysis
Abstract
The allocation of software functions to processors under compute capacity and network links constraints is an important optimization problem in the field of embedded distributed systems. We present a hybrid approach to solve the allocation problem combining a constraint solver and a worst-case traversal time (WCTT) analysis that verifies the network timing constraints. The WCTT analysis is implemented as an industrial black-box program, which makes a tight integration with constraint solving challenging. We contribute to a new multi-objective constraint solving algorithm for integrating external under-approximating functions, such as the WCTT analysis, with constraint solving, and prove its correctness. We apply this new algorithm to the allocation problem in the context of automotive service-oriented architectures based on Ethernet networks, and provide a new dataset of realistic instances to evaluate our approach.
Cite as
Pierre Talbot, Tingting Hu, and Nicolas Navet. Constraint Programming with External Worst-Case Traversal Time Analysis. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 34:1-34:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{talbot_et_al:LIPIcs.CP.2023.34,
author = {Talbot, Pierre and Hu, Tingting and Navet, Nicolas},
title = {{Constraint Programming with External Worst-Case Traversal Time Analysis}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {34:1--34: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.34},
URN = {urn:nbn:de:0030-drops-190713},
doi = {10.4230/LIPIcs.CP.2023.34},
annote = {Keywords: Constraint programming, external function, multi-objective optimization, network analysis, worst-case traversal time analysis, abstract interpretation}
}
Document
Efficient Enumeration of Fixed Points in Complex Boolean Networks Using Answer Set Programming
Abstract
Boolean Networks (BNs) are an efficient modeling formalism with applications in various research fields such as mathematics, computer science, and more recently systems biology. One crucial problem in the BN research is to enumerate all fixed points, which has been proven crucial in the analysis and control of biological systems. Indeed, in that field, BNs originated from the pioneering work of R. Thomas on gene regulation and from the start were characterized by their asymptotic behavior: complex attractors and fixed points. The former being notably more difficult to compute exactly, and specific to certain biological systems, the computation of stable states (fixed points) has been the standard way to analyze those BNs for years. However, with the increase in model size and complexity of Boolean update functions, the existing methods for this problem show their limitations. To our knowledge, the most efficient state-of-the-art methods for the fixed point enumeration problem rely on Answer Set Programming (ASP). Motivated by these facts, in this work we propose two new efficient ASP-based methods to solve this problem. We evaluate them on both real-world and pseudo-random models, showing that they vastly outperform four state-of-the-art methods as well as can handle very large and complex models.
Cite as
Van-Giang Trinh, Belaid Benhamou, and Sylvain Soliman. Efficient Enumeration of Fixed Points in Complex Boolean Networks Using Answer Set Programming. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{trinh_et_al:LIPIcs.CP.2023.35,
author = {Trinh, Van-Giang and Benhamou, Belaid and Soliman, Sylvain},
title = {{Efficient Enumeration of Fixed Points in Complex Boolean Networks Using Answer Set Programming}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {35:1--35:19},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.35},
URN = {urn:nbn:de:0030-drops-190720},
doi = {10.4230/LIPIcs.CP.2023.35},
annote = {Keywords: Computational systems biology, Boolean network, Fixed point, Answer set programming}
}
Document
Guided Bottom-Up Interactive Constraint Acquisition
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-dev.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
Addressing Problem Drift in UNHCR Fund Allocation
Abstract
Optimisation models are concise mathematical representations of real-world problems, usually developed by modelling experts in consultation with domain experts. Typically, domain experts are only indirectly involved in the problem modelling process, providing information and feedback, and thus perceive the deployed model as a black box. Unfortunately, real-world problems "drift" over time, where changes in the input data parameters and/or requirements cause the developed model to fail. This requires modelling experts to revisit and update deployed models. This paper identifies the issue of problem drift in optimisation problems using as case study a model we developed for the United Nations High Commissioner for Refugees (UNHCR) to help them allocate funds to different crises. We describe the initial model and the challenges due to problem drift that occurred over the following years. We then use this case study to explore techniques for mitigating problem drift by including domain experts in the modelling process via techniques such as domain specific languages.
Cite as
Sameela Suharshani Wijesundara, Maria Garcia de la Banda, and Guido Tack. Addressing Problem Drift in UNHCR Fund Allocation. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{wijesundara_et_al:LIPIcs.CP.2023.37,
author = {Wijesundara, Sameela Suharshani and Garcia de la Banda, Maria and Tack, Guido},
title = {{Addressing Problem Drift in UNHCR Fund Allocation}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {37:1--37:18},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.37},
URN = {urn:nbn:de:0030-drops-190740},
doi = {10.4230/LIPIcs.CP.2023.37},
annote = {Keywords: Fund Allocation, Problem Drift, Domain Specific Languages, MiniZinc}
}
Document
From Formal Boosted Tree Explanations to Interpretable Rule Sets
Abstract
The rapid rise of Artificial Intelligence (AI) and Machine Learning (ML) has invoked the need for explainable AI (XAI). One of the most prominent approaches to XAI is to train rule-based ML models, e.g. decision trees, lists and sets, that are deemed interpretable due to their transparent nature. Recent years have witnessed a large body of work in the area of constraints- and reasoning-based approaches to the inference of interpretable models, in particular decision sets (DSes). Despite being shown to outperform heuristic approaches in terms of accuracy, most of them suffer from scalability issues and often fail to handle large training data, in which case no solution is offered. Motivated by this limitation and the success of gradient boosted trees, we propose a novel anytime approach to producing DSes that are both accurate and interpretable. The approach makes use of the concept of a generalized formal explanation and builds on the recent advances in formal explainability of gradient boosted trees. Experimental results obtained on a wide range of datasets, demonstrate that our approach produces DSes that more accurate than those of the state-of-the-art algorithms and comparable with them in terms of explanation size.
Cite as
Jinqiang Yu, Alexey Ignatiev, and Peter J. Stuckey. From Formal Boosted Tree Explanations to Interpretable Rule Sets. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 38:1-38:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{yu_et_al:LIPIcs.CP.2023.38,
author = {Yu, Jinqiang and Ignatiev, Alexey and Stuckey, Peter J.},
title = {{From Formal Boosted Tree Explanations to Interpretable Rule Sets}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {38:1--38:21},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.38},
URN = {urn:nbn:de:0030-drops-190758},
doi = {10.4230/LIPIcs.CP.2023.38},
annote = {Keywords: Decision set, interpretable model, gradient boosted tree, BT compilation}
}
Document
Searching for Smallest Universal Graphs and Tournaments with SAT
Abstract
A graph is induced k-universal if it contains all graphs of order k as an induced subgraph. For over half a century, the question of determining smallest k-universal graphs has been studied. A related question asks for a smallest k-universal tournament containing all tournaments of order k.
This paper proposes and compares SAT-based methods for answering these questions exactly for small values of k. Our methods scale to values for which a generate-and-test approach isn't feasible; for instance, we show that an induced 7-universal graph has more than 16 vertices, whereas the number of all connected graphs on 16 vertices, modulo isomorphism, is a number with 23 decimal digits Our methods include static and dynamic symmetry breaking and lazy encodings, employing external subgraph isomorphism testing.
Cite as
Tianwei Zhang and Stefan Szeider. Searching for Smallest Universal Graphs and Tournaments with SAT. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{zhang_et_al:LIPIcs.CP.2023.39,
author = {Zhang, Tianwei and Szeider, Stefan},
title = {{Searching for Smallest Universal Graphs and Tournaments with SAT}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {39:1--39: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.39},
URN = {urn:nbn:de:0030-drops-190760},
doi = {10.4230/LIPIcs.CP.2023.39},
annote = {Keywords: Constrained-based combinatorics, synthesis problems, symmetry breaking, SAT solving, subgraph isomorphism, tournament, directed graphs}
}
Document
FastMapSVM for Predicting CSP Satisfiability
Abstract
Recognizing the satisfiability of Constraint Satisfaction Problems (CSPs) is NP-hard. Although several Machine Learning (ML) approaches have attempted this task by casting it as a binary classification problem, they have had only limited success for a variety of challenging reasons. First, the NP-hardness of the task does not make it amenable to straightforward approaches. Second, CSPs come in various forms and sizes while many ML algorithms impose the same form and size on their training and test instances. Third, the representation of a CSP instance is not unique since the variables and their domain values are unordered. In this paper, we propose FastMapSVM, a recently developed ML framework that leverages a distance function between pairs of objects. We define a novel distance function between two CSP instances using maxflow computations. This distance function is well defined for CSPs of different sizes. It is also invariant to the ordering on the variables and their domain values. Therefore, our framework has broader applicability compared to other approaches. We discuss various representational and combinatorial advantages of FastMapSVM. Through experiments, we also show that it outperforms other state-of-the-art ML approaches.
Cite as
Kexin Zheng, Ang Li, Han Zhang, and T. K. Satish Kumar. FastMapSVM for Predicting CSP Satisfiability. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{zheng_et_al:LIPIcs.CP.2023.40,
author = {Zheng, Kexin and Li, Ang and Zhang, Han and Kumar, T. K. Satish},
title = {{FastMapSVM for Predicting CSP Satisfiability}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {40:1--40:17},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.40},
URN = {urn:nbn:de:0030-drops-190775},
doi = {10.4230/LIPIcs.CP.2023.40},
annote = {Keywords: Constraint Satisfaction Problems, Machine Learning, FastMapSVM}
}
Document
Improving Local Search for Pseudo Boolean Optimization by Fragile Scoring Function and Deep Optimization
Abstract
Pseudo-Boolean optimization (PBO) is usually used to model combinatorial optimization problems, especially for some real-world applications. Despite its significant importance in both theory and applications, there are few works on using local search to solve PBO. This paper develops a novel local search framework for PBO, which has three main ideas. First, we design a two-level selection strategy to evaluate all candidate variables. Second, we propose a novel deep optimization strategy to disturb some search spaces. Third, a sampling flipping method is applied to help the algorithm jump out of local optimum. Experimental results show that the proposed algorithms outperform three state-of-the-art PBO algorithms on most instances.
Cite as
Wenbo Zhou, Yujiao Zhao, Yiyuan Wang, Shaowei Cai, Shimao Wang, Xinyu Wang, and Minghao Yin. Improving Local Search for Pseudo Boolean Optimization by Fragile Scoring Function and Deep Optimization. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 41:1-41:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{zhou_et_al:LIPIcs.CP.2023.41,
author = {Zhou, Wenbo and Zhao, Yujiao and Wang, Yiyuan and Cai, Shaowei and Wang, Shimao and Wang, Xinyu and Yin, Minghao},
title = {{Improving Local Search for Pseudo Boolean Optimization by Fragile Scoring Function and Deep Optimization}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {41:1--41:18},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.41},
URN = {urn:nbn:de:0030-drops-190784},
doi = {10.4230/LIPIcs.CP.2023.41},
annote = {Keywords: Local Search, Pseudo-Boolean Optimization, Deep Optimization}
}
Document
Short Paper
Predict-Then-Optimise Strategies for Water Flow Control (Short Paper)
Abstract
A pressure sewer system is a network of pump stations used to collect and manage sewage from individual properties that cannot be directly connected to the gravity driven sewer network due to the topography of the terrain. We consider a common scenario for a pressure sewer system, where individual sites collect sewage in a local tank, and then pump it into the gravity fed sewage network. Standard control systems simply wait until the local tank reaches (near) capacity and begin pumping out. Unfortunately such simple control usually leads to peaks in sewage flow in the morning and evening, corresponding to peak water usage in the properties. High peak flows require equalization basins or overflow systems, or larger capacity sewage treatment plants. In this paper we investigate combining prediction and optimisation to better manage peak sewage flows. We use simple prediction methods to generate realistic possible future scenarios, and then develop optimisation models to generate pumping plans that try to smooth out flows into the network. The solutions of these models create a policy for pumping out that is specialized to individual properties and which overall is able to substantially reduce peak flows.
Cite as
Vincent Barbosa Vaz, James Bailey, Christopher Leckie, and Peter J. Stuckey. Predict-Then-Optimise Strategies for Water Flow Control (Short Paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 42:1-42:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{barbosavaz_et_al:LIPIcs.CP.2023.42,
author = {Barbosa Vaz, Vincent and Bailey, James and Leckie, Christopher and J. Stuckey, Peter},
title = {{Predict-Then-Optimise Strategies for Water Flow Control}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {42:1--42:10},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.42},
URN = {urn:nbn:de:0030-drops-190795},
doi = {10.4230/LIPIcs.CP.2023.42},
annote = {Keywords: Water Flow Control, Optimization, Machine Learning}
}
Document
Short Paper
Constraint Programming Models for Depth-Optimal Qubit Assignment and SWAP-Based Routing (Short Paper)
Abstract
Due to the limited connectivity of gate model quantum devices, logical quantum circuits must be compiled to target hardware before they can be executed. Often, this process involves the insertion of SWAP gates into the logical circuit, usually increasing the depth of the circuit, achieved by solving a so-called qubit assignment and routing problem. Recently, a number of integer linear programming (ILP) models have been proposed for solving the qubit assignment and routing problem to proven optimality. These models encode the objective function and constraints of the problem, and leverage the use of automated solver technology to find hardware-compliant quantum circuits. In this work, we propose constraint programming (CP) models for this problem and compare their performance against ILP for circuit depth minimization for both linear and two-dimensional grid lattice device topologies on a set of randomly generated instances. Our empirical analysis indicates that the proposed CP approaches outperform the ILP models both in terms of solution quality and runtime.
Cite as
Kyle E. C. Booth. Constraint Programming Models for Depth-Optimal Qubit Assignment and SWAP-Based Routing (Short Paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 43:1-43:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{booth:LIPIcs.CP.2023.43,
author = {Booth, Kyle E. C.},
title = {{Constraint Programming Models for Depth-Optimal Qubit Assignment and SWAP-Based Routing}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {43:1--43:10},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.43},
URN = {urn:nbn:de:0030-drops-190805},
doi = {10.4230/LIPIcs.CP.2023.43},
annote = {Keywords: Qubit routing, quantum computing, constraint programming, combinatorial optimization}
}
Document
Short Paper
Constraint Model for the Satellite Image Mosaic Selection Problem (Short Paper)
Abstract
Satellite imagery solutions are widely used to study and monitor different regions of the Earth. However, a single satellite image can cover only a limited area. In cases where a larger area of interest is studied, several images must be stitched together to create a single larger image, called a mosaic, that can cover the area. Today, with the increasing number of satellite images available for commercial use, selecting the images to build the mosaic is challenging, especially when the user wants to optimize one or more parameters, such as the total cost and the cloud coverage percentage in the mosaic. More precisely, for this problem the input is an area of interest, several satellite images intersecting the area, a list of requirements relative to the image and the mosaic, such as cloud coverage percentage, image resolution, and a list of objectives to optimize. We contribute to the constraint and mixed integer lineal programming formulation of this new problem, which we call the satellite image mosaic selection problem, which is a multi-objective extension of the polygon cover problem. We propose a dataset of realistic and challenging instances, where the images were captured by the satellite constellations SPOT, Pléiades and Pléiades Neo. We evaluate and compare the two proposed models and show their efficiency for large instances, up to 200 images.
Cite as
Manuel Combarro Simón, Pierre Talbot, Grégoire Danoy, Jedrzej Musial, Mohammed Alswaitti, and Pascal Bouvry. Constraint Model for the Satellite Image Mosaic Selection Problem (Short Paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{combarrosimon_et_al:LIPIcs.CP.2023.44,
author = {Combarro Sim\'{o}n, Manuel and Talbot, Pierre and Danoy, Gr\'{e}goire and Musial, Jedrzej and Alswaitti, Mohammed and Bouvry, Pascal},
title = {{Constraint Model for the Satellite Image Mosaic Selection Problem}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {44:1--44:15},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.44},
URN = {urn:nbn:de:0030-drops-190815},
doi = {10.4230/LIPIcs.CP.2023.44},
annote = {Keywords: constraint modeling, satellite imaging, set covering, polygon covering}
}
Document
Short Paper
Partitioning a Map into Homogeneous Contiguous Regions: A Branch-And-Bound Approach Using Decision Diagrams (Short Paper)
Abstract
Regionalization is a crucial spatial analysis technique used for partitioning a map divided into zones into k continuous areas, optimizing the similarity of zone attributes within each area. This technique has a variety of applications in fields like urban planning, environmental management, and geographic information systems. The REDCAP algorithm is a well-known approach for addressing the regionalization problem. It consists of two main steps: first, it generates a spatially contiguous tree (SCT) representing the neighborhood structure of the set of spatial objects using a contiguity-constrained hierarchical clustering method. Second, it greedily removes k-1 edges from the SCT to create k regions. While this approach has proven to be effective, it may not always produce the most optimal solutions. We propose an alternative method for the second step, an exact dynamic programming (DP) formulation for the k-1 edges removal problem. This DP is solved using a multi-valued decision diagram (MDD)-based branch and bound solver leading to a more optimal solution. We compared our proposed method with the REDCAP state-of-the-art technique on real data and synthetic ones, using different instances of the regionalization problem and different supervised and unsupervised metrics. Our results indicate that our approach provides higher quality partitions than those produced by REDCAP at acceptable computational costs. This suggests that our method could be a viable alternative for addressing the regionalization problem in various applications.
Cite as
Nicolas Golenvaux, Xavier Gillard, Siegfried Nijssen, and Pierre Schaus. Partitioning a Map into Homogeneous Contiguous Regions: A Branch-And-Bound Approach Using Decision Diagrams (Short Paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 45:1-45:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{golenvaux_et_al:LIPIcs.CP.2023.45,
author = {Golenvaux, Nicolas and Gillard, Xavier and Nijssen, Siegfried and Schaus, Pierre},
title = {{Partitioning a Map into Homogeneous Contiguous Regions: A Branch-And-Bound Approach Using Decision Diagrams}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {45:1--45:10},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.45},
URN = {urn:nbn:de:0030-drops-190825},
doi = {10.4230/LIPIcs.CP.2023.45},
annote = {Keywords: Regionalization, Redcap, Skater, Multivalued Decision Diagrams}
}
Document
Short Paper
Constraint Programming to Improve Hub Utilization in Autonomous Transfer Hub Networks (Short Paper)
Abstract
The Autonomous Transfer Hub Network (ATHN) is one of the most promising ways to adapt self-driving trucks for the freight industry. These networks use autonomous trucks for the middle mile, while human drivers perform the first and last miles. This paper extends previous work on optimizing ATHN operations by including transfer hub capacities, which are crucial for labor planning and policy design. It presents a Constraint Programming (CP) model that shifts an initial schedule produced by a Mixed Integer Program to minimize the hub capacities. The scalability of the CP model is demonstrated on a case study at the scale of the United States, based on data provided by Ryder System, Inc. The CP model efficiently finds optimal solutions and lowers the necessary total hub capacity by 42%, saving $15.2M in annual labor costs. The results also show that the reduced capacity is close to a theoretical (optimistic) lower bound.
Cite as
Chungjae Lee, Wirattawut Boonbandansook, Vahid Eghbal Akhlaghi, Kevin Dalmeijer, and Pascal Van Hentenryck. Constraint Programming to Improve Hub Utilization in Autonomous Transfer Hub Networks (Short Paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 46:1-46:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{lee_et_al:LIPIcs.CP.2023.46,
author = {Lee, Chungjae and Boonbandansook, Wirattawut and Akhlaghi, Vahid Eghbal and Dalmeijer, Kevin and Van Hentenryck, Pascal},
title = {{Constraint Programming to Improve Hub Utilization in Autonomous Transfer Hub Networks}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {46:1--46:11},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.46},
URN = {urn:nbn:de:0030-drops-190835},
doi = {10.4230/LIPIcs.CP.2023.46},
annote = {Keywords: Constraint Programming, Autonomous Trucking, Tranfer Hub Network}
}
Document
Short Paper
A New Approach to Finding 2 x n Partially Spatially Balanced Latin Rectangles (Short Paper)
Abstract
Partially spatially balanced Latin rectangles are combinatorial structures that are important for experimental design. However, it is computationally challenging to find even small optimally balanced rectangles, where previous work has not been able to prove optimality for any rectangle with a dimension above size 11. Here we introduce a graph-based encoding for the 2 × n case based on finding the minimum-cost clique of size n. This encoding inspires a new mixed-integer programming (MIP) formulation, which finds exact solutions for the 2 × 12 and 2 × 13 cases and provides improved bounds up to n = 20. Compared to three other methods, the new formulation establishes the best lower bound in all cases and establishes the best upper bound in five out of seven cases.
Cite as
Renee Mirka, Laura Greenstreet, Marc Grimson, and Carla P. Gomes. A New Approach to Finding 2 x n Partially Spatially Balanced Latin Rectangles (Short Paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 47:1-47:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{mirka_et_al:LIPIcs.CP.2023.47,
author = {Mirka, Renee and Greenstreet, Laura and Grimson, Marc and Gomes, Carla P.},
title = {{A New Approach to Finding 2 x n Partially Spatially Balanced Latin Rectangles}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {47:1--47:11},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.47},
URN = {urn:nbn:de:0030-drops-190849},
doi = {10.4230/LIPIcs.CP.2023.47},
annote = {Keywords: Spatially balanced Latin squares, partially spatially balanced Latin rectangles, minimum edge weight clique, combinatorial optimization, mixed integer programming, imbalance, cliques}
}
Document
Short Paper
Proven Optimally-Balanced Latin Rectangles with SAT (Short Paper)
Abstract
Motivated by applications from agronomic field experiments, Díaz, Le Bras, and Gomes [CPAIOR 2015] introduced Partially Balanced Latin Rectangles as a generalization of Spatially Balanced Latin Squares. They observed that the generation of Latin rectangles that are optimally balanced is a highly challenging computational problem. They computed, utilizing CSP and MIP encodings, Latin rectangles up to 12 × 12, some optimally balanced, some suboptimally balanced.
In this paper, we develop a SAT encoding for generating balanced Latin rectangles. We compare experimentally encoding variants. Our results indicate that SAT encodings perform competitively with the MIP encoding, in some cases better. In some cases we could find Latin rectangles that are more balanced than previously known ones. This finding is significant, as there are many arithmetic constraints involved. The SAT approach offers the advantage that we can certify that Latin rectangles are optimally balanced through DRAT proofs that can be verified independently.
Cite as
Vaidyanathan Peruvemba Ramaswamy and Stefan Szeider. Proven Optimally-Balanced Latin Rectangles with SAT (Short Paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 48:1-48:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{peruvembaramaswamy_et_al:LIPIcs.CP.2023.48,
author = {Peruvemba Ramaswamy, Vaidyanathan and Szeider, Stefan},
title = {{Proven Optimally-Balanced Latin Rectangles with SAT}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {48:1--48:10},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.48},
URN = {urn:nbn:de:0030-drops-190855},
doi = {10.4230/LIPIcs.CP.2023.48},
annote = {Keywords: combinatorial design, SAT encodings, certified optimality, arithmetic constraints, spatially balanced Latin rectangles}
}
Document
Short Paper
Enumerative Level-2 Solution Counting for Quantified Boolean Formulas (Short Paper)
Abstract
We lift the problem of enumerative solution counting to quantified Boolean formulas (QBFs) at the second level. In contrast to the well-explored model counting problem for SAT (#SAT), where models are simply assignments to the Boolean variables of a formula, we are now dealing with tree (counter-)models reflecting the dependencies between the variables of the first and the second quantifier block. It turns out that enumerative counting on the second level does not give the complete model count. We present the - to the best of our knowledge - first approach of counting tree (counter-)models together with a counting tool that exploits state-of-the-art QBF technology. We provide several kinds of benchmarks for testing our implementation and illustrate in several case studies that solution counting provides valuable insights into QBF encodings.
Cite as
Andreas Plank, Sibylle Möhle, and Martina Seidl. Enumerative Level-2 Solution Counting for Quantified Boolean Formulas (Short Paper). In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 49:1-49:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
Copy BibTex To Clipboard
@InProceedings{plank_et_al:LIPIcs.CP.2023.49,
author = {Plank, Andreas and M\"{o}hle, Sibylle and Seidl, Martina},
title = {{Enumerative Level-2 Solution Counting for Quantified Boolean Formulas}},
booktitle = {29th International Conference on Principles and Practice of Constraint Programming (CP 2023)},
pages = {49:1--49:10},
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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2023.49},
URN = {urn:nbn:de:0030-drops-190867},
doi = {10.4230/LIPIcs.CP.2023.49},
annote = {Keywords: QBF, Second-Level Model Counting}
}