Tutorials
CPMpy, a numpy-based CP modeling environment
Presenter: Tias Guns, KU Leuven and VUB (Belgium)
CPMpy is a new CP modeling environment in Python. Its two distinguishing characteristics is that 1) it aims to make it easy to both model CP problems, as well as making it easy to repeatedly call solvers, iteratively change the input to solvers as well as combine solvers, 2) it is based on the n-dimensional numpy array as basic data structure, which is common in many scientific python libraries. CPMpy wants to promote the use of CP solvers as oracles in a wider program. We will provide examples of how it is already used in Tias' lab to combine convolutional neural network predictions with CP models (e.g. for visual sudoku), to use a CP solver inside the training of neural networks (decision-focussed learning) and to extract minimal unsatisfiable subsets and sequential explanations of CSPs.
Tutorial in equity modeling
Presenter: John Hooker, Professor of Operations Research, and Holleran Professor of Business Ethics and Social Responsibility, Carnegie Mellon University
CThere is a growing interest in incorporating equity and fairness into optimization and constraint satisfaction models. Yet it is far from obvious how to formulate such ethical concerns mathematically. This tutorial surveys a variety of constraints and objective functions that have been proposed for this purpose, as well as possible justifications for them. It begins with a brief background in concepts of ethics, distributive justice, and social choice theory, so as to lay a foundation for critical evaluation of mathematical criteria. It then examines a number of fairness metrics, with an emphasis on those that combine equity with efficiency. These include inequality measures, Rawlsian maximin and leximax criteria, alpha fairness and the special case of proportional fairness (also known as the Nash bargaining solution), the Kalai-Smorodinsky bargaining solution, and recently proposed threshold functions that integrate equity and efficiency. It also provides an exposition and critical analysis of fairness measures that are popular in machine learning, such as individual fairness and such statistical fairness metrics as demographic parity, equalized odds, predictive rate parity, and counterfactual fairness. The implications of the various equity measures are compared in specific applications, such as healthcare provision and disaster response.
Visualization for Constraint Programming
Presenter: Helmut Simonis, SFI Insight Centre for Data Analytics, University College Cork, Ireland
Presenter: Guido Tack, Department of Data Science and AI, Monash University, Melbourne, Australia
Visualization is probably the most powerful tool to help develop, test and improve Constraint Programming solutions. Many different tools and methods have been developed in the past to understand constraint propagation, the shape of the search tree, or properties of solutions. This tutorial will present past approaches, the tools currently available, and describe a methodology to use visualization throughout the development process. We will give examples of the use of visualization for small and large projects, and show which questions during development of a solution can be addressed by existing or custom visualizations.
Applying Constraint Programming to Group Theory
Presenters: Christopher Jefferson, University of St. Andrews
There is a long history of dealing with symmetry in constraint problems using results from group theory -- both by adding new constraints (in particular lexicographic ordering constraints), or dynamically changing the search with techniques like Symmetry Breaking During Search. Less well known in the CP community is how problems are solved using backtrack in computational group theory systems. These systems have many similarities to backtracking constraint solvers, featuring propagators (known there as refiners) and backtrack search. There are also significant differences, for example variables are stored very differently, and new symmetries can arise as search progresses. This talk will present a unified overview of backtrack search in computational group theory. This talk will begin with a brief overview of group theory and early systems. The talk will then discuss Brendan McKay's "Nauty" graph solver, Jeffry S. Leon's Partition Backtrack system, and "Vole", a new state of the art graph backtracking which provides the functionality of both of these existing systems.