Accelerating column generation for aircraft scheduling using constraint propagation Export

@article{citeulike:3101010, abstract = {We discuss how constraint programming can improve the performance of a column generation solution process for the NP-hard Tail Assignment problem in aircraft scheduling. Combining a constraint model of a relaxed Tail Assignment problem with column generation, we achieve substantially improved performance. A generalized preprocessing technique based on constraint propagation is presented that can dramatically reduce the size of the flight network. We also present a heuristic preprocessing method based on the costs of connections, and show how constraint propagation can be used to improve fixing heuristics. Proof of concept is provided using real world Tail Assignment instances.}, author = {Gr\"{o}nkvist, Mattias}, booktitle = {Part Special Issue: Constraint Programming}, citeulike-article-id = {3101010}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1143212}, citeulike-linkout-1 = {http://dx.doi.org/10.1016/j.cor.2005.01.017}, citeulike-linkout-2 = {http://www.sciencedirect.com/science/article/B6VC5-4FDJ6SG-1/2/abbed2262e8aab9c7dbeda8cc8e7c360}, doi = {10.1016/j.cor.2005.01.017}, journal = {Computers \& Operations Research}, keywords = {air, dis}, month = {October}, number = {10}, pages = {2918--2934}, posted-at = {2008-08-08 15:26:12}, priority = {2}, title = {Accelerating column generation for aircraft scheduling using constraint propagation}, url = {http://dx.doi.org/10.1016/j.cor.2005.01.017}, volume = {33}, year = {2006} }

TY - JOUR ID - citeulike:3101010 L3 - citeulike-article-id:3101010 N2 - We discuss how constraint programming can improve the performance of a column generation solution process for the NP-hard Tail Assignment problem in aircraft scheduling. Combining a constraint model of a relaxed Tail Assignment problem with column generation, we achieve substantially improved performance. A generalized preprocessing technique based on constraint propagation is presented that can dramatically reduce the size of the flight network. We also present a heuristic preprocessing method based on the costs of connections, and show how constraint propagation can be used to improve fixing heuristics. Proof of concept is provided using real world Tail Assignment instances. IS - 10 JF - Computers & Operations Research EP - 2934 TI - Accelerating column generation for aircraft scheduling using constraint propagation VL - 33 T2 - Part Special Issue: Constraint Programming SP - 2918 KW - air KW - dis AU - Grönkvist, Mattias PY - 2006/10// UR - http://dx.doi.org/10.1016/j.cor.2005.01.017 ER -