×

zbMATH — the first resource for mathematics

Efficient filtering for the resource-cost alldifferent constraint. (English) Zbl 1387.90148
Summary: This paper studies a family of optimization problems where a set of items, each requiring a possibly different amount of resource, must be assigned to different slots for which the price of the resource can vary. The objective is then to assign items such that the overall resource cost is minimized. Such problems arise commonly in domains such as production scheduling in the presence of fluctuating renewable energy costs or variants of the Travelling Salesman Problem. In Constraint Programming, this can be naturally modeled in two ways: (a) with a sum of element constraints; (b) with a MinimumAssignment constraint. Unfortunately the sum of element constraints obtains a weak filtering and the MinimumAssignment constraint does not scale well on large instances. This work proposes a third approach by introducing the ResourceCostAllDifferent constraint and an associated incremental and scalable filtering algorithm, running in \(\mathcal{O}(n\cdot m)\), where \(n\) is the number of unbound variables and \(m\) is the maximum domain size of unbound variables. Its goal is to compute the total cost in a scalable manner by dealing with the fact that all assignments must be different. We first evaluate the efficiency of the new filtering on a real industrial problem and then on the Product Matrix Travelling Salesman Problem, a special case of the Asymmetric Travelling Salesman Problem. The study shows experimentally that our approach generally outperforms the decomposition and the MinimumAssignment ones for the problems we considered.
MSC:
90C10 Integer programming
90C27 Combinatorial optimization
Software:
Concorde; CSPLib; OscaR
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ait-Kaci, H., & Des Flambertins. F. (1999). Warren’s abstract machine: a tutorial reconstruction. · Zbl 0635.90096
[2] Applegate, David L., Bixby, Robert E., Chvátal, V, & Cook, W. J. (2006). Concorde TSP solver. · Zbl 0987.90086
[3] Applegate, David L., Bixby, Robert E., Chvátal, V, & Cook, W. J. (2011). The traveling salesman problem: a computational study. Princeton University Press. · Zbl 1130.90036
[4] Van Cauwelaert, S, & Schaus, P. CSPLib problem 075: product matrix travelling salesman problem. http://www.csplib.org/Problems/prob075. · Zbl 1049.90004
[5] de Saint-Marcq, V C, Schaus, P, Solnon, C, & Lecoutre, C (2013). Sparse-sets for domain implementation. In International workshop on techniques foR implementing constraint programming systems (pp. 1-10). · Zbl 1049.90004
[6] Dejemeppe, C, Devolder, O, Lecomte, V, & Schaus, P (2016). Forward-checking filtering for nested cardinality constraints: application to an energy cost-aware production planning problem for tissue manufacturing. In International conference on integration of artificial intelligence and operations research techniques in constraint programming (pp. 108-124). Springer. · Zbl 06598660
[7] Dolan, ElizabethD; Moré, JorgeJ, Benchmarking optimization software with performance profiles, Mathematical Programming, 91, 201-213, (2002) · Zbl 1049.90004
[8] Ducomman, S, Cambazard, H, & Penz, B (2016). Alternative filtering for the weighted circuit constraint: comparing lower bounds for the TSP and solving TSPTW. In AAAI conference on artificial intelligence.
[9] Focacci, F, Lodi, A, & Milano, M (1999). Integration of CP and OR methods for matching problems. In International workshop on integration of AI and OR techniques in constraint programming for combinatorial optimization problems. · Zbl 0990.90553
[10] Focacci, F; Lodi, A; Milano, M; Vigo, D, Solving TSP through the integration of OR and CP techniques, Electronic Notes in Discrete Mathematics, 1, 13-25, (1999) · Zbl 0990.90553
[11] Gay, S, Hartert, R, Lecoutre, C, & Schaus, P (2015). Conflict ordering search for scheduling problems. In International conference on principles and practice of constraint programming (pp. 140-148). Springer.
[12] Gay, S, Schaus, P, & De Smedt, V (2014). Continuous casting scheduling with constraint programming. In International conference on principles and practice of constraint programming (pp. 831-845). Springer.
[13] Gilmore, P.C, Lawler, E.L., & Shmoys, D. (1985). Well-solved special cases of the traveling salesman problem. In John Wiley & Sons (ed.), The traveling salesman problem. · Zbl 0631.90081
[14] Houndji, V. R., Schaus, P., Wolsey, L., & Deville, Y. (2014). The stockingcost constraint. In International conference on principles and practice of constraint programming (pp. 382-397). Springer. · Zbl 1028.68157
[15] Jonker, R; Volgenant, T, Transforming asymmetric into symmetric traveling salesman problems, Operations Research Letters, 2, 161-163, (1983) · Zbl 0529.90090
[16] OscaR Team (2012). OscaR: scala in OR. Available from https://bitbucket.org/oscarlib/oscar. · Zbl 0990.90553
[17] Pesant, G; Gendreau, M; Potvin, J-Y; Rousseau, J-M, An exact constraint logic programming algorithm for the traveling salesman problem with time windows, Transportation Science, 32, 12-29, (1998) · Zbl 0987.90086
[18] Plante, RD; Lowe, TJ; Chandrasekaran, R, The product matrix traveling salesman problem: an application and solution heuristic, Operations Research, 35, 772-783, (1987) · Zbl 0635.90096
[19] Régin, J.-C (1994). A filtering algorithm for constraints of difference in CSPs. In AAAI conference on artificial intelligence (Vol. 94, pp. 362-367).
[20] Régin, J-C, Cost-based arc consistency for global cardinality constraints, Constraints, 7, 387-405, (2002) · Zbl 1028.68157
[21] Sarvanov, V. I. (1980). On the complexity of minimizing a linear form on a set of cyclic permutations. In Dokl. Akad. Nauk SSSR (Vol. 253, pp. 533-535). · Zbl 0476.90081
[22] Sellmann, M (2002). An arc-consistency algorithm for the minimum weight all different constraint. In International conference on principles and practice of constraint programming (pp. 744-749). Springer.
[23] Simonis, H, & Hadzic, T (2010). A family of resource constraints for energy cost aware scheduling. In Third international workshop on constraint reasoning and optimization for computational sustainability. St. Andrews.
[24] Simonis, H, & Hadzic, T (2011). A resource cost aware cumulative. In Recent advances in constraints: 14th annual ERCIM international workshop on constraint solving and constraint logic programming, CSCLP 2009, Barcelona, Spain, June 15-17, 2009, Revised Selected Papers (pp. 76-89). Springer.
[25] Van Cauwelaert, S., Lombardi, M., & Schaus, P. (2015). Understanding the potential of propagators. In International conference on integration of artificial intelligence and operations research techniques in constraint programming (pp. 427-436). Springer. · Zbl 06605772
[26] Van Cauwelaert, S, Lombardi, M, & Schaus, P (2017). A visual web tool to perform what-if analysis of optimization approaches. arXiv preprint arXiv:1703.06042. · Zbl 0635.90096
[27] Van Hentenryck, P, & Carillon, J.-P. (1988). Generality versus specificity: an experience with AI and OR techniques. In AAAI conference on artificial intelligence (pp. 660-664). · Zbl 0529.90090
[28] van Hoeve, W.-J. (2001). The alldifferent constraint: a survey. coRR cs.PL/0105015.
[29] Vilím, P. (2004). \(\mathcal{O}(n.log(n))\) filtering algorithms for unary resource constraint. In Régin, J-C, & Rueher, M (Eds.), International conference on integration of artificial intelligence and operations research techniques in constraint programming (pp. 335-347): Springer. · Zbl 1094.90566
[30] Wamba, G. M., & Beldiceanu, N. (2016). The taskintersection constraint. In International conference on integration of artificial intelligence and operations research techniques in constraint programming (pp. 246-261). Springer. · Zbl 06598669
[31] Warren, D. H. D. (1983). An abstract Prolog instruction set Vol. 309. California: Artificial Intelligence Center, SRI International Menlo Park.
[32] Weron, R, Electricity price forecasting: a review of the state-of-the-art with a look into the future, International Journal of Forecasting, 30, 1030-1081, (2014)
[33] Wüstenhagen, R; Bilharz, M, Green energy market development in Germany: effective public policy and emerging customer demand, Energy Policy, 34, 1681-1696, (2006)
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.