×

zbMATH — the first resource for mathematics

Filtering AtMostNValue with difference constraints: application to the shift minimisation personnel task scheduling problem. (English) Zbl 1407.90150
Summary: The problem of minimising the number of distinct values among a set of variables subject to difference constraints occurs in many real-life contexts. This is the case of the Shift Minimisation Personnel Task Scheduling Problem, introduced by Krishnamoorthy et al., which is used as a case study all along this paper. Constraint-Programming enables to formulate this problem easily, through several AllDifferent constraints and a single AtMostNValue constraint. However, the independence of these constraints results in a poor lower bounding, hence a difficulty to prove optimality. This paper introduces a formalism to describe a family of propagators for AtMostNValue. In particular, we provide simple but significant improvement of the state-of-the-art AtMostNValue propagator of Bessière et al., to filter the conjunction of an AtMostNValue constraint and disequalities. In addition, we provide an original search strategy which relies on constraint reification. Extensive experiments show that our contribution significantly improves a straightforward model, so that it competes with the best known approaches from Operational Research.

MSC:
90B35 Deterministic scheduling theory in operations research
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C10 Integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andreello, G.; Caprara, A.; Fischetti, M., Embedding \(\{0, 1 / 2 \}\)-cuts in a branch-and-cut framework: a computational study, INFORMS J. Comput., 19, 2, 229-238, (2007) · Zbl 1241.90181
[2] Asaf, S.; Eran, H.; Richter, Y.; Connors, D. P.; Gresh, D. L.; Ortega, J.; Mcinnis, M. J., Applying constraint programming to identification and assignment of service professionals, (CP, Lecture Notes in Computer Science, vol. 6308, (2010), Springer), 24-37
[3] Beldiceanu, N., Pruning for the minimum constraint family and for the number of distinct values constraint family, (CP, Lecture Notes in Computer Science, vol. 2239, (2001), Springer), 211-224 · Zbl 1067.68611
[4] Beldiceanu, N.; Carlsson, M.; Demassey, S.; Petit, T., Global constraint catalogue: past, present and future, Constraints, 12, 1, 21-62, (2007) · Zbl 1128.68092
[5] Beldiceanu, N.; Carlsson, M.; Flener, P.; Pearson, J., On the reification of global constraints, Constraints, 18, 1, 1-6, (2013) · Zbl 1328.68192
[6] Beldiceanu, N.; Simonis, H., A constraint seeker: finding and ranking global constraints from examples, (CP, Lecture Notes in Computer Science, vol. 6876, (2011), Springer), 12-26
[7] Bessière, C.; Hebrard, E.; Hnich, B.; Kiziltan, Z.; Walsh, T., Filtering algorithms for the nvalue constraint, Constraints, 11, 4, 271-293, (2006) · Zbl 1114.68064
[8] Borchers, B., Csdp, a c library for semidefinite programming, Optim. Methods Softw., 11, 1-4, 613-623, (1999) · Zbl 0973.90524
[9] Boussemart, F.; Hemery, F.; Lecoutre, C.; Sais, L., Boosting systematic search by weighting constraints, (European Conference on Artificial Intelligence, (2004)), 146-150
[10] Bron; Coen; Kerbosch; Joep, Algorithm 457: finding all cliques of an undirected graph, Commun. ACM, 16, 9, 575-577, (1973) · Zbl 0261.68018
[11] Burer, S.; Monteiro, R. D.C., A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Math. Program., 95, 2, 329-357, (2003) · Zbl 1030.90077
[12] Carter, M. W.; Tovey, C. A., When is the classroom assignment problem hard?, Oper. Res., 40, 1, 28-39, (1992) · Zbl 0745.90049
[13] Chabert, G.; Jaulin, L.; Lorca, X., A constraint on the number of distinct vectors with application to localization, (CP, Lecture Notes in Computer Science, vol. 5732, (2009), Springer), 196-210
[14] Choco: an open source Java constraint programming library, (2010), Ecole des Mines de Nantes, Tech. Rep.
[15] Debruyne, R.; Bessière, C., Some practicable filtering techniques for the constraint satisfaction problem, (Proceedings of the 15th International Joint Conference on Artificial Intelligence, IJCAI’97, (1997), Morgan Kaufmann Publishers Inc.), 412-417
[16] Dijkstra, M. C.; Kroon, L. G.; Salomon, M.; Van Nunen, J. A.E. E.; van Wassenhove, L. N., Planning the size and organization of KLM’s aircraft maintenance personnel, Interfaces, 24, 6, 47-58, (1994)
[17] Dowling, D.; Krishnamoorthy, M.; Mackenzie, H.; Sier, D., Staff rostering at a large international airport, Ann. Oper. Res., 72, 125-147, (1997) · Zbl 0895.90137
[18] Erdős, P.; Rubin, A.; Taylor, H., Choosability in graphs, (Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, Congres., vol. 26, (1979)), 125-157
[19] Ernst, A. T.; Jiang, H.; Krishnamoorthy, M.; Sier, D., Staff scheduling and rostering: a review of applications, methods and models, Eur. J. Oper. Res., 153, 1, 3-27, (2004) · Zbl 1053.90034
[20] F. Fages, On the use of constraint reification within search, 2013, personal communication.
[21] Fages, J. G.; Lapègue, T., Filtering atmostnvalue with difference constraints: application to the shift minimisation personnel task scheduling problem, (CP, Lecture Notes in Computer Science, vol. 8124, (2013), Springer), 63-79
[22] Feydy, T.; Somogyi, Z.; Stuckey, P. J., Half reification and flattening, (CP, Lecture Notes in Computer Science, vol. 6876, (2011), Springer), 286-301
[23] Fischetti, M.; Martello, S.; Toth, P., The fixed job schedule problem with spread-time constraints, Oper. Res., 35, 6, 849-858, (1987) · Zbl 0638.90055
[24] Fischetti, M.; Martello, S.; Toth, P., The fixed job schedule problem with working-time constraints, Oper. Res., 37, 3, 395-403, (1989) · Zbl 0672.90074
[25] Flavia, B.; Guillermo, D.; Javier, M., Exploring the complexity boundary between coloring and List-coloring, Electron. Notes Discrete Math., 25, 41-47, (2006) · Zbl 1134.68374
[26] Flener, P.; Pearson, J.; Sellmann, M.; Hentenryck, P. V.; Ågren, M., Dynamic structural symmetry breaking for constraint satisfaction problems, Constraints, 14, 4, 506-538, (2009) · Zbl 1186.68438
[27] Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness, (1979), W.H. Freeman · Zbl 0411.68039
[28] Golumbic, M. C., Algorithmic graph theory and perfect graphs, Ann. Discrete Math., vol. 57, (2004), Elsevier · Zbl 1050.05002
[29] Gondran, M.; Minoux, M.; Vajda, S., Graphs and algorithms, (1984), John Wiley & Sons, Inc. New York, NY, USA
[30] Gualandi, S.; Malucelli, F., Exact solution of graph coloring problems via constraint programming and column generation, INFORMS J. Comput., 24, 81-100, (2012) · Zbl 06599257
[31] Halldórsson, M. M.; Radhakrishnan, J., Greed is good: approximating independent sets in sparse and bounded-degree graphs, Algorithmica, 18, 1, 145-163, (1997) · Zbl 0866.68077
[32] Haralick, R. M.; Elliott, G. L., Increasing tree search efficiency for constraint satisfaction problems, (Proceedings of the 6th International Joint Conference on Artificial Intelligence, IJCAI’79, vol. 1, (1979), Morgan Kaufmann Publishers Inc.), 356-364
[33] Kadioglu, S.; Malitsky, Y.; Sellmann, M.; Tierney, K., Isac - instance-specific algorithm configuration, (ECAI, Frontiers in Artificial Intelligence and Applications, vol. 215, (2010), IOS Press), 751-756
[34] Kolen, A. W.J.; Lenstra, J. K.; Papadimitriou, C. H.; Spieksma, F. C.R., Interval scheduling: a survey, Nav. Res. Logist., 54, 530-543, (2007) · Zbl 1143.90337
[35] Kovalyov, M. Y.; Ng, C. T.; Cheng, T. C.E., Fixed interval scheduling: models, applications, computational complexity and algorithms, Eur. J. Oper. Res., 178, 331-342, (2007) · Zbl 1107.90019
[36] Krishnamoorthy, M.; Ernst, A.; Baatar, D., Algorithms for large scale shift minimisation personnel task scheduling problems, Eur. J. Oper. Res., 219, 34-48, (2012) · Zbl 1244.90094
[37] Krishnamoorthy, M.; Ernst, A., The personnel task scheduling problem, (Yang, X.; Teo, K.; Caccetta, L., Optimization Methods and Applications, Applied Optimization, vol. 52, (2001), Springer US), 343-368 · Zbl 0978.90048
[38] Kroon, L. G.; Salomon, M.; Wassenhove, L. N.V., Exact and approximation algorithms for the tactical fixed interval scheduling problem, Oper. Res., 45, 4, (1997) · Zbl 0887.90089
[39] Kuip, C., Public remark at workshop “CP solvers: modeling, applications, integration, and standartization”, (19th International Conference on Principles and Practice of Constraint Programming, (2013))
[40] Lapègue, T.; Fages, J. G.; Prot, D.; Bellenguez-Morineau, O., Personnel task scheduling problem library, (2013)
[41] Lecoutre, C.; Sais, L.; Tabary, S.; Vidal, V., Reasoning from last conflict(s) in constraint programming, Artif. Intell., 173, 18, 1592-1614, (2009) · Zbl 1185.68645
[42] Leone, R.; Festa, P.; Marchitto, E., A bus driver scheduling problem: a new mathematical model and a GRASP approximate solution, J. Heuristics, 17, 4, 441-466, (2010) · Zbl 1233.90152
[43] Lin, S. W.; Ying, K. C., Minimizing shifts for personnel task scheduling problems: a three-phase algorithm, Eur. J. Oper. Res., (2014) · Zbl 1304.90098
[44] López-Ortiz, A.; Quimper, C. G.; Tromp, J.; van Beek, P., A fast and simple algorithm for bounds consistency of the alldifferent constraint, (IJCAI, (2003), Morgan Kaufmann), 245-250
[45] Lovász, L., On the Shannon capacity of a graph, IEEE Trans. Inf. Theory, 25, 1, 1-7, (1979) · Zbl 0395.94021
[46] Michel, L.; Van Hentenryck, P., Activity-based search for black-box constraint programming solvers, (CPAIOR, (2012)), 228-243
[47] Monette, J. N.; Flener, P.; Pearson, J., Towards solver-independent propagators, (CP, Lecture Notes in Computer Science, vol. 7514, (2012), Springer), 544-560
[48] Pachet, F.; Roy, P., Automatic generation of music programs, (CP, (1999)), 331-345
[49] Refalo, P., Impact-based search strategies for constraint programming, (Principles and Practice of Constraint Programming, (2004)), 557-571 · Zbl 1152.68577
[50] Régin, J. C., A filtering algorithm for constraints of difference in csps, (National Conference on Artificial Intelligence, AAAI, (1994)), 362-367
[51] Richter, Y.; Freund, A.; Naveh, Y., Generalizing alldifferent: the somedifferent constraint, (CP, Lecture Notes in Computer Science, vol. 4204, (2006), Springer), 468-483 · Zbl 1160.68561
[52] (Rossi, F.; van Beek, P.; Walsh, T., Handbook of Constraint Programming, (2006), Elsevier) · Zbl 1175.90011
[53] Schrijvers, T.; Tack, G.; Wuille, P.; Samulowitz, H.; Stuckey, P. J., Search combinators, (Principles and Practice of Constraint Programming, (2011)), 774-788
[54] Schulte, C.; Stuckey, P. J., Efficient constraint propagation engines, ACM Trans. Program. Lang. Syst., 31, 1, (2008)
[55] Schulte, C.; Tack, G., Weakly monotonic propagators, (Principles and Practice of Constraint Programming, (2009)), 723-730
[56] Smet, P.; Wauters, T.; Mihaylow, M.; Vanden Berghe, G., The shift minimisation personnel task scheduling problem: a new hybrid approach and computational insights, (2013), University of North Carolina, Technical Report
[57] Van den Bergh, J.; Beliën, J.; De Bruecker, P.; Demeulemeester, E.; De Boeck, L., Personnel scheduling: a literature review, Eur. J. Oper. Res., 226, 3, 367-385, (2013) · Zbl 1292.90001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.