Today was the end of the ACP Winter School 2024 in Aussois, in the mountains of Savoie in France. As the group photo shows, people look very happy with with the school. There was an excellent program at the school, but also some experience of snow at the end of March.
My own talks covered the “Introduction to Constraint Programming” and the “Applications of Constraint Programming” parts of the course, but the school covered a lot more ground, as you can see at https://school.a4cp.org/winter2024/.
The slides of the lectures should become freely available on the Caseine platform in the near future, definitely worth a look.
I attended the CPML (Constraint Programming/Machine Learning) bridge event at this year’s AAAI 2024 conference in Vancouver BC, Canada, and presented some work on “Scheduling Examples for Constraint Acquisition” at the event. Unfortunately, the weather was rather mixed, as the image below shows.
My own presentation looked at finding examples of scheduling problems as benchmarks for Constraint Acquisition tools.
In the talk we consider different sources of the scheduling problems, starting from teaching examples in books and courses on Constraint Programming, to problems described in the literature (with data provided as supplementary materials for papers and articles), and more complex datasets coming from industrial applications. One of the problems encountered is that the data formats of the different problems are quite ad-hoc, and very often cannot be easily interpreted by the Constraint Acquisition tools. We will talk more about this in the future.
The deadline for registration at the ACP Winter School 2024 is rapidly approaching. Register before March 1st at https://school.a4cp.org/winter2024/ for a week of exiting lectures and practice sessions on Constraint Programming in the middle of the French alps.
I will give two presentations at the school, a general introduction to CP, and an overview of CP applications. The other presenters at the school will do the heavy lifting, talking about CP solvers, propagation and search, and explainable CP. Students will use the Choco-solver in the Caseine environment to work on an constraint problem during the week.
Another date for your calendar. After the very successful ACP Summerschool 2023, the next school for the ACP will be in Winter, March 25-29, 2024. The location will be Aussois, in the mountains of Savoie in France. The school will be organized by Margaux Nattaf of Grenoble INP, together with Christine Solnon and Arnaud Malapert. I hope that there will be some snow on the slopes as well 🙂
One of the initiatives announced by the ACP president David Bergman in the general meeting yesterday concerns the Teaching of Constraint Programming. Of course, I was interested.
The idea is to build on the success of the WTCP 2023 workshop and the material collected by the community survey to create an archive of teaching materials for different types of courses and audiences. I have been invited to contribute to the initiative, and Tejas Santanam from Georgia Tech and Jimmy Lee from the Chinese University of Hong Kong have gracefully agreed to help with this.
But we need more contributors, to agree on a way forward and to collect, collate, and perhaps create more materials for the community. If you are interested in teaching, and are willing to participate, please drop me a note (helmut.simonis@insight-centre.org), so that we can arrange a working group. The current plan is to do the easy steps first, and produce some useful first version in the immediate future.
If you are teaching a CP or related course, but have not yet had the time to fill the survey, please visit https://forms.gle/v54HUsbSXcyHmfME9 to enter some details. It will only take a few minutes.
Every year some papers are selected as the best submissions in their categories for the CP conference. This year there is a best paper award and a best application track paper award.
The best paper award for CP 2023 goes to Matthew McIlree and Ciaran McCreesh from Glasgow University for their paper “Proof Logging for Smart Extensional Constraints”. We were told that this is Matthew’s first submission, and first time at the CP conference. That is most impressive! Well done and congratulations to both authors. You can find a version of the paper in the preliminary proceedings at https://submission.dagstuhl.de/collections/CP-2023/preliminary-proceedings/26
The best application track paper award for CP 2023 goes to Matthias Klapperstueck, Frits de Nijs, Ilankaikone Senthooran, Jack Lee-Kopij, Maria Garcia de la Banda, and Michael Wybrow from Monash University and Woodside Energy for their paper “Exploring Hydrogen Supply/Demand Networks: Modeller and Domain Expert Views” available at https://submission.dagstuhl.de/collections/CP-2023/preliminary-proceedings/21 Congratulations to the authors which bring together skills as domain experts, constraint programming modellers, and visualization experts.
There were a number of welcome announcements made at the ACP General Meeting at CP 2023 in Toronto. The locations of the next CPAIOR conference and the next three CP Conferences were announced yesterday.
CPAIOR2024 will be in Uppsala at the end of May 2024. The local organizers are Maria Andreina Francisco Rodriguez, Justin Pearson, and Pierre Flener from Uppsala University, the program chair is Bistra Dilkina from the University of Southern California. Abstract deadline is November 27 28th. You may remember the CP 2013 conference, which was also held in Uppsala, but CPAIOR will be in brand-new building, close to the city centre. The conference website can be found at https://sites.google.com/view/cpaior2024/
CP 2024 will be held in Girona, in Catalonia, Spain in September 2024. Local organizers are Miquel Bofill and Mateu Villaret from the University of Girona (pictured with David Bergman, ACP President), program chair is Paul Shaw, from IBM, France. Details about submission timeline will be made later.
CP 2025 will be in Glasgow, Scotland, with local organizers Ciaran McCreesh and Blair Archibald from the University of Glasgow, and program chair Maria Garcia de la Banda from Monash University in Melbourne. This will be a return to Scotland for the CP Conference, after the CP 2010 conference in St.Andrews.
CP 2026 will be in Lisbon, Portugal, as part of FLOC. As is the rule with such large federated conferences, the co-location decision has to be taken early, to allow planning of the venue and timing of the conference. In any case, Lisbon is a beautiful place, CP 2009 was there as well.
Plenty of announcements at the General Meeting of the ACP, held as part of the CP 2023 conference in Toronto. The Most important things first, the ACP awards announced for 2023.
Mats Carlsson from RI.SE in Sweden was announced as the winner of the ACP Research Excellence Award in 2023. Mats is well known for his work on the SICStus Prolog system, which has some of the best global constraints for scheduling and packing problems. I’ve been using his system for many years, resulting in a number of papers. Congratulations to Mats for this well deserved award.
Ciaran McCreesh of the University of Glasgow was awarded the Early Career Researcher Award of the ACP for his work on the use of Constraint Programming for Graph analysis and proof logging. This is an area I know very little about, but I find Ciaran’s presentations always interesting. Congratulations!
Stephan Gocht from Lund University in Sweden won the ACP Doctoral Research award for this thesis “Certifying Correctness for Combinatorial Algorithms: by Using Pseudo-Boolean Reasoning”, also on proof logging. This seems to be a hot topic right now! Congratulations to Stephan, who, I read, is also looking into starting his own company. Best of luck!
The CP conference this year in Toronto (https://cp2023.a4cp.org/index.html) is a good place for application papers. There were a lot of submissions, and twelve application track papers have been selected during review. In addition, there are a number of other papers in the conference that are talking about interesting applications in other contexts.
The application papers are scattered a bit around the program, so I tried to collect them here in one place for easy reference. In order of appearance in the program:
Addressing problem drift in the UNHCR fund allocation problem (paper) Sameela Wijesundara, Maria Garcia De La Banda and Guido Tack
First Impression: A very interesting problem of making sure that money made available for the UN is actually allocated to matching projects, reducing unspent funds at the end of the year. We are talking about finding a use for hundreds of million dollars every year! It also addresses the more fundamental problem what happens to your CP Application when the problem constraints and the input data format change after a while, and your program no longer solves the problem.
Partially Preemptive Multi Skill/Mode Resource-constrained Project Scheduling with Generalized Precedence Relations and Calendars (paper) Guillaume Poveda, Nahum Alvarez and Christian Artigues
A CP Approach for the Liner Shipping Network Design Problem (paper) Yousra El Ghazi, Djamal Habet and Cyril Terrioux
First impression: Solving a very big problem for shipping companies, resulting in a huge impact on the global economy. How do you decide which routes, stopping at which ports, you want to serve as a company, and how do you assign ships to those routes so that you can handle the projected demand. Logistics with a capital L.
Constraint programming models for depth-optimal qubit assignment and SWAP-based routing (paper) Kyle E. C. Booth
Assembly Line Preliminary Design Optimization for an Aircraft Airframe (paper) Stephanie Roussel, Thomas Polacsek and Anouck Chan
First impression: A very interesting problem from aircraft manufacturing, related to the assembly line balancing problem. This paper not only describes a solution, but also provides some realistic data sets!
First Impression: If you want to get an image of some area on the planet, you may have to piece pictures from multiple satellites together. You have to decide which images to select, while getting the best image quality, and not pay for some unnecessary duplication of data. So it is not about stitching the images together (which is an interesting image processing problem), but rather a type of multi-criteria set covering.The images may have different resolution, parts of the image may be covered by clouds, or the image is taken at an oblique angle so that combing it with the other images is problematic. CP to the rescue!
Optimization of Short-Term Underground Mine Planning using Constraint Programming (paper) Younes Aalian, Gilles Pesant and Michel Gamache
First impression: This paper deals with scheduling the work in an underground mine, where you have to prepare blasts by drilling long holes and filling them with explosives, then blasting the rock to make smaller pieces that you can transport, and then repeating this in a safe and efficient manner. An interesting scheduling problem in a very challenging environment, deep underground in the north of Canada.
Efficient enumeration of fixed points in complex Boolean networks using answer set programming (paper) Van-Giang Trinh, Belaid Benhamou and Sylvain Soliman
Predict-then-Optimise Strategies for Water Flow Control (paper) Vincent Barbosa Vaz, James Bailey, Chris Leckie and Peter J. Stuckey
Constraint Programming to Improve Hub Utilization in Autonomous Transfer Hub Networks (paper) Chungjae Lee, Wirattawut Boonbandansook, Vahid Eghbal Akhlaghi, Kevin Dalmeijer and Pascal Van Hentenryck
First impression: A What-if analysis of considering autonomous trucks driving between hub locations next to the highway, and human drivers picking up and delivering the loads on the last mile stretch from and to the customers. How would this affect drivers, is this a good idea for the company, and can you use CP for this type of analysis?
Exploring Hydrogen Supply/Demand Networks: Modeller and Domain Expert views (paper) Matthias Klapperstueck, Frits De Nijs, Ilankaikone Senthooran, Jack Lee-Kopij, Maria Garcia De La Banda and Michael Wybrow
First impression: This is a well-deserved best application track paper for the conference. Not only does it deal with a topic of renewable energy distribution, it brings together a team of domain expert, optimization and visualization specialists. The paper does not talk about solving a specific problem, but also considers how to deal with inconsistencies, and how to present the results in a meaningful way to the domain expert. Some beautiful pictures as well, if you like visualization!
Partitioning a Map into Homogeneous Contiguous Regions: A Branch-and-Bound approach Using Decision Diagrams (paper) Nicolas Golenvaux, Pierre Schaus, Xavier Gillard and Siegfried Nijssen
First impressions: This is an interesting and difficult variant of a clustering problem in a map. You want to cluster regions with similar properties together, but the clusters must form contiguous regions on the map. This makes it a hard problem, which is usually solved by a heuristic (still complex) approach. The proposed method uses Dynamic Programming with MDDs to find better solutions. This presentations also had nice visualizations, explaining the problem and the alternative algorithms.
Two more papers found their way into application track sessions:
Constraint Programming with External Worst-Case Traversal Time Analysis (paper) Pierre Talbot, Tingting Hu and Nicolas Navet
First impression: This paper looks at a problem of network management and service allocation, but inside a car. Modern cars have so many computing elements, that you need a lot of communications to handle the interaction of all the sensors and computers. How do you allocate services to processors so that you provide the required service levels, while leaving some rooms for further upgrades of the applications? Technically, this deals with the issue of integrating existing black box simulators into the optimization model. Very interesting.
Optimization models for pickup and delivery problems with reconfigurable capacities (paper) Arnoosh Golestanian, Giovanni Lo Bianco, Chengyu Tao and J. Christopher Beck
First impression: An interesting study looking at a very Canadian problem. In the north of the country, planes often offer the only connections between small settlements, and are used for both passenger and cargo transport. In the planes, you can take out some seats, and put them back in at a later time, in order to increase the cargo or passenger carrying capacity. The paper compares different models on how to formalize and solve these problems, solving a problem that not only affects the aircraft operators, but which provides urgently needed transport capacity in a sparsely populated part of the country.
I could not see all application papers, as in a dual track conference you are going to miss out on some papers. I hope to give more details on some of the papers in later posts. If you already want to have a look at all the papers of the conference, the complete preliminary proceedings are here: https://submission.dagstuhl.de/collections/CP-2023/preliminary-proceedings
The workshop on Teaching Constraint Programming (WTCP2023) at the CP conference in Toronto happened yesterday, Sunday August 27th.
A Jedi Knight at Breakfast in the Chelsea Hotel, Toronto
When I had breakfast at the hotel before the workshop, I noticed a Jedi Knight in the lobby (as one does). I first thought this was connected to one of our workshop papers, which describes a Star Wars theme in the excellent CP course at Georgia Tech. But no, this was just a random Jedi “going about his business”. He was surprised to learn that Jedi Knights in Atlanta were teaching Constraint Programming.
Back to the workshop: We had six submitted papers, an invited talk by Peter Stuckey from Monash University in Melbourne, an overview of the state of CP Teaching by myself, and some excellent discussion sessions on teaching topics.
The invited talk by Peter Stuckey was on the Solution Checking and Grading facilities in MiniZinc that are used in their courses at the university, as well as in the online course on Constraint Programming on Coursera. Jimmy Lee from the Chinese University in Hong Kong will give an invited talk at the main conference on this course as well. More on that later.
My overview talk https://hsimonis.github.io/WTCP2023/presentations/WTCP_2023_overview.pdf presents results from the survey on Teaching CP I mentioned in an earlier post. Many thanks to the 45 participants from 18 countries that already responded. If you haven’t filled in the survey, please do. We are still accepting more submissions.
Many thanks to my workshop co-chair, Tejas Santanam from Georgia Tech, and to the excellent preparation for the workshop at the CP site in Hart House at the University of Toronto. A shout-out to the workshop chair, Lars Kotthoff, for a simple and stress-free organization of the workshop at the conference.
Constraint Applications Blog by Helmut Simonis 