Name
Abstract | ||
|---|---|---|
Matrix models are ubiquitous for constraint problems. Many such problems have a matrix of variables $\mathcal{M}$, with the same constraint defined by a finite-state automaton $\mathcal{A}$ on each row of $\mathcal{M}$ and a global cardinality constraint ${\mathit{gcc}}$ on each column of $\mathcal{M}$. We give two methods for deriving, by double counting, necessary conditions on the cardinality variables of the ${\mathit{gcc}}$ constraints from the automaton $\mathcal{A}$. The first method yields linear necessary conditions and simple arithmetic constraints. The second method introduces the cardinality automaton, which abstracts the overall behaviour of all the row automata and can be encoded by a set of linear constraints. We evaluate the impact of our methods on a large set of nurse rostering problem instances. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-642-13520-0_4 | CPAIOR |
Keywords | Field | DocType |
linear constraint,finite-state automaton,simple arithmetic constraint,large set,row automaton,cardinality variable,linear necessary condition,cardinality automaton,global cardinality constraint,double counting,constraint problem,computer science,finite state automaton | Discrete mathematics,Combinatorics,Mathematical optimization,Double counting (accounting),Matrix (mathematics),Automaton,Cardinality,Loop counter,Mathematics | Conference |
Volume | ISSN | ISBN |
6140 | 0302-9743 | 3-642-13519-6 |
Citations | PageRank | References |
4 | 0.49 | 15 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicolas Beldiceanu | 1 | 547 | 51.14 |
| Mats Carlsson | 2 | 975 | 79.24 |
| Pierre Flener | 3 | 533 | 50.28 |
| Justin Pearson | 4 | 237 | 24.28 |