Constraints (2017) 22:1–2 DOI 10.1007/s10601-016-9256-8
Introduction to the fast track issue for CP 2016 Willem-Jan van Hoeve1 · Michel Rueher2
Published online: 9 September 2016 © Springer Science+Business Media New York 2016
The conference Principles and Practice of Constraint Programming (CP) is the premier forum for research on all aspects of computing with constraints, including: theory, algorithms, environments, languages, models, systems, and applications such as decisionmaking, resource allocation, scheduling, configuration, and planning. The conference takes place annually since 1995, and is held under the auspices of the Association for Constraint Programming. Outstanding submissions to the 2016 edition of the CP conference were invited to be published exclusively through a fast-track process in the Constraints journal. Suitable papers were first identified by program committee members of the conference, among which the fast track chair (Willem-Jan van Hoeve) and the conference program chair (Michel Rueher) made the final selection. Before being accepted into Constraints, the resulting papers were subject to another round of reviewing to ensure the high standards for this journal. This issue collects the four papers that were accepted: The paper The Power of Propagation: When GAC is Enough by Cohen and Jeavons studies the power of generalized arc consistency (GAC) when applied to systems of overlapping global constraints. They identify classes of problems for which constraint propagation alone is able to decide feasibility efficiently, or not. The paper Graphical Models for Optimal Power Flow by Dvijotham, Chertkov, Van Hentenryck, Vuffray, and Misra considers the optimal power flow problem in power grids. The authors formulate this problem as an inference problem on a tree-structured graphical model. By developing an interval discretization approach, constraint programming
Willem-Jan van Hoeve
[email protected] Michel Rueher
[email protected] 1
Tepper School of Business, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15213, USA
2
CNRS, Universit´e de Nice Sophia Antipolis, I3S, 06900 Sophia Antipolis, France
2
Constraints (2017) 22:1–2
techniques (bound-tightening, constraint propagation) are utilized to make the algorithm practically efficient. The paper “Almost-stable” matchings in the Hospitals / Residents problem with Couples by Manlove, McBride, and Trimble discusses the Hospitals / Residents problem with Couples, which extends the stable matching problem with joint preference lists for specific couples. They focus on finding solutions that are ‘as stable as possible’, by minimizing the number of blocking pairs. In addition to formal computational complexity results, the authors introduce and evaluate integer programming and constraint programming models for this problem. The paper Constraint Programming for Planning Test Campaigns of Communications Satellites by Hebrard, Huguet, Veysseire, Boche-Sauvan, and Cabon describes an optimization application, in which test activities on communication satellites need to be scheduled over time, subject to various side constraints including thermal constraints. They introduce a constraint programming approach to model and solve this problem, resulting in a practically efficient tool. We thank the reviewers and the authors for their help and commitment to make this issue possible, and have all papers published on time for the conference.