Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 9

Position Papers of the 2016 Federated Conference on Computer Science and Information Systems

Is Your Parallel Algorithm Correct?

,

DOI: http://dx.doi.org/10.15439/2016F554

Citation: Position Papers of the 2016 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 9, pages 87–93 ()

Full text

Abstract. Verifying the correctness of parallel algorithms is not trivial, and it is usually omitted in the works from the parallel computation field. In this paper, we discuss in detail how to show that a certain parallel algorithm is correct. This process involves proving its safety and liveness. We perform the in-depth analysis of our parallel guided ejection search (P-GES) for the pickup and delivery problem with time windows, which serves as an excellent case study. P-GES was implemented as a distributed algorithm using the Message Passing Interface library with asynchronous communications, and was validated using the well-known Li and Lim's benchmark containing demanding test instances. We already proved the efficacy of this algorithm and showed that it can retrieve very high-quality (quite often better than the world's best at that time) routing schedules.

References

  1. M. Blocho and J. Nalepa, “A parallel algorithm for minimizing the fleet size in the pickup and delivery problem with time windows,” in Proc. of 22nd European MPI Users’ Group Meeting, ser. EuroMPI ’15. New York, USA: ACM, 2015, pp. 15:1–15:2. [Online]. Available: http://doi.acm.org/10.1145/2802658.2802673
  2. J. Nalepa and M. Blocho, “A parallel algorithm with the search space partition for the pickup and delivery with time windows,” in 10th International Conference on P2P, Parallel, Grid, Cloud and Internet Computing, 3PGCIC 2015, Krakow, Poland, November 4-6, 2015, 2015, pp. 92–99. [Online]. Available: http://dx.doi.org/10.1109/3PGCIC.2015.12
  3. L. Grandinetti, F. Guerriero, F. Pezzella, and O. Pisacane, “The multiobjective multi-vehicle pickup and delivery problem with time windows,” Social and Beh. Sc., vol. 111, pp. 203 – 212, 2014.
  4. W. P. Nanry and J. W. Barnes, “Solving the pickup and delivery problem with time windows using reactive tabu search,” Transportation Research, vol. 34, no. 2, pp. 107 – 121, 2000.
  5. J.-F. Cordeau, “A branch-and-cut algorithm for the dial-a-ride problem,” Oper. Res., vol. 54, no. 3, pp. 573–586, 2006. [Online]. Available: http://dx.doi.org/10.1287/opre.1060.0283
  6. R. Baldacci, E. Bartolini, and A. Mingozzi, “An exact algorithm for the pickup and delivery problem with time windows,” Operations Research, vol. 59, no. 2, pp. 414–426, 2011. [Online]. Available: http://dx.doi.org/10.1287/opre.1100.0881
  7. A. Bettinelli, A. Ceselli, and G. Righini, “A branch-and-price algorithm for the multi-depot heterogeneous-fleet pickup and delivery problem with soft time windows,” Mathematical Programming Computation, vol. 6, no. 2, pp. 171–197, 2014. [Online]. Available: http://dx.doi.org/10.1007/s12532-014-0064-0
  8. B. Bernay, S. Deleplanque, and A. Quilliot, “Routing on dynamic networks: GRASP versus genetic,” in Proceedings of the 2014 Federated Conference on Computer Science and Information Systems, Warsaw, Poland, September 7-10, 2014., 2014, pp. 487–492. [Online]. Available: http://dx.doi.org/10.15439/2014F52
  9. J.-F. Cordeau, G. Laporte, and S. Ropke, The Vehicle Routing Problem: Latest Advances and New Challenges. Boston, MA: Springer, 2008, ch. Recent Models and Algorithms for One-to-One Pickup and Delivery Problems, pp. 327–357. [Online]. Available: http://dx.doi.org/10.1007/978-0-387-77778-8_15
  10. R. Baldacci, A. Mingozzi, and R. Roberti, “Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints,” European Journal of Operational Research, vol. 218, no. 1, pp. 1 – 6, 2012.
  11. H. Akeb, A. Bouchakhchoukha, and M. Hifi, “A beam search based algorithm for the capacitated vehicle routing problem with time windows,” in Proceedings of the 2013 Federated Conference on Computer Science and Information Systems, Kraków, Poland, September 8-11, 2013., 2013, pp. 329–336. [Online]. Available: http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6644021
  12. H. Akeb, A. Bouchakhchoukha, and M. Hifi, Recent Advances in Computational Optimization: Results of the Workshop on Computational Optimization WCO 2013, FedCSIS 2013. Cham: Springer International Publishing, 2015, ch. A Three-Stage Heuristic for the Capacitated Vehicle Routing Problem with Time Windows, pp. 1–19. [Online]. Available: http://dx.doi.org/10.1007/978-3-319-12631-9_1
  13. Q. Lu and M. M. Dessouky, “A new insertion-based construction heuristic for solving the pickup and delivery problem with time windows,” European Journal of Operational Research, vol. 175, no. 2, pp. 672–687, 2006.
  14. C. Zhou, Y. Tan, L. Liao, and Y. Liu, “Solving the multi-vehicle pick-up and delivery problem with time widows by new construction heuristic,” in Proc. IEEE CISDA, vol. 2, 2006, pp. 1035–1042. [Online]. Available: http://dx.doi.org/10.1109/ISDA.2006.253754
  15. H. Li and A. Lim, “A metaheuristic for the pickup and delivery problem with time windows,” in Proc. IEEE ICTAI, 2001, pp. 160–167. [Online]. Available: http://dx.doi.org/10.1109/ICTAI.2001.974461
  16. S. N. Parragh, K. F. Doerner, and R. F. Hartl, “A survey on pickup and delivery problems,” Journal fur Betriebswirtschaft, vol. 58, no. 1, pp. 21–51, 2008. [Online]. Available: http://dx.doi.org/10.1007/s11301-008-0033-7
  17. S. Ropke and D. Pisinger, “An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows,” Transportation Science, vol. 40, no. 4, pp. 455–472, 2006. [Online]. Available: http://dx.doi.org/10.1287/trsc.1050.0135
  18. G. Pankratz, “A grouping genetic algorithm for the pickup and delivery problem with time windows,” OR Spectrum, vol. 27, no. 1, pp. 21–41, 2005. [Online]. Available: http://dx.doi.org/10.1007/s00291-004-0173-7
  19. Y. Nagata and S. Kobayashi, Proc. PPSN XI. Heidelberg: Springer, 2010, ch. A Memetic Algorithm for the Pickup and Delivery Problem with Time Windows Using Selective Route Exchange Crossover, pp. 536–545. [Online]. Available: http://dx.doi.org/10.1007/ 978-3-642-15844-5_54
  20. M. Cherkesly, G. Desaulniers, and G. Laporte, “A population-based metaheuristic for the pickup and delivery problem with time windows and LIFO loading,” Computers & Operations Research, vol. 62, pp. 23–35, 2015. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0305054815000829
  21. P. Kalina and J. Vokrínek, “Parallel solver for vehicle routing and pickup and delivery problems with time windows based on agent negotiation,” in 2012 IEEE International Conference on Systems, Man, and Cybernetics (SMC), Oct 2012, pp. 1558–1563. [Online]. Available: http://dx.doi.org/10.1109/ICSMC.2012.6377958
  22. J. Nalepa and M. Blocho, Intelligent Information and Database Systems: Proc. 8th Asian Conference, ACIIDS 2016. Heidelberg: Springer, 2016, ch. Enhanced Guided Ejection Search for the Pickup and Delivery Problem with Time Windows, pp. 388–398. [Online]. Available: http://dx.doi.org/10.1007/978-3-662-49381-6_37
  23. Y. Nagata and S. Kobayashi, “Guided ejection search for the pickup and delivery problem with time windows,” in Proc. EvoCOP, ser. LNCS. Springer, 2010, vol. 6022, pp. 202–213. [Online]. Available: http://dx.doi.org/10.1007/978-3-642-12139-5_18
  24. T. G. Crainic and M. Toulouse, “Parallel meta-heuristics,” in Handbook of Metaheuristics, ser. International Series in Operations Research & Management Science, M. Gendreau and J.-Y. Potvin, Eds. Springer US, 2010, vol. 146, pp. 497–541. [Online]. Available: http://dx.doi.org/10.1007/978-1-4419-1665-5_17
  25. J. Nalepa and M. Blocho, “Co-operation in the parallel memetic algorithm,” International Journal of Parallel Programming, vol. 43, no. 5, pp. 812–839, 2014. [Online]. Available: http://dx.doi.org/10.1007/s10766-014-0343-4
  26. T. G. Crainic and H. Nourredine, “Parallel meta-heuristics applications,” in Parallel Metaheuristics: A New Class of Algorithms, M. Gendreau and J.-Y. Potvin, Eds. Wiley, 2005, pp. 447–494. [Online]. Available: http://dx.doi.org/10.1007/978-1-4419-1665-5_17
  27. G. Senarclens de Grancy and M. Reimann, “Evaluating two new heuristics for constructing customer clusters in a vrptw with multiple service workers,” Central European Journal of Operations Research, vol. 23, no. 2, pp. 479–500, 2015. [Online]. Available: http://dx.doi.org/10.1007/s10100-014-0373-4
  28. R. Banos, J. Ortega, C. Gil, F. de Toro, and M. G. Montoya, “Analysis of OpenMP and MPI implementations of meta-heuristics for vehicle routing problems,” Applied Soft Computing, vol. 43, pp. 262 – 275, 2016. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S1568494616300862
  29. Z. Manna, “Mathematical theory of partial correctness,” Journal of Computer and System Sciences, vol. 5, no. 3, pp. 239 – 253, 1971. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0022000071800351
  30. M. Blocho, “A parallel memetic algorithm for the vehicle routing problem with time windows,” Ph.D. dissertation, Silesian University of Technology, 2013, (in Polish).
  31. S. Owicki and L. Lamport, “Proving liveness properties of concurrent programs,” ACM Trans. Program. Lang. Syst., vol. 4, no. 3, pp. 455–495, 1982. [Online]. Available: http://doi.acm.org/10.1145/357172.357178
  32. Z. Czech, Introduction to Parallel Computing. PWN, 2013.
  33. S. Wrona and M. Pawelczyk, “Controllability-oriented placement of actuators for active noise-vibration control of rectangular plates using a memetic algorithm,” Archives of Acoustics, vol. 38, no. 4, pp. 529–536, 2013. [Online]. Available: http://dx.doi.org/10.2478/aoa-2013-0062
  34. J. Nalepa and M. Kawulok, “A memetic algorithm to select training data for support vector machines,” in Proc. of the 2014 Annual Conference on Genetic and Evolutionary Computation, ser. GECCO ’14. New York, USA: ACM, 2014, pp. 573–580. [Online]. Available: http://doi.acm.org/10.1145/2576768.2598370
  35. K. Siminski, Man–Machine Interactions 4: 4th International Conference on Man–Machine Interactions, ICMMI 2015 Kocierz Pass, Poland, October 6–9, 2015. Cham: Springer International Publishing, 2016, ch. Memetic Neuro-Fuzzy System with Big-Bang-Big-Crunch Optimisation, pp. 583–592. [Online]. Available: http://dx.doi.org/10.1007/978-3-319-23437-3_50
  36. J. Nalepa, M. Cwiek, and M. Kawulok, “Adaptive memetic algorithm for the job shop scheduling problem,” in 2015 International Joint Conference on Neural Networks (IJCNN), July 2015, pp. 1–8. [Online]. Available: http://dx.doi.org/10.1109/IJCNN.2015.7280409
  37. J. Nalepa and M. Blocho, “Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows,” Soft Computing, vol. 20, no. 6, pp. 2309–2327, 2016. [Online]. Available: http://dx.doi.org/10.1007/s00500-015-1642-4
  38. J. Nalepa and M. Kawulok, “Adaptive memetic algorithm enhanced with data geometry analysis to select training data for SVMs,” Neurocomputing, vol. 185, pp. 113 – 132, 2016. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0925231215019839
  39. M. Cwiek, J. Nalepa, and M. Dublanski, Intelligent Information and Database Systems: Proc. 8th Asian Conference, ACIIDS 2016. Heidelberg: Springer, 2016, ch. How to Generate Benchmarks for Rich Routing Problems?, pp. 399–409. [Online]. Available: http://dx.doi.org/10.1007/978-3-662-49381-6_38