Context-Free Grammar Constraints

Speaker: Meinolf Sellmann, Brown University

When dealing with real-world optimization problems, we frequently face complicated side constraints which are hard to formulate in integer programming and constraint programming. To facilitate the modeling process, we introduce the context-free grammar constraint that requires that an assignment of values to an ordered set of variables must form a word in a given context-free language. For this constraint, we devise an efficient, complete, and incremental filtering algorithm that has the same asymptotic complexity as the Cocke-Younger-Kasami algorithm for parsing context-free languages. Moreover, we show how the constraint can be linearized automatically whereby the resulting polytope has only integer extreme points.

Joint work with Serdar Kadioglu, Louis-Martin Rousseau, Claude-Guy Quimper, and Gilles Pesant