Implementation de la contrainte REGULAR en COMET.

摘要

Constraint-based local search intents to solve optimization problems by combining a inherited constraint programming modeling with a local search heuristic. Comet is a recent programming language for constraint-based local search. Comet is an open language allowing users to implement then own constraints. In this masters thesis, we describe an implementation of REGULAR Constraint.; REGULAR is a global constraint. It ensures that a sequence of variables may be recognized as a word from a regular language, or by a finite state automaton. In COMET, invariants are specific incremental variables that maintain a relation between one or more variables. C OMET ensures that all invariants' maintain their relation during the use of COMET programs. This master thesis describes an implementation of REGULAR constraint in COMET, and the way we use invariants to estimate the constraint violation degree and some simple local moves.; The REGULAR constraint is generally used for scheduling problems. Generally, schedules have to respect a specific pattern, which can be modeled within a finite state automaton. Through two scheduling problems, we will discuss the benefits and the limitations of the use of REGULAR constraint in constraint-based local search.; Keywords: Local Search, Constraint Programming, Constraint-Based Local Search, REGULAR Constraint, COMET, Rotating Schedule, Scheduling problems.