Name
Abstract | ||
|---|---|---|
Context-free grammar constraints enforce that a sequence of variables forms a word in a language defined by a context-free grammar. The constraint has received a lot of attention in the last few years as it represents an effective and highly expressive modeling entity. Its application has been studied in the field of Constraint Programming, Mixed Integer Programming, and SAT to solve complex decision problems such as shift scheduling. In this theoretical study we demonstrate how the constraint can be linearized efficiently. In particular, we propose a lifted polytope which has only integer extreme points. Based on this result, for shift scheduling problems we prove the equivalence of Dantzig's original set covering model and a lately introduced grammar-based model. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-01929-6_17 | CPAIOR |
Keywords | Field | DocType |
shift scheduling problem,context-free grammar,mixed integer programming,complex decision problem,expressive modeling entity,context-free grammar constraint,context-free grammar constraints,integer extreme point,constraint programming,grammar-based model,shift scheduling,context free grammar,scheduling problem,extreme point,decision problem,polytope,set cover | Constraint satisfaction,Decision problem,Mathematical optimization,Context-free grammar,ID/LP grammar,Computer science,Constraint programming,Grammar,Integer programming,Unrestricted grammar | Conference |
Volume | ISSN | Citations |
5547 | 0302-9743 | 5 |
PageRank | References | Authors |
0.54 | 10 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gilles Pesant | 1 | 906 | 80.82 |
| Claude-guy Quimper | 2 | 353 | 33.47 |
| Louis-Martin Rousseau | 3 | 888 | 63.71 |
| Meinolf Sellmann | 4 | 728 | 48.77 |