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

1. Front Matter

   PDF

2. Preference Elicitation and Preference Learning in Social Choice

   • Craig Boutilier

   Pages 1-1

3. Propagation in Constraints: How One Thing Leads to Another

   • Ian P. Gent

   Pages 2-2

4. On Bilevel Programming and Its Impact in Branching, Cutting and Complexity

   • Andrea Lodi

   Pages 3-3

5. Optimization Methods for the Partner Units Problem

   • Markus Aschinger, Conrad Drescher, Gerhard Friedrich, Georg Gottlob, Peter Jeavons, Anna Ryabokon et al.

   Pages 4-19

6. Manipulating MDD Relaxations for Combinatorial Optimization

   • David Bergman, Willem-Jan van Hoeve, John N. Hooker

   Pages 20-35

7. The AllDifferent Constraint with Precedences

   • Christian Bessiere, Nina Narodytska, Claude-Guy Quimper, Toby Walsh

   Pages 36-52

8. Retail Store Workforce Scheduling by Expected Operating Income Maximization

   • Nicolas Chapados, Marc Joliveau, Louis-Martin Rousseau

   Pages 53-58

9. Spatial and Objective Decompositions for Very Large SCAPs

   • Carleton Coffrin, Pascal Van Hentenryck, Russell Bent

   Pages 59-75

10. Upgrading Shortest Paths in Networks

    • Bistra Dilkina, Katherine J. Lai, Carla P. Gomes

    Pages 76-91

11. Parallel Machine Scheduling with Additional Resources: A Lagrangian-Based Constraint Programming Approach

    • Emrah B. Edis, Ceyda Oguz

    Pages 92-98

12. Branch-Cut-and-Propagate for the Maximum k-Colorable Subgraph Problem with Symmetry

    • Tim Januschowski, Marc E. Pfetsch

    Pages 99-116

13. Climbing Depth-Bounded Adjacent Discrepancy Search for Solving Hybrid Flow Shop Scheduling Problems with Multiprocessor Tasks

    • Asma Lahimer, Pierre Lopez, Mohamed Haouari

    Pages 117-130

14. On Counting Lattice Points and Chvátal-Gomory Cutting Planes

    • Andrea Lodi, Gilles Pesant, Louis-Martin Rousseau

    Pages 131-136

15. Precedence Constraint Posting for Cyclic Scheduling Problems

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

    Pages 137-153

16. A Probing Algorithm for MINLP with Failure Prediction by SVM

    • Giacomo Nannicini, Pietro Belotti, Jon Lee, Jeff Linderoth, François Margot, Andreas Wächter

    Pages 154-169

17. Recovering Indirect Solution Densities for Counting-Based Branching Heuristics

    • Gilles Pesant, Alessandro Zanarini

    Pages 170-175

18. Using Hard Constraints for Representing Soft Constraints

    • Jean-Charles Régin

    Pages 176-189

19. The Objective Sum Constraint

    • Jean-Charles Régin, Thierry Petit

    Pages 190-195

20. Almost Square Packing

    • Helmut Simonis, Barry O’Sullivan

    Pages 196-209

This book constitutes the refereed proceedings of the 8th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR 2011, held in Berlin, Germany, in May 2011. The 13 revised full papers and 7 revised short papers presented together with 3 invited lectures were carefully reviewed and selected from 35 submissions. The papers are focused on both theoretical and practical, application-oriented issues and present current research with a special focus on the integration and hybridization of the approaches of constraint programming, artificial intelligence, and operations research technologies for solving large scale and complex real life combinatorial optimization problems.

• branch-and-cut algorithm
• complexity
• cutting planes
• parallel machines
• scheduling
• algorithm analysis and problem complexity

• Zuse Institut Berlin, Berlin, Germany

  Tobias Achterberg

• Department of Computer Science, University of Toronto, Toronto, Canada

  J. Christopher Beck

Policies and ethics