CP 2019

CP 2019 was held in Stamford, CT, USA during the week from 31st of September to the 4th of October 2019. This post contains some thoughts and reflections. Any selection of papers that I comment on is just what I personally found extra interesting of the presentations that I saw.

Table of contents

Workshop day, ModRef 2019

The first day I attended the workshop on Constraint Modelling and Reformulation. It started with a presentation by me on game state and polyomino placement for the game Patchwork, which I felt went well.

There was a lot of interesting presentations. Two that I want to mention are

  • Alexander Ek presented “Modelling and Solving Online Optimisation Problems” by Ek, Garcia de La Banda, Schutt, Stuckey, and Tack. It is about adding new annotations to MiniZinc to handle on-line problems. The annotations were quite intuitive, and the solving method does not require any special handling by the solver.
  • Tias Guns presented a position paper/statement regarding how to create a good environment for lowering the hurdles of integrating combinatorial modelling in a CP-style into larger systems. He argues that leveraging the common infrastructure in Python where “everything” is based on Numpy would be a good way. This is quite interesting and probably would be a good way to get non-experts to use CP. Of course, it would be a huge undertaking.

There were two good invited talks also.

  • Christian Schulte gave an update and summary on the Unison project, where code generation in the final back-end in a compiler is replaced with combinatorial optimization. This is the first such project that actually runs in practice and is used in industry.
  • Nina Narodytska talked about SAT Encodings for Binarized Neural Networks. The really cool thing about BNNs is that when translated into SAT in a sufficiently smart way, it is actually possible to verify properties about them.

First conference day

The first day of the main conference included a poster session, where I had a poster based on the abstract “Nmbr9 as a Constraint Programming Challenge”. Lots of interesting discussions about the problem and the game. It was very good to have the game with me to show how it works.

A few presentations that I found interesting:

  • Sara Frimodig gave a great presentation on scheduling of radiation therapy patients. The problem comes from the company she works at, and is clearly important. The scheduling problem has some interesting facets, and several models were presented.
  • Peter Jeavons presented a paper on fitness landscapes with studies on what the worst-case is for certain simple constraint graphs. One interesting idea is to measure fitness landscapes by the order of lengths of improving paths, where the good case is when all improving paths are polynomial in length over the landscape. Unfortunately, they could also show that very simple constructions could give exponential length paths, even when using steepest gradient.
  • John Hooker had a very interesting presentation where he combined decision diagrams, dynamic programming, and Lagrangian relaxations to derive tight bounds for some quite general problems.

There was also two award presentations. one by Peter Stuckey who got a research excellence award. His presentation on his own journey and the things he has done was very entertaining. One thing in particular was that he encouraged people to look into other areas to find problems where the lessons learned and techniques developed in CP can be applied. As a motivating example, he mentioned their work on Multi Agent Path Finding, where he, Daniel Harabour, and others had improved the state of the art with more than three orders of magnitude in just 18 months using CP-style ideas.

Edward ‘Eddie’ Lam won the doctoral thesis award, and presented very interesting work done on vehicle routing problems. I especially liked that the solution developed to solve hard problems included hybridizing MIP-solvers, CP-propagation, and SAT-solvers. He also announced a solver that he works on and which is to be released soon that implements this in a more general way, and which can be used as a MiniZinc back-end.

In the hallway-track, I heard a lot about a new lazy clause generation solver from Monash called Geas, mainly implemented by Graeme Gange with the goal of taking over as the LCG star after Chuffed with a more maintainable code-base. One cool thing is that they are planning a standardized interface for lazy clause generation propagators, so that propagator implementations can be shared between Chuffed and Geas, which sounds like a very nice approach. I hope that they find a nice design, and that they figure out a way to make it easy to add new propagators from the community.

Second conference day

The second day of the conference did not have as many papers that I personally found extra interesting. Some stand outs were

  • Siegfried Nijssen gave the presentation for the best paper, “Generic Constraint-based Block Modeling using Constraint Programming”. This is a really fun paper, which showcases where CP can really have an impact in an easy way. Taking a complicated combinatorial problem, and designing a custom propagator that does just the right amount of propagation so efficiently solve it. While various consistency-levels such as bounds(Z), bounds(D), and domain consistency are really interesting and gives us nice guarantees, it is important to remember that the goal is to solve the problem.
  • Constrain programming systems are large and complicated code bases, and yet there is not much in the way of systematically testing them. Xavier Gillard presented “SolverCheck: Declarative Testing of Constraints”, a new testing system for Java-based constraint solvers. The idea is to essentially generate oracle-propagators using generate-and-test on the variables domain Cartesian products. The work is closely related but still different from the work we’ve done in Gecode on testing. I really liked this paper, especially since I was quite involved in developing the Gecode testing infrastructure.
  • Roland Yap gave an interesting presentation on making better AC algorithms on hidden variable transformations, and getting comparable performance to GAC algorithms. This was in the context of classical CSP, so all constraints are extensional. Still, the insights were quite interesting.

Third conference day

The third day had a somewhat slow start since the conference dinner was the day before. A few interesting paper were the following.

  • Emir Demirović presented some interesting work on MaxSAT solving. This work built upon previous work that he and his co-author Peter Stuckey did using solution based phase saving, which I think is a very cool idea. One thing that I think stood out was the focus on both describing what they did that was in the final result, in addition to what they tried that was not as good. The fact that they also won a category in the MaxSAT competition was a nice validation of their results.
  • Peter Stuckey presented his and Guido Tacks work on compiling conditional constraints in MiniZinc. I really like the paper, which combines interesting modelling reformulations with practical concerns and actual measurements. One part of the translation is the arg_max constraint, which gives the index of the first maximum element. They give both a decomposition and a propagator for it. Interestingly enough, I needed the same constraint for my patchwork paper, and did a different decomposition. I’ve looked into it some, and my decomposition has more variables with fewer propagators, and seems to be slightly slower in some tests.
  • Gilles Pesant presented a cool abstract on “propagating” solution densities between constraints, extending his previous work on counting based search. For some examples, it gave an excellent guidance for search, but may be hard to do for very large scheduling domains. The construction is somewhat similar to a paper in CPAIOR 2008 by Birgit Grohe and Dag Wedelin on cost propagation.

Philippe Laborie gave an awesome tutorial which was an introduction to CP Optimizer and how it does scheduling. He focused a lot on the fact that it was designed for industrial applications with a very strong focus on finding good solutions. Some cool examples of usage were airplane construction planning, satellite observations planning, and scheduling of semiconductor wafer production. The latter was cool because the factory used CP Optimizer for scheduling, and so did some of the machines for their internal operations. I’ve been impressed with CP Optimizer and their results for a long time, and it was interesting to hear some ideas behind it. One really cool thing is that they have a deterministic algorithm, even though they use randomization, floating point variables, parallel search, restarts, MIP-guidance, learning, and much more. One thing that I was curious about and asked later on was how and if they have anything for patterns like the regular constraint, and he agreed that this was something they currently lacked.

The day concluded with the ACP general assembly. Next years CPAIOR will be in Vienna in May, and next years CP will be in early September in Louvain-La-Neuve. Most of the time of the assembly was given to a large and well-prepared discussion on the publication venue for the conference (Springer LNCS or something else) and also discussion about what to do about the Constraints journal. Some interesting points were raised on both sides. Personally, I argued that the most important thing is to ensure true open access for the conference, since this gives outsiders like me the possibility to follow the development without searching through all authors web sites or resorting to Sci-Hub.

Last conference day

Nina Narodytska gave an invited talk also in the main conference, and it was also very good. She talked about how to explain and understand the behavior of neural networks. The examples that she presented used image recognition, but later on she mentioned a case form VMWare where they might want to move different virtual machines around. Without knowing why, operations would not be keen to actually trust the system.

Of the talks, the ones that I found interesting where the following.

  • Gustav Björdal presented “Exploring Declarative Local-Search Neighborhoods with Constraint Programming”. In previous works, the authors have defined extensions to MiniZinc for describing neighborhoods for local search, and they used those in a constraint based local search solver. Their new proposal is how to implement the local search as repeated solving of standard CP models, by re-writing. Gustav gave an excellent overview and motivation for the work. I think this is quite an interesting approach, and would love to see when this can also compete with pure local search implementations, since the propagation can remove large parts of the neighborhood. One of the required building parts for the construction is a new global constraint writes.
    This spring I was present at a discussion on the writes constraint, where we discussed how to propagate it. The result of that discussion was the decomposition used in the paper with alldifferent_except_0. What I hadn’t expected was that the writes constraint would turn out to be NP-complete to propagate fully.
  • Jordi Coll presented work on compiling high level models into SAT. The cool ideas was to first generate a graph of incompatibilities, and from that extracting at most one constraints by finding clique covers. Then, for psudo Boolean constraints, these cliques of incompatible values were used to generate much smaller SAT solutions.
  • Last year Emmanuelle Hebrard and George Katsirelos published a very cool paper on graph coloring based on the observation that for any graph to be colored, two nodes that are not connected either have the same color and then they can be merged, or they have different colors and then you can add an edge between them. Gaël Glorian presented a paper on how to do graph coloring using SAT-solvers that used some of the same ideas.

Concluding remarks

It’s been six years since I’ve been at a CP conference the last time, which was 2013 in Uppsala. It was really nice to be back, and to meet and talk with a lot of the people, both old friends and new.

I learned a lot of new things this year. While I typically read through many CP papers each year, being at a conference is a different thing, especially since it is easy to grab an author and start discussing their work.

After this week, I feel quite ready to have some down-time relaxing.