Helmut Simonis (Ed.) Integration of 1 5 4 AI and OR Techniques 8 S C in Constraint Programming N L 11th International Conference, CPAIOR 2014 Cork, Ireland, May 19–23, 2014 Proceedings 123 Lecture Notes in Computer Science 8451 CommencedPublicationin1973 FoundingandFormerSeriesEditors: GerhardGoos,JurisHartmanis,andJanvanLeeuwen EditorialBoard DavidHutchison LancasterUniversity,UK TakeoKanade CarnegieMellonUniversity,Pittsburgh,PA,USA JosefKittler UniversityofSurrey,Guildford,UK JonM.Kleinberg CornellUniversity,Ithaca,NY,USA AlfredKobsa UniversityofCalifornia,Irvine,CA,USA FriedemannMattern ETHZurich,Switzerland JohnC.Mitchell StanfordUniversity,CA,USA MoniNaor WeizmannInstituteofScience,Rehovot,Israel OscarNierstrasz UniversityofBern,Switzerland C.PanduRangan IndianInstituteofTechnology,Madras,India BernhardSteffen TUDortmundUniversity,Germany DemetriTerzopoulos UniversityofCalifornia,LosAngeles,CA,USA DougTygar UniversityofCalifornia,Berkeley,CA,USA GerhardWeikum MaxPlanckInstituteforInformatics,Saarbruecken,Germany Helmut Simonis (Ed.) Integration of AI and OR Techniques in Constraint Programming 11th International Conference, CPAIOR 2014 Cork, Ireland, May 19-23, 2014 Proceedings 1 3 VolumeEditor HelmutSimonis UniversityCollegeCork,Ireland E-mail:[email protected] ISSN0302-9743 e-ISSN1611-3349 ISBN978-3-319-07045-2 e-ISBN978-3-319-07046-9 DOI10.1007/978-3-319-07046-9 SpringerChamHeidelbergNewYorkDordrechtLondon LibraryofCongressControlNumber:2014938029 LNCSSublibrary:SL1–TheoreticalComputerScienceandGeneralIssues ©SpringerInternationalPublishingSwitzerland2014 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerptsinconnection withreviewsorscholarlyanalysisormaterialsuppliedspecificallyforthepurposeofbeingenteredand executedonacomputersystem,forexclusiveusebythepurchaserofthework.Duplicationofthispublication orpartsthereofispermittedonlyundertheprovisionsoftheCopyrightLawofthePublisher’slocation, inistcurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer.Permissionsforuse maybeobtainedthroughRightsLinkattheCopyrightClearanceCenter.Violationsareliabletoprosecution undertherespectiveCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Whiletheadviceandinformationinthisbookarebelievedtobetrueandaccurateatthedateofpublication, neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityforanyerrorsor omissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,withrespecttothe materialcontainedherein. Typesetting:Camera-readybyauthor,dataconversionbyScientificPublishingServices,Chennai,India Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) Preface This volume is a compilation of the research program of the 11th International Conference on the Integrationof Artificial Intelligence (AI) and Operations Re- search (OR) Techniques in Constraint Programming (CPAIOR 2014), held in Cork, Ireland, during May 19–23, 2014. After a successful series of five CPAIOR international workshops in Ferrara (Italy),Paderborn(Germany),Ashford(UK),LeCroisic(France),andMontreal (Canada), in 2004 CPAIOR evolved into a conference. More than 100 partici- pants attended the first meeting held in Nice (France). In the subsequent years, CPAIOR was held in Prague (Czech Republic), Cork (Ireland), Brussels (Bel- gium), Paris (France), Pittsburgh (USA), Bologna (Italy), Berlin (Germany), Nantes (France), and Yorktown Heights (USA). In 2014 CPAIOR returned to Ireland. The aim of the CPAIOR conference series is to bring together researchers from constraint programming (CP), artificial intelligence (AI), and operations research (OR) to present new techniques or applications in the intersection of these fields, as well as to provide an opportunity for researchers in one area to learn about techniques in the others. A key objective of the conference is to demonstrate how the integration of techniques from different fields can lead to highly novel and effective new methods for large and complex problems. There- fore, papers that actively combine, integrate, or contrast approaches from more than one of the areas were especially welcome. Application papers showcasing CP/AI/ORtechniques on innovativeand challengingapplications orexperience reports on such applications were also strongly encouraged. In all, 70 long and short papers were submitted to the conference. Out of these, 33 papers were selected by the international Program Committee. Their effort to provide detailed reviews and discuss all papers in depth after author feedback to come up with a strong technical program is greatly appreciated. Thetechnicalprogramoftheconferencewasprecededbyadayofworkshops andamaster-class.Theworkshopsthisyearwereselectedbytheworkshopchair, Lars Kotthoff, and covered the following topics: – WorkshoponMulti-Stage Problems,organizedby MarcoLaumanns, Steven Prestwich, and Roberto Rossi. – 5th International Workshop on Bin Packing and Placement Constraints (BPPC 2014), organized by Francois Fages and Nicolas Beldiceanu. – e-policy Workshop, organizedby Michela Milano. The master-class was organized by Siegfried Nijssen and Lars Kotthoff on the topic of Optimization and Machine Learning, providing an overview of this in- teresting area for PhD students, academics and practitioners. Puttingtogetheraconferencerequireshelpfrommanysources.Iinparticular wanttothanktheProgramCommitteeandallotherreviewers,whoworkedvery VI Preface hardinabusyperiodoftheyear.Myconferenceco-chair,BarryO’Sullivan,was instrumentalinbringingtheconferencebacktoCorkandorganizinganinterest- ingevent.ThehelpofYuriMalitsky(publicity),LarsKotthoff(workshops),and Barry Hurley (website) was greatly appreciated. Finally, the staff at UCC pro- vided outstanding administrative support, without which the conference would not have been possible. Special thanks go to Linda O’Sullivan, Mary Noonan, and Caitriona Walsh. A final acknowledgementgoes to Easychair and Springer, who allowed us to put together these proceedings. February 2014 Helmut Simonis Organization Program Committee Carlos Anso´tegui Gil Universitat de Lleida, Spain Fahiem Bacchus University of Toronto, Canada J. Christopher Beck University of Toronto, Canada Nicolas Beldiceanu EMN, France Hadrien Cambazard G-SCOP, Grenoble INP, CNRS, Joseph Fourier University, France Geoffrey Chu Melbourne University, Australia Fran¸cois Clautiaux University of Bordeaux, France Pierre Flener Uppsala University, Sweden Carla Gomes Cornell University, USA Tias Guns KU Leuven, Belgium Emmanuel Hebrard LAAS, CNRS, France Stefan Heinz Zuse Institute Berlin, Germany John Hooker Carnegie Mellon University, USA Frank Hutter Freiburg University, Germany Serdar Kadioglu Oracle, USA George Katsirelos INRA, Toulouse, France Thorsten Koch ZIB/Matheon, Germany Andrea Lodi DEI, University of Bologna, Italy Yuri Malitsky Cork Constraint Computation Centre, Ireland Laurent Michel University of Connecticut, USA Michela Milano DEIS Universit`a di Bologna, Italy Nina Narodytska University of Toronto, Canada Yehuda Naveh IBM, Israel Barry O’Sullivan 4C, University College Cork, Ireland Laurent Perron Google France Gilles Pesant Ecole Polytechnique de Montreal, Canada Thierry Petit Ecole des Mines de Nantes/LINA, France Claude-Guy Quimper Universit´e Laval, Canada Ted Ralphs Lehigh University, USA Louis-Martin Rousseau Ecole Polytechnique de Montreal, Canada Jean-Charles R´egin Universit´e Nice Sophia Antipolis, I3S CNRS, France Ashish Sabharwal IBM Research, USA Domenico Salvagnin University of Padoa, Italy Pierre Schaus n-side, Belgium Christian Schulte KTH Royal Institute of Technology, Sweden VIII Organization Meinolf Sellmann IBM Research, USA Helmut Simonis 4C, University College Cork, Ireland Michael Trick Carnegie Mellon University, USA Pascal Van Hentenryck NICTAandUniversityofMelbourne,Australia Willem-Jan Van Hoeve Carnegie Mellon University, USA Petr Vil´ım IBM, Czech Republic Mark Wallace Monash University, Australia Tallys Yunes University of Miami, USA Additional Reviewers Aharoni, Merav Hashemi Doulabi, Seyed Hossein Ben-Haim, Yael Ibrahim, Mohamed Bonfietti, Alessio Kotthoff, Lars Boni, Odellia Legrain, Antoine Borgo, Stefano Lombardi, Michele Carbonnel, Cl´ement Malapert, Arnaud Carlsson, Mats Mehta, Deepak Castan˜eda Lozano, Roberto Monaci, Michele David, Philippe Monette, Jean-No¨el de Cauwer, Milan Papadopoulos, Alexandre De Givry, Simon Penz, Bernard De Koninck, Leslie Restrepo-Ruiz, Maria-Isabel Derrien, Alban Schimpf, Joachim Fischetti, Matteo Scott, Joseph Fitzgerald, Tadhg Siala, Mohamed Fontaine, Daniel Simonin, Gilles Gabay, Micha¨el Traversi, Emiliano Grimes, Diarmuid Tubertini, Paolo Gualandi, Stefano Xue, Yexiang Hartert, Renaud Table of Contents Call-Based Dynamic Programming for the Precedence Constrained Line Traveling Salesman .......................................... 1 Thierry Benoist, Antoine Jeanjean, and Vincent Jost Stable Roommates and Constraint Programming..................... 15 Patrick Prosser Detecting and Exploiting Permutation Structures in MIPs ............ 29 Domenico Salvagnin Solving the Quorumcast Routing Problem as a Mixed Integer Program........................................................ 45 Quoc Trung Bui, Quang Dung Pham, and Yves Deville A New MIP Model for Parallel-Batch Scheduling with Non-identical Job Sizes ....................................................... 55 Sebastian Kosch and J. Christopher Beck Mining (Soft-) Skypatterns Using Dynamic CSP ..................... 71 Willy Ugarte Rojas, Patrice Boizumault, Samir Loudni, Bruno Cr´emilleux, and Albon Lepailleur Modelling with Option Types in MiniZinc........................... 88 Christopher Mears, Andreas Schutt, Peter J. Stuckey, Guido Tack, Kim Marriott, and Mark Wallace InteractiveDesignofSustainableCitieswithaDistributedLocalSearch Solver .......................................................... 104 Bruno Belin, Marc Christie, and Charlotte Truchet Sliced Table Constraints: Combining Compression and Tabular Reduction....................................................... 120 Nebras Gharbi, Fred Hemery, Christophe Lecoutre, and Olivier Roussel The PrePackOptimization Problem................................ 136 Maxim Hoskins, Renaud Masson, Gabrielle Gauthier Melan¸con, Jorge E. Mendoza, Christophe Meyer, and Louis-Martin Rousseau An IntegratedConstraintProgrammingApproachto Scheduling Sports Leagues with Divisional and Round-Robin Tournaments .............. 144 Jeffrey Larson, Mikael Johansson, and Mats Carlsson X Table of Contents Local Search for a Cargo Assembly Planning Problem ................ 159 Gleb Belov, Natashia Boland, Martin W.P. Savelsbergh, and Peter J. Stuckey A Logic Based Benders’ Approach to the Concrete Delivery Problem ... 176 Joris Kinable and Michael Trick Evaluating CP Techniques to Plan Dynamic Resource Provisioning in Distributed Stream Processing .................................. 193 Andrea Reale, Paolo Bellavista, Antonio Corradi, and Michela Milano Disregarding Duration Uncertainty in Partial Order Schedules? Yes, We Can! ........................................................ 210 Alessio Bonfietti, Michele Lombardi, and Michela Milano An Exact Branch and Bound Algorithm with Symmetry Breaking for the Maximum Balanced Induced Biclique Problem ................ 226 Ciaran McCreesh and Patrick Prosser Domain k-Wise Consistency Made as Simple as Generalized Arc Consistency ..................................................... 235 Jean-Baptiste Mairy, Yves Deville, and Christophe Lecoutre Representative Encodings to Translate Finite CSPs into SAT.......... 251 Pedro Barahona, Steffen Ho¨lldobler, and Van-Hau Nguyen SAT and Hybrid Models of the Car Sequencing Problem .............. 268 Christian Artigues, Emmanuel Hebrard, Valentin Mayer-Eichberger, Mohamed Siala, and Toby Walsh Continuously Degrading Resource and Interval Dependent Activity Durations in Nuclear Medicine Patient Scheduling.................... 284 Cyrille Dejemeppe and Yves Deville Cost Impact Guided LNS ......................................... 293 Michele Lombardi and Pierre Schaus Proteus: A Hierarchical Portfolio of Solvers and Transformations....... 301 Barry Hurley, Lars Kotthoff, Yuri Malitsky, and Barry O’Sullivan Buffered Resource Constraint: Algorithms and Complexity ............ 318 Christian Bessiere, Emmanuel Hebrard, Marc-Andr´e M´enard, Claude-Guy Quimper, and Toby Walsh Combining Discrete Ellipsoid-Based Search and Branch-and-Cut for Binary Quadratic Programming Problems........................ 334 Wen-Yang Ku and J. Christopher Beck