# whats_hot_at_cpaior_extended_abstract__f708a681.pdf

What s Hot at CPAIOR (Extended Abstract)

Claude-Guy Quimper Universit e Laval D epartement d informatique et de g enie logiciel claude-guy.quimper@ift.ulaval.ca

Introduction The 13th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming (CPAIOR 2016), was held in Banff, Canada, May 29 - June 1, 2016. In order to trigger exchanges between the constraint programming and the operations research community, CPAIOR was co-located with CORS 2016, the Canadian Operational Research society s conference.

Master Class The first day of CPAIOR is traditionally a master class where tutorials are given around a common topic. This year s tutorials were about decomposition methods. Jean-Franc ois Cordeau gave a talk about Classical Benders Decomposition. John Hooker gave a tutorial about Logic-based Benders Decomposition, and J. Christopher Beck presented Hybrid CP/MIP and Benders Decomposition Methods. During the discussions following these three excellent tutorials, many participants saw a parallel between no-good learning and the generation of Benders cuts. Moreover, the tutorials clearly showed how Benders decomposition can be used to hybridize constraint programming with mathematical programming Bernard Gendron gave a tutorial about Lagrangian Relaxation in MIP followed by Willem-Jan van Hoeve s tutorial on Lagrangian Relaxation in Constraint Programming. These tutorials demonstrated how Lagrangian relaxation can greatly improve the bound on the objective function that is computed by constraint solvers. Moreover, global constraint filtering algorithms can be derived from Lagrangian decomposition. Louis-Martin Rousseau concluded the master class with a tutorial on Column Generation, a decomposition method where constraint programming can be highly effective to generate parts of a solution while letting mathematical programming lead the optimization process.

Journal Fast Track For a second time at CPAIOR, the call for paper mentioned a Journal fast track where the best papers would be directly

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

submitted to the Constraint Journal while still be presented at the conference. The authors were invited to add novel material to their paper and submit it for a second round of review. This process led to the selection of four papers. In Breaking Symmetries in Graph Search with Canonizing Sets, (Itzhakov and Codish 2016) present a technique that breaks symmetries when the solution of a problem is expressed as a graph. Such problems contain as many solutions as there are isomorphisms. A solver that eliminates a candidate solution can therefore eliminate all isomorphic candidate solutions. The paper shows how to efficiently do it. In Computing the Ramsey Number R(4,3,3) using Abstraction and Symmetry breaking, (Codish et al. 2016) solve an open problem, computing the Ramsey Number R(4, 3, 3), a number related to the graph colouring problem. Their solution is based on abstraction and symmetry breaking. In A Branch-and-Price-and-Check Model for the Vehicle Routing Problem with Location Resource Constraints, (Lam and Van Hentenryck 2016) solve a routing problem with pickup and delivery, time windows, and location resource constraints. They decompose the problems using a branch-and-price-and-check algorithm, i.e. a branch-andprice solves a vehicle routing problem and a constraint solver checks for the feasibility of the location resource. In Multi-Language Evaluation of Exact Solvers in Graphical Model Discrete Optimization, (Hurley et al. 2016) consider optimization languages able to encode NP-Hard problems such as Cost Function Networks, Markov Random Fields, Weighted Partial Max-SAT, 0-1 Linear Programming, and Constraint Programming. They explain how problems expressed in one language can be translated into another formalism. It follows an extensive comparison of exact solvers and the creation of a portfolio able to exploit the complementarity between the solvers.

Technical Program

Decomposition Methods

In the technical program, decomposition methods were a popular topic with 5 publications. In addition to the work of (Lam and Van Hentenryck 2016) cited above, (Booth, Tran, and Beck 2016) also solve a routing problem but this time by using logic-based decomposition. The problem

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

studied is the Traveling Purchaser Problem where different markets offer a limited quantity of products at a given price. The goal is to visit a subset of the markets such that the demand for each product is satisfied while minimizing the purchase cost and the traveling cost. As a third application of a decomposition method, (Heching and Hooker 2016) solves a scheduling home hospice care problem with logic-based Benders decomposition. Two new decomposition techniques were introduced to improve the performance of constraint solvers. (Chu, Stuckey, and Gange 2016) use a constraint solver to solve sub-problems and then use a Lagrangian decomposition to compute a better bound on the objective function. (Bergman and Cire 2016) decompose a problem into decision diagrams that can be efficiently handled.

Decision Diagrams

Decision Diagrams were not only used as a decomposition technique. (Ab ıo et al. 2016) study existing encodings of Binary Decision Diagrams into CNF clauses and present new encodings. They compare these encodings and study their properties such as the level of filtering obtained by applying unit propagation. (Perez and R egin 2016) improve the manipulation of Multi-Valued Decision Diagrams (MDD) by proposing a new algorithm that builds a MDD from a list of tuples. They also propose new in-place algorithms that insert or delete tuples from an existing MDD. Finally, they show how to efficiently reduce the size of a MDD.

Global Constraints

Global constraints remain a popular topic with 5 publications. New global constraints are introduced in the field of data mining. (Kemmar et al. 2016) introduce the GAP-SEQ constraint that allows to do sequential pattern mining with (or without) gap constraints. The solution set of many global constraints can be recognized by an automaton, sometimes with accumulators. (Arafailova et al. 2016) show how to synthesis such an automaton with as few accumulators as possible and automatically translate the constraint into linear inequalities. Two constraints were introduced to better encode scheduling problems. (Kinable 2016) introduces a reservoir constraint that models a resource that can be produced and consumed by tasks. Consuming tasks must wait for the resource to be available before executing. Producing tasks can regenerate the resource up to a certain limit and then need to wait for the resource to be consumed before generating further the resource. This work won the ACP Summer School competition on Constraint Programming. (Wamba and Beldiceanu 2016) introduce the TASKINTERSECTION constraint that takes as input a sequence of n tasks that needs to be scheduled in a given order and a sequence or n intervals. The constraint fixes an upper bound (or a lower bound) on the amount of intersection between the execution windows of the tasks and the intervals. Matching objects is an important component of many combinatorial problems. When there are preferences, one aims at finding a stable matching. (Siala and O Sullivan

2016) shows how to enforce bounds consistency and domain consistency on two-sided stability constraints. The use of no-goods within constraint solvers gain in popularity and global constraints need to be adapted to generate explanations. (de U na et al. 2016) present an algorithm that produces explanations for the Weighted Spanning Tree constraint.

Conclusion CPAIOR 2016 was a success with its first co-location with CORS. Over thirty papers were presented on topics as diverse as graph theory, decomposition methods, decision diagrams, and global constraints.

References Ab ıo, I.; Gange, G.; Mayer-Eichberger, V.; and Stuckey, P. J. 2016. On cnf encodings for decision diagrams. In Proceedings of the 13th International Conference on Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2016), 1 17. Arafailova, E.; Beldiceanu, N.; Douence, R.; Flener, P.; Rodriguez, M. A. F.; Pearson, J.; and Simonis, H. 2016. Timeseries constraints: Improvements and application in cp and mip contexts. In Proceedings of the 13th International Conference on Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2016), 18 34. Bergman, D., and Cire, A. 2016. Decompositions based on decision diagrams. In Proceedings of the 13th International Conference on Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2016), 45 54. Booth, K. E.; Tran, T. T.; and Beck, J. C. 2016. Logicbased decomposition methods for the travelling purchaser problem. In Proceedings of the 13th International Conference on Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2016), 55 64. Chu, G.; Stuckey, P. J.; and Gange, G. 2016. Lagrangian decomposition via subproblem search. In Proceedings of the 13th International Conference on Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2016), 187 197. Codish, M.; Frank, M.; Itzhakov, A.; and Miller, A. 2016. Computing the ramsey number R(4,3,3) using abstraction and symmetry breaking. Constraints 21(3):375 393. de U na, D.; Gange, G.; Schachte, P.; and Stuckey , P. J. 2016. Weighted spanning tree constraint with explanations. In Proceedings of the 13th International Conference on Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2016), 98 107. Heching, A., and Hooker, J. 2016. Scheduling home hospice care with logic-based benders decomposition. In Proceedings of the 13th International Conference on Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2016), 187 197. Hurley, B.; OSullivan, B.; Allouche, D.; Katsirelos, G.; Schiex, T.; Zytnicki, M.; and de Givry, S. 2016. Multilanguage evaluation of exact solvers in graphical model discrete optimization. Constraints 21(3):413 434.

Itzhakov, A., and Codish, M. 2016. Breaking symmetries in graph search with canonizing sets. Constraints 21(3):357 374. Kemmar, A.; Loudni, S.; Yahia, L.; Boizumault, P.; and Charnois, T. 2016. A global constraint for mining sequential patterns with gap constraint. In Proceedings of the 13th International Conference on Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2016), 198 215. Kinable, J. 2016. A reservoir balancing constraint with applications to bike-sharing. In Proceedings of the 13th International Conference on Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2016), 216 228. Lam, E., and Van Hentenryck, P. 2016. A branch-and-priceand-check model for the vehicle routing problem with location congestion. Constraints 21(3):394 412. Perez, G., and R egin, J.-C. 2016. Constructions and in-place operations for mdds based constraints. In Proceedings of the 13th International Conference on Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2016), 279 293. Siala, M., and O Sullivan, B. 2016. Revisiting two-sided stability constraints. In Proceedings of the 13th International Conference on Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2016), 342 357. Wamba, G. M., and Beldiceanu, N. 2016. The taskintersection constraint. In Proceedings of the 13th International Conference on Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2016), 246 261.