Application track papers at CP 2023

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!

Constraint Model for the Satellite Image Mosaic Selection Problem (paper)
Manuel Combarro Simon, Pierre Talbot, Grégoire Danoy, Jedrzej Musial, Mohammed Alswaitti and Pascal Bouvry

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