×

zbMATH — the first resource for mathematics

New filtering for AtMostNValue and its weighted variant: a Lagrangian approach. (English) Zbl 1327.90130
Summary: The AtMostNValue global constraint, which restricts the maximum number of distinct values taken by a set of variables, is a well known NP-Hard global constraint. The weighted version of the constraint, AtMostWValue, where each value is associated with a weight or cost, is a useful and natural extension. Both constraints occur in many industrial applications where the number and the cost of some resources have to be minimized. This paper introduces a new filtering algorithm based on a Lagrangian relaxation for both constraints. This contribution is illustrated on problems related to facility location, which is a fundamental class of problems in operations research and management sciences. Preliminary evaluations show that the filtering power of the Lagrangian relaxation can provide significant improvements over the state-of-the-art algorithm for these constraints. We believe it can help to bridge the gap between constraint programming and linear programming approaches for a large class of problems related to facility location.

MSC:
90C11 Mixed integer programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Beldiceanu, N; Carlsson, M; Walsh, T (ed.), Pruning for the minimum constraint family and for the number of distinct values constraint family, (2001), Berlin Heidelberg · Zbl 1067.68611
[2] Beldiceanu, N., Carlsson, M., & Thiel, S. (2002). Cost-filtering algorithms for the two sides of the sum of weights of distinct values constraint. Technical report - T2002-14: Swedish Institute of Computer Science.
[3] Benchimol, P; Van Hoeve, WJ; Régin, J-C; Rousseau, L-M; Rueher, M, Improved filtering for weighted circuit constraints, Constraints, 17, 205-233, (2012) · Zbl 1309.90115
[4] Bessiere, C; Hebrard, E; Hnich, B; Kiziltan, Z; Walsh, T, Filtering algorithms for the nvalue constraint, Constraints, 11, 271-293, (2006) · Zbl 1114.68064
[5] Bessiere, C; Katsirelos, G; Narodytska, N; Quimper, C-G; Walsh, T; Cohen, D (ed.), Decomposition of the nvalue constraint, (2010), Berlin Heidelberg
[6] Cambazard, H. Np-hard contraints involving costs: examples of applications and filtering. In Dixièmes Journées Francophones de Programmation par Contraintes - JFPC. 2014. Exposé invité.
[7] Cambazard, H; O’Mahony, E; O’Sullivan, B, A shortest path-based approach to the multileaf collimator sequencing problem, Discrete Applied Mathematics, 160, 81-99, (2012) · Zbl 1235.90125
[8] Cambazard, H., & Penz, B. (2012). A constraint programming approach for the traveling purchaser problem. In Milano, M. (Ed.) Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Quėbec City, QC, Canada, October 8-12, 2012. Proceedings, volume 7514 of Lecture Notes in Computer Science, (pp. 735-749): Springer. · Zbl 1015.90089
[9] Cooper, MC; de Givry, S; Sanchez, M; Schiex, T; Zytnicki, M; Werner, T, Soft arc consistency revisited, Artificial Intelligence, 174, 449-478, (2010) · Zbl 1213.68580
[10] Van den Bergh, J; Belieën, J; De Bruecker, P; Demeulemeester, E; De Boeck, L, Personnel scheduling: a literature review, European Journal of Operational Research, 226, 367-385, (2013) · Zbl 1292.90001
[11] Erlenkotter, D, A dual-based procedure for uncapacitated facility location, Operations Research, 26, 992-1009, (1978) · Zbl 0422.90053
[12] Fages, J-G; Lapègue, T, Filtering atmostnvalue with difference constraints: application to the shift minimisation personnel task scheduling problem, Artificial Intelligence, 212, 116-133, (2014) · Zbl 1407.90150
[13] Fages, J.-G., Lorca, X., & Rousseau, L.-M. (2014). The salesman and the tree: the importance of search in CP. Constraints, 1-18. · Zbl 1237.68188
[14] Focacci, F; Lodi, A; Milano, M; Jaffar, J (ed.), Cost-based domain filtering, (1999), Berlin Heidelberg
[15] Fontaine, D., Michel, L.D., & Van Hentenryck, P. Constraint-based lagrangian relaxation. In O’Sullivan, B. (Ed.) Principles and Practice of Constraint Programming - 20th International Conference, CP 2014, Lyon, France, September 8-12, 2014. Proceedings, volume 8656 of Lecture Notes in Computer Science, (pp. 324-339) (p. 2014). Berlin: Springer. · Zbl 1292.90001
[16] Gaspers, S., & Szeider, S. (2011). Kernels for global constraints, CoRR. arXiv: 1104.2541. · Zbl 1407.90150
[17] Geoffrion, AM; Balinski, ML (ed.), Lagrangean relaxation for integer programming, (1974), Berlin Heidelberg · Zbl 0395.90056
[18] Held, M; Karp, RM, The traveling-salesman problem and minimum spanning trees: part II, Mathematical Programming, 1, 6-25, (1971) · Zbl 0232.90038
[19] Kadioglu, S., Malitsky, Y., Sellmann, M., & Tierney, K. (2010). ISAC - instance-specific algorithm configuration. In ECAI, volume 215 of Frontiers in Artificial Intelligence and Applications, (pp. 751-756): IOS Press. · Zbl 0422.90053
[20] Lee, JHM; Leung, KL, Consistency techniques for flow-based projection-safe global cost functions in weighted constraint satisfaction, Journal of Artificial Intelligence Research, 43, 257-292, (2012) · Zbl 1237.68188
[21] Menana, J., & Demassey, S. (2009). Sequencing and counting with the multicost-regular constraint. In Van Hoeve, W.J., & Hooker, J.N. (Eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 6th International Conference, CPAIOR 2009, Pittsburgh, PA, USA, May 27-31, 2009, Proceedings, volume 5547 of Lecture Notes in Computer Science, (pp. 178-192): Springer. · Zbl 1241.68104
[22] Narula, SC; Ogbu, UI; Samuelsson, HM, An algorithm for the p-Median problem, Operations Research, 25, 709-713, (1977) · Zbl 0372.90096
[23] Prud’homme, C., Fages, J.-G., & Lorca, X. (2014). Choco3 Documentation. TASC, INRIA Rennes, LINA CNRS UMR 6241, COSLING S.A.S. · Zbl 1235.90125
[24] Sellmann, M; Wallace, M (ed.), Theoretical foundations of cp-based Lagrangian relaxation, (2004), Berlin Heidelberg · Zbl 1152.68584
[25] Sellmann, M; Fahle, T, Constraint programming based Lagrangian relaxation for the automatic recording problem, Annals OR, 118, 17-33, (2003) · Zbl 1026.90510
[26] Slusky, M.R., & Van Hoeve, W.J. (2013). A lagrangian relaxation for golomb rulers. In Gomes, C.P., & Sellmann, M. (Eds.) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18-22, 2013. Proceedings, volume 7874 of Lecture Notes in Computer Science, (pp. 251-267): Springer. · Zbl 1382.68233
[27] Wah, B.W., & Wu, Z. (1999). The theory of discrete lagrange multipliers for nonlinear discrete optimization. In Jaffar, J. (Ed.) Principles and Practice of Constraint Programming - CP’99, 5th International Conference, Alexandria, Virginia, USA, October 11-14, 1999, Proceedings, volume 1713 of Lecture Notes in Computer Science, (pp. 28-42): Springer. · Zbl 0965.90051
[28] Wolsey, L.A. (1998). Integer programming. Wiley-Interscience series in discrete mathmatics and optimization. New York: Wiley.
[29] Zhao, X; Luh, PB, New bundle methods for solving Lagrangian relaxation dual problems, Journal of Optimization Theory and Applications, 113, 373-397, (2002) · Zbl 1015.90089
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.