# whats_hot_in_constraint_programming__6bdf5c9b.pdf

What s Hot in Constraint Programming

Laurent Michel CSE Department, University of Connecticut 371 Fairfield Road, Storrs, CT 06269-4155, USA ldm@engr.uconn.edu

Michel Rueher University of Nice Sophia Antipolis / CNRS BP 121, 06903 Sophia Antipolis Cedex, France michel.rueher@gmail.com

The CP conference is the annual international conference on constraint programming. It is concerned with all aspects of computing with constraints, including theory, algorithms, environments, languages, models, systems, and applications such as decision-making, resource allocation, scheduling, configuration, and planning. The CP community is very keen to ensure it remains open to interdisciplinary research at the intersection between constraint programming and related fields. Hence, in addition to the usual technical and application tracks, the CP 2016 conference featured thematic tracks: Computational Sustainability , CP and Biology , Preferences, Social Choice and Optimization , and Testing and Verification . In this overview, we highlight several remarkable papers that have been selected by the senior program committee and papers with the most innovative methods and techniques, and a very high potential for applications (in our opinion).

The conference bestowed best paper awards on Krishnamurthy Dvijotham, Pascal Van Hentenryck, Michael Chertkov, Sidhant Misra and Marc Vuffray for Graphical models for optimal power flow and on David Manlove, Iain Mc Bride and James Trimble for Almost-stable matchings in the Hospitals / Residents problem with Couples .

Graphical models for optimal power flow. In (Dvijotham et al. 2016), the authors consider the problem of reliably operating a power grid in a context where the number of stochastic demand-side resources becomes significant. In particular, it considers the smart management of those demand-side resources through the resolution of a distributed optimization formulation of the optimal power flow problem over tree networks. Unlike previous algorithms that rely on convex relaxations, this novel approach works for arbitrary distribution networks and can handle mixed-integer optimization problems. The paper not only offers the initial steps towards solving the problem, but it also delivers an empirical evaluation demonstrating that the problem can be solved efficiently. The technical approach articulates a

Copyright c 2017, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

dynamic programming formulation which, while being intractable, serves as inspiration for a CP technique relying on interval discretizations that adaptively tighten the variable bounds as the DP algorithm proceeds. The final result is an algorithm that delivers ϵ-feasible super-optimal approximate solution to the optimal power flow in time linear in the network size and polynomial in 1

Almost-stable matchings in the Hospitals / Residents problem with Couples. In (Manlove, Mc Bride, and Trimble 2016), the authors investigate a practical variant of the Hospital/Resident almost-stable matching problem in which couples of residents are allowed to submit joint preferences over pairs of (typically close) hospitals. As expected, the objective is to find an allocation that is as stable as possible. Namely, the number of blocking pairs among participants, or couples of Hospitals / Residents is minimal. The paper establishes that the optimization problem is NP-hard and hard to approximate. It introduces an Integer Programming and a Constraint Programming model and empirically investigates their behavior on randomly generated instances. Interestingly, the CP model augmented with presolving techniques delivers optimal solutions almost an order of magnitude faster than the IP model.

Student Paper Awards. The conference also awarded a Best Student Paper Prize to Cl ement Carbonnel for The Dichotomy for Conservative Constraint Satisfaction is Polynomially Decidable (Carbonnel 2016), and a Distinguished Student Paper Prize to Kyle E. C. Booth, Goldie Nejat and J. Christopher Beck for A Constraint Programming Approach to Multi-Robot Task Allocation and Scheduling in Retirement Homes (Booth, Nejat, and Beck 2016).

The Dichotomy for Conservative Constraint Satisfaction is Polynomially Decidable. Given a fixed constraint language Γ, the conservative CSP over Γ (denoted by c-CSP(Γ)) is a variant of CSP(Γ) where the domain of each variable can be restricted arbitrarily. This paper (Carbonnel 2016), introduces a polynomial-time algorithm that, given a constraint language Γ as input, decides if c-CSP(Γ) is tractable. In addition, if Γ is proven tractable the algorithm also outputs its coloured graph, which contains valuable information on the structure of Γ.

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)

A Constraint Programming Approach to Multi-Robot Task Allocation and Scheduling in Retirement Home. In (Booth, Nejat, and Beck 2016) the authors investigate the application of constraint programming to the planning and scheduling of multiple social robots interacting with residents in a retirement home. The robots autonomously organize and facilitate group and individual activities among residents. This problem involves reasoning about disjoint time windows, inter-schedule task dependencies, user and robot travel times, as well as robot energy levels. Experiments indicate substantial superiority of the initial CP approach over MIP, and subsequent significant improvements in the CP approach through model manipulations. This work demonstrate the promise of CP scheduling technology as a general optimization infrastructure for such problems.

Track Highlights

The track model adopted by CP 16 was meant to offer opportunities to authors to submit papers in novel and diverse application domains or technical areas that contribute to Constraint Programming, present novel challenges or close challenging problems using CP technology. Several noteworthy papers are highlighted below.

Constraint Programming Models for Chosen Key Differential Cryptanalysis. This paper (Gerault, Minier, and Solnon 2016) introduces Constraint Programming (CP) models to solve a cryptanalytic problem: the chosen key differential attack against the standard block cipher AES. The problem is solved in two steps. First, bytes are abstracted by binary values. Second, byte values are searched. The first step is approached with two increasingly complex models. The initial model is derived from AES rules in a straightforward way while the second model contains new constraints that remove invalid solutions. Step 2 also relies on a CP model and evaluates scale-up properties of two classical CP solvers (Gecode and Choco) as well as a hybrid SAT/CP solver (Chuffed). The paper demonstrates that the second model is far more efficient than the first and that Chuffed outperforms both Choco and Gecode on the hardest instances. Furthermore, the paper proves that a solution claimed to be optimal in two recent cryptanalysis papers is not optimal by producing a better solution.

Four-Bar Linkage Synthesis Using Non-Convex Optimization. This paper (Goulet et al. 2016) shows how fourbar linkages can be designed using non-convex optimization techniques. The generative design software takes as input a curve that needs to be reproduced by a four-bar linkage and outputs the best assembly that approximates this curve. The problem model relies on quadratic constraints and shows the importance of redundant constraints. It also provide an algorithm that samples the curve based on its characteristics (e.g., curvature). Experiments show that the software is faster and more precise than existing systems. The current work is part of a larger generative design initiative at Autodesk Research.

Multiobjective Optimization by Decision Diagrams. The paper (Bergman and Cir e 2016) presents a technique for solving multiobjective discrete optimization problems using decision diagrams. The proposed methodology is related to an algorithm designed for multiobjective optimization for dynamic programming, except utilizing decision diagram theory to reduce the state space. This can lead to orders of magnitude performance gains over existing algorithms. The decision diagram-based technique is applied to knapsack, set covering, and set partitioning problems, exhibiting improvements over state-of-the-art general-purpose multiobjective optimization algorithms.

Music. The papers of this track have a remarkable diversity both in the musical topics and the constraint techniques applied to them. In (Hooker 2016), the author asks a very original question: is it possible to find new music scales ? Not only does he answer yes (and provide some, from a CP model), but he even composes a musical piece to show the harmonic potential of those new scales. In (Tanaka, Bemman, and Meredith 2016), CP is used to solve a very difficult combinatorial problem, all partition arrays, stated by the composer Milton Babbit. At a different level, (Papadopoulos, Roy, and Pachet 2016) uses optimization techniques for automated composition in a given style. Finally, (Roy et al. 2016) explores the Allen constraint, which can express time relations.

Testing and Verification. The related track and Workshop attracted excellent papers that show the vitality of the subject and its importance for the CP community. In (Sun et al. 2016) the authors renewed interest in Gr obner basis for formal verification pays off with a novel technique to find unsatisfiable cores in a set of polynomials. Another paper (Aharoni et al. 2016) aimed at attacking the hardware address translation problem in microprocessor memory management by using conditional CSP solving. The generation of test cases for software or hardware systems remains one of the most prominent application area of the constraintbased testing and verification area. Combining CP filtering and search method with classical method dedicated to program testing and verification is probably one of its most promising directions.

Journal Fast Track

The CP conference series now provides a Journal Fast Track for particularly strong, well-articulated contributions that are eligible for direct publication in the Constraint Journal. The Program Chair, the Journal Publication Fast Track Chair, and the Constraints journal editor-in-chief, invited four papers from the CP 16 technical and application tracks to the Journal Fast Track :

The two best papers (Dvijotham et al. 2016; Manlove, Mc Bride, and Trimble 2016)

The Power of Propagation: When GAC is Enough (Cohen and Jeavons 2016), and Constraint Programming for

Planning Test Campaigns of Telecommunication Satellites (Hebrard et al. 2016). These were presented at the conference like any other paper and received a one-page abstract in the proceedings.

References Aharoni, M.; Ben-Haim, Y.; Doron, S.; Koyfman, A.; Tsanko, E.; and Veksler, M. 2016. Using graph-based CSP to solve the address translation problem. In Rueher (2016), 843 858. Bergman, D., and Cir e, A. A. 2016. Multiobjective optimization by decision diagrams. In Rueher (2016), 86 95. Booth, K. E. C.; Nejat, G.; and Beck, J. C. 2016. A constraint programming approach to multi-robot task allocation and scheduling in retirement homes. In Rueher (2016), 539 555. Carbonnel, C. 2016. The dichotomy for conservative constraint satisfaction is polynomially decidable. In Rueher (2016), 130 146. Cohen, D. A., and Jeavons, P. G. 2016. The power of propagation: when gac is enough. Constraints 1 21. Dvijotham, K.; Chertkov, M.; Van Hentenryck, P.; Vuffray, M.; and Misra, S. 2016. Graphical models for optimal power flow. Constraints 1 26. Gerault, D.; Minier, M.; and Solnon, C. 2016. Constraint programming models for chosen key differential cryptanalysis. In Rueher (2016), 584 601. Goulet, V.; Li, W.; Cheong, H.; Iorio, F.; and Quimper, C. 2016. Four-bar linkage synthesis using non-convex optimization. In Rueher (2016), 618 635. Hebrard, E.; Huguet, M.-J.; Veysseire, D.; Sauvan, L. B.; and Cabon, B. 2016. Constraint programming for planning test campaigns of communications satellites. Constraints 1 17. Hooker, J. N. 2016. Finding alternative musical scales. In Rueher (2016), 753 768. Manlove, D. F.; Mc Bride, I.; and Trimble, J. 2016. almoststable matchings in the hospitals / residents problem with couples. Constraints 1 23. Papadopoulos, A.; Roy, P.; and Pachet, F. 2016. Assisted lead sheet composition using flowcomposer. In Rueher (2016), 769 785. Roy, P.; Perez, G.; R egin, J.; Papadopoulos, A.; Pachet, F.; and Marchini, M. 2016. Enforcing structure on temporal sequences: The allen constraint. In Rueher (2016), 786 801. Rueher, M., ed. 2016. Principles and Practice of Constraint Programming - 22nd International Conference, CP 2016, Toulouse, France, September 5-9, 2016, Proceedings, volume 9892 of Lecture Notes in Computer Science. Springer. Sun, X.; Ilioaea, I.; Kalla, P.; and Enescu, F. 2016. Finding unsatisfiable cores of a set of polynomials using the gr obner basis algorithm. In Rueher (2016), 859 875. Tanaka, T.; Bemman, B.; and Meredith, D. 2016. Constraint programming approach to the problem of generating milton babbitt s all-partition arrays. In Rueher (2016), 802 810.