Journées de l'optimisation 2007 Optimizations days

Many optimization problems contain substructures involving constraints on sequences of decision variables. Such constraints can be very complex to express with mixed integer programming (MIP), while in constraint programming (CP), the global constraint regular easily represents this kind of substructure with deterministic finite automata (DFA). In this paper, we use DFAs and the associated layered graph structure built for the regular constraint consistency algorithm to develop a MIP version of the constraint. We present computational results on an employee timetabling problem, showing that this new modeling approach can significantly decrease computational times in comparison with a classical MIP formulation.

We propose generalizations of the Global Cardinality Constraint (GCC) in which a partition of the variables is given. In the context of resource allocation problems, such constraints allow the expression of requirements, in terms of lower and upper bounds, for resources with different capabilities. Alternate models using GCC's are shown to be weaker. We present filtering algorithms based on flow theory that achieve domain consistency and give experimental evidence of the usefulness of such constraints. We consider an optimization version of the constraints and discuss its relationship with the cost GCC.

We present an implementation of the Regular constraint in the Constraint-Based Local Search (CBLS) programming language Comet. In Comet, constraints do not prune the search space but guide the search toward a solution. We discuss the benefits of enriching CBLS with Regular constraints to solve scheduling problems.

We study the shift scheduling problem which consists of determining the schedule of a set of employees in order to satisfy the demand that fluctuates with time. We model the schedule of an employee with regular and context-free grammars. We propose two neighborhood operators for a hill climbing local search.