Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems: First International Conference, CPAIOR 2004, Nice, France, April 20-22, 2004. Proceedings

Christos T. Maravelias, Ignacio E. Grossmann (auth.), Jean-Charles Régin, Michel Rueher (eds.)354021836X, 9783540218364, 9783540246640

This book constitutes the refereed proceedings of the First International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2004, held in Nice, France in April 2004.

The 23 revised full papers and 7 revised short papers presented together with an invited talk were carefully reviewed and selected from 56 submissions. Methodological and foundational issues from AI, OR, and algorithmics are presented as well as applications to the solution of combinatorial optimization problems in various fields via constraint programming.

---

Table of contents :
Front Matter….Pages –
Using MILP and CP for the Scheduling of Batch Chemical Processes….Pages 1-20
SIMPL: A System for Integrating Optimization Techniques….Pages 21-36
A New Exact Solution Algorithm for the Job Shop Problem with Sequence-Dependent Setup Times….Pages 37-49
Simple Rules for Low-Knowledge Algorithm Selection….Pages 50-64
Filtering Algorithms for the Same Constraint….Pages 65-79
Cost Evaluation of Soft Global Constraints….Pages 80-95
SAT-Based Branch & Bound and Optimal Control of Hybrid Dynamical Systems….Pages 96-111
Solving the Petri Nets Reachability Problem Using the Logical Abstraction Technique and Mathematical Programming….Pages 112-126
Generating Benders Cuts for a General Class of Integer Programming Problems….Pages 127-141
A Constraint Programming Model for Tail Assignment….Pages 142-156
Super Solutions in Constraint Programming….Pages 157-172
Local Probing Applied to Network Routing….Pages 173-189
Dynamic Heaviest Paths in DAGs with Arbitrary Edge Weights….Pages 190-199
Filtering Methods for Symmetric Cardinality Constraint….Pages 200-208
Arc-Consistency Filtering Algorithms for Logical Combinations of Constraints….Pages 209-224
Combining Forces to Solve the Car Sequencing Problem….Pages 225-239
Travelling in the World of Local Searches in the Space of Partial Assignments….Pages 240-255
A Global Constraint for Nesting Problems….Pages 256-270
Models and Symmetry Breaking for ‘Peaceable Armies of Queens’….Pages 271-286
A Global Constraint for Graph Isomorphism Problems….Pages 287-301
Echelon Stock Formulation of Arborescent Distribution Systems: An Application to the Wagner-Whitin Problem….Pages 302-318
Scheduling Abstractions for Local Search….Pages 319-334
O ( nlog n ) Filtering Algorithms for Unary Resource Constraint….Pages 335-347
Problem Decomposition for Traffic Diversions….Pages 348-363
LP Relaxations of Multiple all_different Predicates….Pages 364-369
Dispatching and Conflict-Free Routing of Automated Guided Vehicles: A Hybrid Approach Combining Constraint Programming and Mixed Integer Programming….Pages 370-379
Making Choices Using Structure at the Instance Level within a Case Based Reasoning Framework….Pages 380-386
The Challenge of Generating Spatially Balanced Scientific Experiment Designs….Pages 387-394
Building Models through Formal Specification….Pages 395-401
Stabilization Issues for Constraint Programming Based Column Generation….Pages 402-408
A Hybrid Branch-And-Cut Algorithm for the One-Machine Scheduling Problem….Pages 409-415
Back Matter….Pages –