Modeling the regular constraint with integer programming

Cote, M.-C.;Gendron, B.;Rousseau, L.-M.
(2007) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 4th International Conference, CPAIOR 2007 — Location: Brussels, Belgium (23.May.2007)

Files

No attached file found for this publication.

Details

Authors
  • Cote, M.-C.
    Author
  • Gendron, B.
    Author
  • Rousseau, L.-M.
    Author
Abstract
Many optimisation 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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Cote, M.-C., Gendron, B., & Rousseau, L.-M. (2007). Modeling the regular constraint with integer programming. In Van Hentenryck, P.; Wolsey, L.; (ed.), Integration of AI and OR Techniques in Constraint Programming forCombinatorial Optimization Problems. Proceedings 4th InternationalConference, CPAIOR 2007 (p. p. 29-43). Springer-verlag. https://hdl.handle.net/2078.5/223066