User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Efficient Filtering for the Resource-Cost AllDifferent Constraint

Primary tabs

download
  • Open access
  • PDF
  • 681.49 K
Van Cauwelaert, Sascha [UCL] Schaus, Pierre [UCL]

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 O(n · 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.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès libre
Publication date 2017
Language Anglais
Journal information "Constraints" - Vol. 22, no.4, p. 493–511 (Octobre 2017)
Peer reviewed yes
issn 1383-7133
e-issn 1572-9354
Publication status Publié
Affiliation UCL - SST/ICTM/INGI - Pôle en ingénierie informatique
Links
  1. Ait-Kaci, H., & Des Flambertins. F. (1999). Warren’s abstract machine: a tutorial reconstruction.
  2. Applegate, David L., Bixby, Robert E., Chvátal, V, & Cook, W. J. (2006). Concorde TSP solver.
  3. Applegate, David L., Bixby, Robert E., Chvátal, V, & Cook, W. J. (2011). The traveling salesman problem: a computational study. Princeton University Press.
  4. Van Cauwelaert, S, & Schaus, P. CSPLib problem 075: product matrix travelling salesman problem. http://www.csplib.org/Problems/prob075 .
  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).
  6. Dejemeppe Cyrille, Devolder Olivier, Lecomte Victor, Schaus Pierre, Forward-Checking Filtering for Nested Cardinality Constraints: Application to an Energy Cost-Aware Production Planning Problem for Tissue Manufacturing, Integration of AI and OR Techniques in Constraint Programming (2016) ISBN:9783319339535 p.108-124, 10.1007/978-3-319-33954-2_9
  7. Dolan Elizabeth D., Moré Jorge J., Benchmarking optimization software with performance profiles, 10.1007/s101070100263
  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.
  10. Focacci Filippo, Lodi Andrea, Milano Michela, Vigo Daniele, Solving TSP through the Integration of OR and CP Techniques, 10.1016/s1571-0653(04)00002-2
  11. Gay Steven, Hartert Renaud, Lecoutre Christophe, Schaus Pierre, Conflict Ordering Search for Scheduling Problems, Lecture Notes in Computer Science (2015) ISBN:9783319232188 p.140-148, 10.1007/978-3-319-23219-5_10
  12. Gay Steven, Schaus Pierre, De Smedt Vivian, Continuous Casting Scheduling with Constraint Programming, Lecture Notes in Computer Science (2014) ISBN:9783319104270 p.831-845, 10.1007/978-3-319-10428-7_59
  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.
  14. Houndji Vinasétan Ratheil, Schaus Pierre, Wolsey Laurence, Deville Yves, The StockingCost Constraint, Lecture Notes in Computer Science (2014) ISBN:9783319104270 p.382-397, 10.1007/978-3-319-10428-7_29
  15. Jonker Roy, Volgenant Ton, Transforming asymmetric into symmetric traveling salesman problems, 10.1016/0167-6377(83)90048-2
  16. OscaR Team (2012). OscaR: scala in OR. Available from https://bitbucket.org/oscarlib/oscar .
  17. Pesant Gilles, Gendreau Michel, Potvin Jean-Yves, Rousseau Jean-Marc, An Exact Constraint Logic Programming Algorithm for the Traveling Salesman Problem with Time Windows, 10.1287/trsc.32.1.12
  18. Plante Robert D., Lowe Timothy J., Chandrasekaran R., The Product Matrix Traveling Salesman Problem: An Application and Solution Heuristic, 10.1287/opre.35.5.772
  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 Jean-Charles, 10.1023/a:1020506526052
  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).
  22. Sellmann Meinolf, An Arc-Consistency Algorithm for the Minimum Weight All Different Constraint, Lecture Notes in Computer Science (2002) ISBN:9783540441205 p.744-749, 10.1007/3-540-46135-3_56
  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 Helmut, Hadzic Tarik, A Resource Cost Aware Cumulative, Lecture Notes in Computer Science (2011) ISBN:9783642194856 p.76-89, 10.1007/978-3-642-19486-3_5
  25. Van Cauwelaert Sascha, Lombardi Michele, Schaus Pierre, Understanding the Potential of Propagators, Integration of AI and OR Techniques in Constraint Programming (2015) ISBN:9783319180076 p.427-436, 10.1007/978-3-319-18008-3_29
  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 .
  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).
  28. van Hoeve, W.-J. (2001). The alldifferent constraint: a survey. coRR cs.PL/0105015.
  29. Vilím, P. (2004). O ( n . log ( n ) ) $\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.
  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.
  31. Warren, D. H. D. (1983). An abstract Prolog instruction set Vol. 309. California: Artificial Intelligence Center, SRI International Menlo Park.
  32. Weron Rafał, Electricity price forecasting: A review of the state-of-the-art with a look into the future, 10.1016/j.ijforecast.2014.08.008
  33. Wüstenhagen Rolf, Bilharz Michael, Green energy market development in Germany: effective public policy and emerging customer demand, 10.1016/j.enpol.2004.07.013
Bibliographic reference Van Cauwelaert, Sascha ; Schaus, Pierre. Efficient Filtering for the Resource-Cost AllDifferent Constraint. In: Constraints, Vol. 22, no.4, p. 493–511 (Octobre 2017)
Permanent URL http://hdl.handle.net/2078.1/187560