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

1. Front Matter

   PDF

2. Invited Papers

   1. Integration of Rules and Optimization in Plant PowerOps

      • Thomas Bousonville, Filippo Focacci, Claude Le Pape, Wim Nuijten, Frederic Paulin, Jean-Francois Puget et al.

      Pages 1-15

   2. Embedded Systems Design: Optimization Challenges

      • Paul Pop

      Pages 16-16

   3. Models for Solving the Travelling Salesman Problem

      • H. P. Williams

      Pages 17-18

3. Technical Papers

   1. Set Variables and Local Search

      • Magnus Ågren, Pierre Flener, Justin Pearson

      Pages 19-33

   2. The Temporal Knapsack Problem and Its Solution

      • Mark Bartlett, Alan M. Frisch, Youssef Hamadi, Ian Miguel, S. Armagan Tarim, Chris Unsworth

      Pages 34-48

   3. Simplifying Diagnosis Using LSAT: A Propositional Approach to Reasoning from First Principles

      • Andreas Bauer

      Pages 49-63

   4. The tree Constraint

      • Nicolas Beldiceanu, Pierre Flener, Xavier Lorca

      Pages 64-78

   5. Filtering Algorithms for the NValue Constraint

      • Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, Zeynep Kiziltan, Toby Walsh

      Pages 79-93

   6. Identifying and Exploiting Problem Structures Using Explanation-Based Constraint Programming

      • Hadrien Cambazard, Narendra Jussien

      Pages 94-109

   7. A Hybrid Algorithm for a Class of Resource Constrained Scheduling Problems

      • Yingyi Chu, Quanshi Xia

      Pages 110-124

   8. On the Minimal Steiner Tree Subproblem and Its Application in Branch-and-Price

      • Wilhelm Cronholm, Farid Ajili, Sofia Panagiotidi

      Pages 125-139

   9. Constraint Programming Based Column Generation for Employee Timetabling

      • Sophie Demassey, Gilles Pesant, Louis-Martin Rousseau

      Pages 140-154

   10. Scheduling Social Golfers Locally

       • Iván Dotú, Pascal Van Hentenryck

       Pages 155-167

   11. Multiconsistency and Robustness with Global Constraints

       • Khaled Elbassioni, Irit Katriel

       Pages 168-182

   12. Mixed Discrete and Continuous Algorithms for Scheduling Airborne Astronomy Observations

       • Jeremy Frank, Elif Kürklü

       Pages 183-200

   13. Shorter Path Constraints for the Resource Constrained Shortest Path Problem

       • Thorsten Gellermann, Meinolf Sellmann, Robert Wright

       Pages 201-216

   14. Improving the Cooperation Between the Master Problem and the Subproblem in Constraint Programming Based Column Generation

       • Bernard Gendron, Hocine Lebbah, Gilles Pesant

       Pages 217-227

   15. Group Construction for Airline Cabin Crew: Comparing Constraint Programming with Branch and Price

       • Jesper Hansen, Tomas Lidén

       Pages 228-242

   16. A Search-Infer-and-Relax Framework for Integrating Solution Methods

       • J. N. Hooker

       Pages 243-257

The 2nd International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR2005)washeldinPrague,CzechRepublic,duringMay31–June1,2005. The conference is intended primarily as a forum to focus on the integration and hybridization of the approaches of constraint programming (CP), arti?cial intelligence (AI), and operations research (OR) technologies for solving large-scale and complex real-life optimization problems. Therefore, CPAIOR is never far from industrial applications. The high number of submissions received this year, almost 100 papers, in witness to the interest of the research community in this conference. From these submissions, we chose 26 to be published in full in the proceedings. This volume includes summaries of the invited talks of CPAIOR: one from industry, one from the embedded system research community, and one from the operations research community. The invited speakers were: Filippo Focacci from ILOGS.A.,France,oneoftheleadingcompaniesinthe?eld;PaulPop,professor in the Embedded Systems Lab in the Computer and Information Science - partment, Link¨ oping University; and Paul Williams, full professor of Operations Research at the London School of Economics. The day before CPAIOR, a Master Class was organized by Gilles Pesant, where leading researchers gave introductory and overview talks in the area of metaheuristics and constraint programming. The Master Class was intended for PhD students, researchers, and practitioners. We are very grateful to Gilles who brought this excellent program together. For conference publicity we warmly thank Willem Jan van Hoeve and Petr Vil´ ?m who did a great job with the high number of submissions received.

• AI
• CSP
• algorithmics
• algorithms
• artificial intelligence
• combinatorial optimization
• constraint programming
• constraint satisfaction problem
• integer programming
• mathematical programming
• operations research
• optimization
• programming
• proving
• sequencing

• Faculty of Mathematics and Physics, Charles University in Prague, Praha 1, Czech Republic

  Roman Barták

• DEIS, University of Bologna, Bologna, Italy

  Michela Milano

Policies and ethics