DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Fifty Seven
TITLE: "Constraint Programming and Large Scale Discrete Optimization"
EDITORS: Eugene C. Freuder and Richard J. Wallace

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the AMS Bookstore and order directly from there. DIMACS does not distribute or sell these books.


Constraint programming has become an important general approach for solving hard combinatorial problems that occur in a number of application domains, such as scheduling and configuration. This volume contains selected papers from the workshop on Constraint Programming and Large Scale Discrete Optimization held September 14-17, 1998 at DIMACS. It gives a sense of state-of-the-art research in this field, touching on many of the important issues that are emerging and giving an idea of the major current trends. Topics include new strategies for local search, multithreaded constraint programming, specialized constraints that enhance consistency processing, fuzzy representations, hybrid approaches involving both constraint programming and integer programming, and applications to scheduling problems in domains such as sports scheduling and satellite scheduling.


Foreword                                                   vii

Introduction to DIMACS workshop on Constraint 
  Programming and Large Scale Discrete Optimization  
    R. J. Wallace and E. C. Freuder                          1

           Part I. General Methods 

Using global constraints for local search 
    A. Nareyek                                               9
Guided local search joins the elite in discrete 
    C. Voudouris and E. Tsang                               29                

Multithreaded constraint programming: A hybrid approach 
    F. Zabatta                                              41

      Part II. CP approaches to scheduling 

Nurse rostering as constraint satisfaction with fuzzy 
  constraints and inferred control strategies 
    H. Meyer auf'm Hofe                                     67

A constraint-based approach to satellite scheduling 
    J. C. Pemberton and F. Galiber, III                    101

Minimization of the number of breaks in sports 
  scheduling problems using constraint programming 
    J.-C. Régin                                            115

A constraint programming pre-processor for a bus 
  driver scheduling system 
    B. M. Smith, C. J. Layfield, and A. Wren               131

     Part III. LSCO and software methodology 

Large scale combinatorial optimization: 
  A methodological viewpoint 
    C. Gervet                                              151

Index Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on September 27, 2001.