Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems

1. Front Matter

   PDF

2. Invited Talks

   1. Machine Learning Framework for Classification in Medicine and Biology

      • Eva K. Lee

      Pages 1-7

   2. G12 - Towards the Separation of Problem Modelling and Problem Solving

      • Mark Wallace

      Pages 8-10

3. Regular Papers

   1. Six Ways of Integrating Symmetries within Non-overlapping Constraints

      • Magnus Ågren, Nicolas Beldiceanu, Mats Carlsson, Mohamed Sbihi, Charlotte Truchet, Stéphane Zampelli

      Pages 11-25

   2. Throughput Constraint for Synchronous Data Flow Graphs

      • Alessio Bonfietti, Michele Lombardi, Michela Milano, Luca Benini

      Pages 26-40

   3. A Shortest Path-Based Approach to the Multileaf Collimator Sequencing Problem

      • Hadrien Cambazard, Eoin O’Mahony, Barry O’Sullivan

      Pages 41-55

   4. Backdoors to Combinatorial Optimization: Feasibility and Optimality

      • Bistra Dilkina, Carla P. Gomes, Yuri Malitsky, Ashish Sabharwal, Meinolf Sellmann

      Pages 56-70

   5. Solution Enumeration for Projected Boolean Search Problems

      • Martin Gebser, Benjamin Kaufmann, Torsten Schaub

      Pages 71-86

   6. k-Clustering Minimum Biclique Completion via a Hybrid CP and SDP Approach

      • Stefano Gualandi

      Pages 87-101

   7. Optimal Interdiction of Unreactive Markovian Evaders

      • Alexander Gutfraind, Aric Hagberg, Feng Pan

      Pages 102-116

   8. Using Model Counting to Find Optimal Distinguishing Tests

      • Stefan Heinz, Martin Sachenbacher

      Pages 117-131

   9. Reformulating Global Grammar Constraints

      • George Katsirelos, Nina Narodytska, Toby Walsh

      Pages 132-147

   10. IBM ILOG CP Optimizer for Detailed Scheduling Illustrated on Three Problems

       • Philippe Laborie

       Pages 148-162

   11. Open Constraints in a Boundable World

       • Michael J. Maher

       Pages 163-177

   12. Sequencing and Counting with the multicost-regular Constraint

       • Julien Menana, Sophie Demassey

       Pages 178-192

   13. Bandwidth-Limited Optimal Deployment of Eventually-Serializable Data Services

       • Laurent Michel, Pascal Van Hentenryck, Elaine Sonderegger, Alexander Shvartsman, Martijn Moraal

       Pages 193-207

   14. Tightening the Linear Relaxation of a Mixed Integer Nonlinear Program Using Constraint Programming

       • Sylvain Mouret, Ignacio E. Grossmann, Pierre Pestiaux

       Pages 208-222

   15. The Polytope of Context-Free Grammar Constraints

       • Gilles Pesant, Claude-Guy Quimper, Louis-Martin Rousseau, Meinolf Sellmann

       Pages 223-232

   16. Determining the Number of Games Needed to Guarantee an NHL Playoff Spot

       • Tyrel Russell, Peter van Beek

       Pages 233-247

   17. Scalable Load Balancing in Nurse to Patient Assignment Problems

       • Pierre Schaus, Pascal Van Hentenryck, Jean-Charles Régin

       Pages 248-262

This book constitutes the refereed proceedings of the 6th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2009, held in Pittsburgh, PA, USA, in May 2009. The 20 revised full papers and 10 extended abstracts presented together with 2 invited talks were carefully reviewed and selected from 65 submissions. The papers describe current research in the fields of constraint programming, artificial intelligence, and operations research and present new techniques or new applications in combinatorial optimization, thus exploring ways of solving large-scale, practical optimization problems through integration and hybridization of the fields' different techniques.

• AI
• CSP
• artificial intelligence
• automated test generation
• classification
• combinatorial optimization
• combinatorial optimization problems
• constraint programming
• cumulative constraints
• cutting planes
• embedded systems
• filtering
• operations research
• optimization
• programming
• algorithm analysis and problem complexity
• combinatorics

• Tepper School of Business, Carnegie Mellon University, Pittsburgh, USA

  Willem-Jan Hoeve

• Carnegie Mellon University, USA

  John N. Hooker

Policies and ethics