Modelling Counter Automata Constraints with Integer Programming

Many constraints can be described in term of automata where it is possible to come up with an automaton for which there is a one to one correspondence between the solutions of the considered constraint and the words accepted by the automaton [1]. To represent the automaton more compactly a common technique is to use counters [3] that are modified while triggering some transitions; a solution is then the word accepted by the automaton as well as the final counter value.
The goal of this internship is to model such counter automata constraints with integer programming, so that models consisting of a conjunction of counter automata constraints can be also handled in the context of MIP solvers [2]. The work is done in the context of an application that learns constraints models from sample solutions of the Unit Commitment Problem of EDF, which computes the power output for each power plant in France as a 48 hours time series [4].

[1] G. Pesant. A Regular Language Membership Constraint for Finite Sequences of Variables. In M. G. Wallace,
editor, Principles and Practice of Constraint Programming (CP’2004) , volume 3258 of LNCS , pages 482–495.
Springer-Verlag, 2004.
[2] M.-C. Côté, B. Gendron and L.-M. Rousseau: Modeling the Regular Constraint with Integer Programming.
In P. van Hentenryck and L. A. Wolsey, editor, Integration of AI and OR Techniques (CPAIOR’2007) , volume
4510 of LNCS , pages 29–43. Springer-Verlag, 2007.
[3] N. Beldiceanu, M. Carlsson, R. Debruyne, T. Petit: Reformulation of Global Constraints Based on
Constraints Checkers. Constraints 10(4): 339-362, 2005.
[4] N. Beldiceanu, G. Ifrim, A. Lenoir, H. Simonis: Describing and Generating Solutions for the EDF Unit
Commitment Problem with the ModelSeeker. In C. Schulte, editor, Principles and Practice of Constraint
Programming (CP’2013) , volume 8124 of LNCS , pages 733–748. Springer-Verlag, 2013.

Lieu: 
Mines - Nantes/ Paris
Encadrant: 
N. Beldiceanu
Co-Encadrant: 
M. Minoux
Référent Universitaire: 
Michel Minoux
Attribué: 
No
Année: 
2 015

User login