caa a22 4500 44587919X CHVBK 20180317145537.0 cr unu---uuuuu 170323e20110101xx s 000 0 eng 10.1007/s10601-009-9083-2 doi (NATIONALLICENCE)springer-10.1007/s10601-009-9083-2 Formal languages for integer programming modeling of shift scheduling problems [Elektronische Daten] [Marie-Claude Côté, Bernard Gendron, Claude-Guy Quimper, Louis-Martin Rousseau] 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. Springer Science+Business Media, LLC, 2009 Constraint programming nationallicence Integer programming nationallicence Reformulations nationallicence Formal languages nationallicence Côté Marie-Claude Département de mathématiques et génie industriel, École Polytechnique de Montréal, succ. Centre-Ville, PO Box 6079, H3C 3A7, Montréal, Canada aut Gendron Bernard CIRRELT-Interuniversity Research Center on Enterprise Networks, Logistics and Transportation, Montréal, Canada aut Quimper Claude-Guy Omega Optimisation, 4200 St-Laurent 301, H2W 2R2, Montréal, Canada aut Rousseau Louis-Martin Département de mathématiques et génie industriel, École Polytechnique de Montréal, succ. Centre-Ville, PO Box 6079, H3C 3A7, Montréal, Canada aut Constraints Springer US; http://www.springer-ny.com 16/1(2011-01-01), 54-76 1383-7133 16:1<54 2011 16 10601 https://doi.org/10.1007/s10601-009-9083-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10601-009-9083-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Côté Marie-Claude Département de mathématiques et génie industriel, École Polytechnique de Montréal, succ. Centre-Ville, PO Box 6079, H3C 3A7, Montréal, Canada aut NATIONALLICENCE 700 1- Gendron Bernard CIRRELT-Interuniversity Research Center on Enterprise Networks, Logistics and Transportation, Montréal, Canada aut NATIONALLICENCE 700 1- Quimper Claude-Guy Omega Optimisation, 4200 St-Laurent 301, H2W 2R2, Montréal, Canada aut NATIONALLICENCE 700 1- Rousseau Louis-Martin Département de mathématiques et génie industriel, École Polytechnique de Montréal, succ. Centre-Ville, PO Box 6079, H3C 3A7, Montréal, Canada aut NATIONALLICENCE 773 0- Constraints Springer US; http://www.springer-ny.com 16/1(2011-01-01), 54-76 1383-7133 16:1<54 2011 16 10601 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer