Tutorials
For any questions regarding the tutorials, please contact the Tutorial Chair, Prof Pierre Schaus (pierre.schaus@uclouvain.be).
Modeling and Solving Combinatorial Optimization Problems with Domain-Independent Dynamic Programming
Domain-independent dynamic programming (DIDP) is a recently proposed technology for solving combinatorial optimization based on dynamic programming (DP). DIDP is a model-based paradigm similar to constraint programming (CP): a user formulates a problem as a DP model and solves it using a general-purpose DP solver. However, unlike CP, the DP model describes the problem using states and transitions between states. Recent research has demonstrated that DIDP has state-of-the-art performance in multiple combinatorial optimization problem classes, outperforming commercial CP and mixed integer programming (MIP) solvers. This tutorial introduces the basics of DIDP and does a hands-on session using DIDPPy, the Python interface of our DIDP software framework. After introducing the background, we present an example of a DP model that is implemented and solved with DIDPPy. Then, we do a hands-on session using the Jupyter Notebook, where participants formulate and solve a DP model for a given combinatorial optimization problem. We then introduce the heuristic search algorithms that are used in the currently developed DIDP solvers and present their empirical performance evaluated in our recent paper.
J Christopher Beck is a Professor in the Department of Mechanical & Industrial Engineering at the University of Toronto. He is the author of over 160 peer reviewed conference and journal publications in AI and Operations Research in areas such as planning, scheduling, constraint programming, and combinatorial optimization. Chris is a former President of the Executive Committee for the International Conference on Automated Planning and Scheduling, the current Past President of the Association for Constraint Programming, and the Associate Editor-in-Chief of the Journal of Artificial Intelligence Research. He recently developed domain-independent dynamic programming with his student, Ryo Kuroiwa.
Ryo Kuroiwa is a Ph.D. student at the University of Toronto supervised by Prof. J. Christopher Beck. During his Ph.D., he developed domain-independent dynamic programming with his supervisor, publishing papers at the International Conference on Automated Planning and Scheduling, the International Conference on Principles and Practices of Constraint Programming, and the AAAI Conference on Artificial Intelligence.
Constraint Programming with JuMP
This tutorial provides a comprehensive guide to solving constraint programming problems using JuMP, a domain-specific modeling language for mathematical optimization in Julia. JuMP supports a wide range of solvers including SAT, CP (both Constraint Programming and Conic Programming), and Mixed-Integer Linear Programming (MILP) solvers, all accessible through a unified interface. One of JuMP's key features is its powerful constraint reformulation mechanism, which allows users and solvers to define new constraint types and reformulations or to disable existing ones. JuMP's automatic reformulation process involves solving a shortest path problem within a hypergraph that represents all possible constraint types and their reformulations. This innovative approach enables users to effectively explore and experiment with different reformulations, ensuring the appropriate model is communicated to the solver. JuMP also implements an interface with MiniZinc which allows it to use any solver that MiniZinc supports. We also show how to use callbacks with MILP solvers, an essential feature to combine the generic heuristic of the solver with the user problem-specific knowledge. During the tutorial, we go through several examples to illustrate each aspect of the talk.
Benoît Legat is starting as Assistant Professor at UCLouvain in the Mathematical Engineering department (INMA) of the ICTEAM. He received his Ph.D. degree in applied mathematics from the UCLouvain, Belgium, in 2020. He then worked as postdoctoral researcher at MIT with Prof. Pablo Parrilo in the LIDS and now at KU Leuven with Prof. Bart De Moor in the STADIUS. His research interests include global landscape analysis of nonconvex optimization problems as well as their convex formulations with a focus on the fields of machine learning, polynomial optimization, invariant set computation and optimal control.
Constraint Acquisition - A Tutorial on Learning Constraint Models
Constraint Programming (CP) is a powerful paradigm for solving complex combinatorial problems, but its adoption is often hindered by the expertise required for modeling. Constraint Acquisition (CA) aims to mitigate this bottleneck by semi-automating the modeling process. This tutorial will provide a comprehensive introduction to CA, covering both passive and interactive learning approaches. For passive acquisition, we will explore CA techniques for learning constraint models from datasets of existing solutions and non-solutions. We will discuss different approaches that focus on learning fixed-arity or global constraints, handling noise, and generalizing the learned models to handle varying problem instances. We will also review interactive CA techniques, highlighting the recent integration of statistical Machine Learning methods that enhance efficiency by reducing the number of queries needed. During the tutorial, state-of-the-art CA tools implemented in the open-source CPMpy modeling language will be demonstrated. Finally, we will discuss current challenges and future directions in constraint acquisition research.
Dimos Tsouros is a PostDoc researcher at the DTAI KU Leuven lab. His expertise is in interactive constraint acquisition. He earned an honorable mention in the Doctoral Dissertation Award of ACP in 2022 for his PhD. He has a strong interest in rich interactive techniques between users and solving systems, focusing on a more human-aware approach to the constraint solving process.