View: session overviewtalk overview

CP 2023 Opening

**Invited Talk 1**: __Great Hall (#1022)__ (Chair: Roland Yap)

- Laurent Perron (Google, France),
**The CP-SAT-LP solve**r - Petr Vilím (ScheduleOpt),
**CP Solver Design for Maximum CPU Utilization**

__Great Hall Lower Gallery (#1022K)__

Modelling 1, __Great Hall (#1022)__ (Chair: Helmut Simonis)

10:40 | Simplifying Step-wise Explanation Sequences PRESENTER: Ignace Bleukx ABSTRACT. Explaining constraint programs is useful to debug an unsatisfiable set of constraints, to understand why a given solution is optimal, or to understand the values in a unique solution. A recently-proposed framework for step-wise explaining constraint programs works well to step-by-step explain unique solutions to a problem. It can also be used to step-wise explain why a model is unsatisfiable, but this may create redundant steps and introduce superfluous information in explanation sequences. This paper proposes methods to simplify any 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 our techniques can significantly simplify step-wise explanation sequences. |

11:10 | Addressing problem drift in the UNHCR fund allocation problem 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 system to fail. Problem drift requires modelling experts to revisit and update deployed models. This paper presents 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, which was successfully deployed, and the challenges due to problem drift that occurred over the following years. We 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 |

11:40 | Searching for smallest universal graphs and tournaments with SAT PRESENTER: Stefan Szeider 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 k-universal graphs with the smallest number of vertices 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 for small values of k. Our methods scale to values for which it is not feasible to enumerate all candidate graphs up to isomorphism and check for each graph whether it is universal. Therefore we need to integrate isomorph-free generation and universality check. With our methods we can show, for instance, that an induced 7-universal graph has more than 16 vertices, although the number of all connected graphs on 16 vertices, modulo isomorphism, is a number with 22 digits. Our methods include static and dynamic symmetry breaking and lazy encodings that employ external subgraph isomorphism testing. |

Scheduling, __East Common Room (#1034)__ (Chair: Chris Beck)

__Great Hall Lower Gallery (#1022K)__

**Tutorial 1**: __Great Hall (#1022)__ (Chair: Gilles Pesant)

- Vijay Ganesh (Univesity of Waterloo),
**Machine Learning for Solvers**

Search 1, __East Common Room (#1034)__ (Chair: Neng-Fa Zhou)

Decision Diagrams 1, __Great Hall (#1022)__ (Chair: Jean-Charles Regin)

Symmetries, __East Common Room (#1034)__ (Chair: Jimmy Lee)

__Great Hall Lower Gallery (#1022K)__

Applications 1, __Great Hall (#1022)__ __(__Chair: Mats Carlson__)__

Constraints 1, __East Common Room (#1034)__ (Chair: Stefan Szeider)

**CP 2023 Welcome Reception**,** **__Great Hall (#1022)__