The Doctoral Program of CP 2021

The Doctoral Program (DP) of CP 2021 is open to all students doing research in constraint programming or related areas, including participants of past DPs. The aim is to gather early-career (student) researchers in order to discuss ongoing research in a relaxed atmosphere. Additionally the DP aims to provide opportunities for students to interact with more experienced researchers.

The DP will be a full day event on the 25th of October, the workshop day of the conference. The program of the DP will consists of a discussion of the reviews submited by the participants, two sessions for the participants to present their own work, and a panel discussion on presenting work with more senior researchers. The program will conclude with a social session and online games.

Any questions on the program can be directed toward the chair of the DP, Jeremias.

Proceedings

The proceedings of the DP can be found at Google Drive.
Note: These are not formal proceedings. The work presented in these submissions can be freely used for later conferences or journals publications.

Presentations

The video presentations from each submission, and the panel discussion on presenting work can now be found on youtube. Thank you to everyone who contributed to the program, especially the four panelists.

Prior to the Program

Before October 25 the participants of the DP are expected to prepare a camera-ready version of their submission (at the latest by September 17th), record a video presentation and fill out a form with preliminary questions (at the latest by September 30).

The camera-ready version is expected to follow the same standards as for the main conference i.e. following these directions with the following two exceptions:

  • Please submit only the PDF of the final version directly to Jeremias.
  • Please add the following to the "%Editor-only macros" of the .tex file:
    \EventEditors{Jeremias Berg}
    \EventNoEds{1}
    \EventLongTitle{The doctoral program of CP 2021}
    \EventShortTitle{CP-DP 2021}
    \EventAcronym{CP-DP}
    \EventYear{2021}
    \EventDate{October 25, 2021}
    \EventLocation{Montpellier, France (Virtual Conference)}
    \EventLogo{}
    \SeriesVolume{1}
    \ArticleNo{ [YOUR-SUBMISSION-NUMBER] }

Papers accepted to the doctoral program will be made available online, but are not published in formal printed proceedings. They may therefore be reused or extended for other conferences in the future.

The video presentation should be at most 10 minutes long. More directions on submitting the video will be sent to the authors of the accepted papers.

The form with preliminary questions is meant to help with the planning of the program. In addition to providing the participants with an opportunity to suggest games to play in the evening, participants can also use the form to ask questions of the panel and give permision to the panel to discuss the video presentation that they submitted. Note that only giving permision does not guarantee that we will discuss your presentation in the panel discussion, the aim of the panel is to provide useful information to as many of the participants as possible. However, not giving permission guarantees that we will not.

Summary of Important Dates

All deadlines and dates are intended as anywhere on Earth
  • August 22 - Deadline for reviews
  • August 31 - Notification
  • September 17 - Camera-ready version for online proceedings.
  • September 30 - Deadline for upploading videos of the talks and filling out the form with preliminary questions.
  • October 25 - The Doctoral Program

Schedule of the DP

The schedule of the program is now online and can be found on the conference schedule page.

Panel Discussion -
Presenting your Work

During the DP we will have a panel discussion on presenting your work at conferences and other scientific venues. The panelists are all well established researchers in the field of constraint programming - and as such could be expected to sit in the audience of a scientific presentation given by the participants of the DP.

The aim of the panel is to provide the perticipants of the DP with different views and opinions on what makes a good and remembrable presentation. In addition to discussing the panelists own experiences, we will also answer any questions from the audience and even talk about some of the video presentations submitted to the DP.

A permision for the panel to discuss your video can be given by filling out this form (which should be filled by all participants of the DP by September 30th).The same form can also be used to pre-submit questions for the panelists.

Panelists

  • Christine Solnon
    • Professor at INSA de Lyon
  • Tias Guns
    • Associate Professor at the KU Leuven
  • Susanna de Rezende
    • Postdoctoral Researcher at the Institute of Mathematics of the Czech Academy of Sciences, Prague
  • Christopher Jefferson
    • Royal Society Research Fellow and Reader at the School of Computer Science at the University of St. Andrews

Abstracts of the Submissions

Session 1:

Learning to Choose SAT Encodings for Pseudo-Boolean and Integer Sum Constraints
Felix Ulrich-Oltean, Peter Nightingale and James Alfred Walker.
Abstract: Many constraint satisfaction and optimisation problems can be solved effectively by encoding them as instances of the Boolean Satisfiability problem (SAT). However, even the simplest types of constraints have many encodings in the literature with widely varying performance, and the problem of selecting suitable encodings for a given problem instance is not trivial. We explore the problem of selecting encodings for pseudo-Boolean and integer sum constraints using a supervised machine learning approach. We show that it is possible to select encodings effectively using a standard set of features for constraint problems, however we obtain better performance with a new set of features specifically designed for the pseudo-Boolean and integer sum constraints.

Massively Parallel SAT: Revisiting 3-SAT
Filippos Pantekis and Phillip James.
Abstract: Parallel SAT has been explored many times by many researchers. Often, the main challenge encountered in search space splitting solvers is to deal with the sharing of information between threads of the solver. In this work, we present a parallel SAT algorithm for 3-SAT that does not rely on any sharing of information between threads, but instead runs a massively parallel number of naïve threads each working on checking a small number of assignments each. This is made possible thanks to recent advances in General Purpose Graphics Processing Units (GPGPUs) and a highly optimised implementation of a fairly simple algorithm.

Boosting incomplete search with conflict learning
Trong-Hieu Tran, Cédric Pralet and Hélène Fargier.
Abstract: In this paper, we introduce an ongoing work regarding a hybrid approach usable for obtaining high quality solutions to large-scale combinatorial optimization problems. This approach divides the process of solving a global problem into a master process that performs constraint-based search and a slave process that uses specific incomplete search techniques. In this hybrid architecture, the master level takes advantage of the conflicts discovered during incomplete search at the slave level, and reciprocally enhances the efficiency of the incomplete search since conflicts collected by the master level are used to avoid visiting the same parts of the search space over and over again. One of the novelties of this work is that the conflicts are memorized over the long-term in compact data structures, namely OBDDs or MDDs. The experimental results obtained on OPTW and FJSP instances show that even in our preliminary implementation, this kind of approach can reach some best-known results.

Solution sampling with random table constraints
Mathieu Vavrille, Charlotte Truchet and Charles Prud'Homme.
Abstract: Constraint programming provides generic techniques to efficiently solve combinatorial problems. In this paper, we tackle the natural question of using constraint solvers to sample combinatorial problems in a generic way. We propose an algorithm, inspired from Meel’s ApproxMC algorithm on SAT, to add hashing constraints to a CP model in order to split the search space into small cells of solutions. By sampling the solutions in the restricted search space, we can randomly generate solutions without revamping the model of the problem. We ensure the randomness by introducing a new family of hashing constraints: randomly generated tables. We implemented this solving method using the constraint solver Choco-solver. The quality of the randomness and the running time of our approach are experimentally compared to a random branching strategy. We show that our approach improves the randomness while being in the same order of magnitude in terms of running time.

Session 2:

Efficient low rank convex bounds for pairwise discrete Graphical Models
Valentin Durante, Thomas Schiex and George Katsirelos.
Abstract: By concisely representing a joint function of many variables as the combination of small functions, discrete graphical models (GMs) provide a powerful framework to analyze systems of interacting variables. One of the main queries on such models is to identify the extremum of this joint function. On Cost Function Networks, this is known as the Weighted Constraint Satisfaction Problem (WCSP).
Algorithms for approximate GM optimization typically rely on belief propagation or local consistency algorithms. The latter are related to linear programming (LP) relaxations and often coupled with “equivalence preserving transformations” that provide fast incremental bounds for Branch and Bound algorithms. Since the seminal work of Goemans and Williamson, it is known that convex SDP relaxations can provide superior guarantees than LP. But the computational cost of interior point methods has limited their application. The situation has improved with the introduction of the Burer-Monteiro style methods which are well suited to handle the SDP relaxations of combinatorial problems with binary variables (such as MAXCUT). In this paper, we compute low rank SDP bounds for the WCSP by extending a Burer-Monteiro style method. We consider a dualized constraint approach or a dedicated Block Coordinate Descent approach which hides the normalizing constraints associated with non binary variables. On dense WCSP instances, we observe that the BCD approach outperforms the dualized and linear approaches.

Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming
Fulya Trösser, Simon de Givry and George Katsirelos.
Abstract: Bayesian networks are probabilistic graphical models with a wide range of application areas including gene regulatory networks inference, risk analysis and image processing. Learning the structure of a Bayesian network (BNSL) from discrete data is known to be an NP-hard task with an exponential search space of directed acyclic graphs. In this work, we propose a new polynomial time algorithm for discovering a subset of all possible cluster cuts and a greedy algorithm for approximately solving the resulting linear program. We embed these in the constraint programming-based branch-and-bound solver CPBayes and show that, despite being suboptimal, they improve performance by orders of magnitude. The resulting solver also compares favourably with GOBNILP, a state-of-the-art solver for the BNSL problem which solves an NP-hard problem to discover each cut and solves the linear program exactly.

Combining Directional Arc Consistency with Asynchronous Forward Bounding algorithm
Rachid Adrdor and Lahcen Koutti.
Abstract: The AFB_BJ+-AC∗ algorithm is one of the latest algorithms used to solve Distributed Constraint Optimization Problems (DCOPs). It is based on simple arc consistency (AC∗) to speed up the process of solving a problem by permanently removing any value that doesn’t belong to its optimal solution. In this paper, we use a directional arc consistency (DAC∗), the next higher level of AC∗, to erase more values and thus reach the optimal solution of a problem with minimal search attempts. Experiments on some benchmarks show that the new algorithm, AFB_BJ+-DAC∗, reduces the communication load by 25% on average and requires 15% less computational effort.

Multiple-choice knapsack constraint in CFN
Pierre Montalbano, Simon de Givry and George Katsirelos.
Abstract: Cost function networks (CFNs), also known as Weighted Constraint Satisfaction Problems, can compactly express large decomposable cost functions, which leads to efficient inference algorithms. In particular, most methods for computing dual (lower) bounds in minimization compute feasible dual solutions of a specific linear relaxation. These methods are more effective than solving the linear relaxation exactly, because its size is significantly larger than the original CFN. However, these algorithms are specialized to the structure of the linear relaxation of a CFN and cannot, for example, deal with constraints for which the corresponding cost function has an exponential size, such as linear constraints of large arity.
In this work, we show how to extend soft local consistencies, a set of approximate inference techniques for CFNs, so that they handle linear constraints, as well as combinations of linear constraints with at-most-one constraints. We embedded the resulting algorithm in toulbar2, an exact Branch-and-Bound solver for CFNs which primarily relies dual bounds during search. This allows us to test this solver on problems on which it was previously not applicable, such as pseudo-Boolean optimization (PB) and knapsack with conflict graph (KPCG). Compared to dedicated PB solvers and integer linear programming solvers, we demonstrate state-of-the-art performance on some families from recent PB optimization evaluations and KPCG, and improve performance in computational protein design with diversity guarantees.

Opening the Black Box: Automated Software Analysis for Algorithm Selection
Damir Pulatov, Marie Anastacio, Lars Kotthoff and Holger Hoos.
Abstract: Impressive performance improvements have been achieved in many areas of AI by meta-algorithmic techniques, such as automated algorithm selection and configuration. However, existing techniques treat the target algorithms they are applied to as black boxes – nothing is known about their inner workings. This allows meta-algorithmic techniques to be used broadly, but leaves untapped potential performance improvements enabled by information gained from a deeper analysis of the target algorithms. In this paper, we open the black box without sacrificing universal applicability of meta-algorithmic techniques by automatically analyzing algorithms. We show how to use this information to perform algorithm selection, and demonstrate improved performance compared to previous approaches that treat algorithms as black boxes.

Contact & Acknowledgements

Any further questions of the DP or the submission procedure can be directed at the chair of the doctoral program:

The organizer of the Doctoral Program would like to thank all of the panelists for their time as well as all of the people who voulenteered to be a part of the program committee:

  • John Hooker, Carnegie Mellon University
  • Blair Archibald, University of Glasgow
  • Gauthier Picard, ONERA
  • Lars Kotthoff, University of Wyoming
  • Maria Garcia De La Banda, Monash University
  • Armin Biere, Johannes Kepler University Linz
  • Christian Bessiere, CNRS, University of Montpellier
  • Andreas Niskanen, University of Helsinki
  • Daniel Harabor, Monash University
  • Emir Demirović, Delft University of Technology
  • Christophe Lecoutre, CRIL, Univ. Artois
  • Claude-Guy Quimper, Laval University
  • David Cohen, Royal Holloway, University of London
  • Justin Pearson, Uppsala University
  • Jimmy Lee, The Chinese University of Hong Kong
  • Christine Solnon, INSA Lyon
  • Graeme Gange, Monash University
  • Jakob Nordstrom, University of Copenhagen and Lund University
  • Ilankaikone Senthooran, Monash University
  • Laura Climent
  • Roberto Amadini, University of Bologna
  • Peter J. Stuckey, Monash University
  • Kevin Leo, Monash University
  • Tias Guns, Vrije Universiteit Brussel (VUB)