Formal languages for integer programming modeling of shift scheduling problems |
| |
Authors: | Marie-Claude Côté Bernard Gendron Claude-Guy Quimper Louis-Martin Rousseau |
| |
Affiliation: | (1) School of Psychology and Clinical Language Sciences, University of Reading, Whiteknights, PO Box 217, Reading, RG6 6AH, UK;(2) Institute for Linguistics, University of Potsdam, Potsdam, Germany |
| |
Abstract: | This paper approaches the problem of modeling optimization problems containing substructures involving constraints on sequences
of decision variables. Such constraints can be very complex to express with Mixed Integer Programming (MIP). We suggest an
approach inspired by global constraints used in Constraint Programming (CP) to exploit formal languages for the modeling of
such substructures with MIP. More precisely, we first suggest a way to use automata, as the CP regular constraint does, to express allowed patterns for the values taken by the constrained sequence of variables. Secondly, we
present how context-free grammars can contribute to formulate constraints on sequences of variables in a MIP model. Experimental
results on both approaches show that they facilitate the modeling, but also give models easier to solve by MIP solvers compared
to compact assignment MIP formulations. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|