Parallel optimization over the integer efficient set
Djellouli Younes
AMCD-RO Laboratory, DGRSDT, USTHB, Faculty of Mathematics, Department of Operations Research, B.P. 32 El-alia, Bab Ezzouar, Algiers, 16111 Algeria
Search for more papers by this authorHamadou Sarah
AMCD-RO Laboratory, DGRSDT, USTHB, Faculty of Mathematics, Department of Operations Research, B.P. 32 El-alia, Bab Ezzouar, Algiers, 16111 Algeria
Search for more papers by this authorCorresponding Author
Chaabane Djamal
AMCD-RO Laboratory, DGRSDT, USTHB, Faculty of Mathematics, Department of Operations Research, B.P. 32 El-alia, Bab Ezzouar, Algiers, 16111 Algeria
Corresponding author.
Search for more papers by this authorDjellouli Younes
AMCD-RO Laboratory, DGRSDT, USTHB, Faculty of Mathematics, Department of Operations Research, B.P. 32 El-alia, Bab Ezzouar, Algiers, 16111 Algeria
Search for more papers by this authorHamadou Sarah
AMCD-RO Laboratory, DGRSDT, USTHB, Faculty of Mathematics, Department of Operations Research, B.P. 32 El-alia, Bab Ezzouar, Algiers, 16111 Algeria
Search for more papers by this authorCorresponding Author
Chaabane Djamal
AMCD-RO Laboratory, DGRSDT, USTHB, Faculty of Mathematics, Department of Operations Research, B.P. 32 El-alia, Bab Ezzouar, Algiers, 16111 Algeria
Corresponding author.
Search for more papers by this authorAbstract
This paper introduces a modified sequential version method for optimizing a linear function over an integer efficient set, as well as a new exact parallel algorithm. The performance of parallel programming in this context is clear and shown through different instances with different sizes. Each procedure builds a finite monotonous sequence of values for the main criterion to be optimized, in a reasonable amount of CPU execution time. This latter remains much better. For the first time, the Algerian IBNBADIS cluster—CERIST—was used with this type of problem. Significant results are obtained by both proposed techniques, particularly with the parallel one.
References
- Abbas, M., Chaabane, D., 2006. Optimizing a linear function over an integer efficient set. European Journal of Operational Research 174, 2, 1140–1161.
- Abraham, M.J., Murtola, T., Schulz, R., Páll, J., and Smith, J.C., Hess, B., Lindahla, E., 2015. Gromacs: high performance molecular simulations through multi-level parallelism from laptops to supercomputers. SoftwareX 1, 19–25.
10.1016/j.softx.2015.06.001 Google Scholar
- Benson, H., 1992. A finite nonadjacent extreme-point search algorithm for optimization over the efficient set. Journal of Optimization Theory and Applications 73, 1, 47–64.
- Boland, N., Charkhgarda, H., Savelsbergh, M., 2017. A new method for optimizing a linear function over the efficient set of a multiobjective integer program. European Journal of Operational Research 260, 3, 904–919.
- Chaabane, D., Brahmia, B., Ramdania, Z., 2012. The augmented weighted Tchebychev norm for optimizing a linear function over an integer efficient set of a multicriteria linear program. International Transactions in Operational Research 19, 4, 531–545.
- Chaabane, D., Pirlot, M., 2010. A method for optimizing over the integer efficient set. Journal of Industrial and Management Optimization 6, 4, 811–823.
- Chen, S., Senar, M., 2019. Exploring efficient data parallelism for genome read mapping on multicore and manycore architectures. Parallel Computing 87, 11–24.
- Dauer, J., Fosnaugh, T., 1995. Optimization over the efficient set. Journal of Global Optimization 7, 3, 261–277.
- Ecker, J., Kouada, I., 1975. Finding efficient points for multi-objective linear programs. Mathematical Programming 8, 375–377.
- Ecker, J., Song, H., 1994. Optimizing a linear function over an efficient set. Journal of Optimization Theory and Applications 83, 3, 541–563.
- Ehrgott, M., Gandibleux, X., 2000. A survey and annotated bibliography of multiobjective combinatorial optimization. OR Spektrum 22, 4, 425–460.
- Fülöp, J., 1994. A cutting plane algorithm for linear optimization over the efficient set. In S. Komlósi, T. Rapcsák, S. Schaible (eds) Generalized Convexity. Springer, Berlin, pp. 374–385.
10.1007/978-3-642-46802-5_28 Google Scholar
- Gao, J., Zhu, X., Zhang, R., 2022. A branchandprice approach to the multitasking scheduling with batch control on parallel machines. International Transactions in Operational Research 29, 1–22.
- Gustafson, J., Greer, B. (Intel). ClearSpeed Advance: A Hardware Accelerator for the Intel Math Library. http://www.clearspeed.com/docs/resources/ClearSpeed_Intel_Whitepaper_Mar07.pdf (accessed March 2006).
- Jorge, J., 2005. A bilinear algorithm for optimizing a linear function over the efficient set of a multiple objective linear programming problem. Journal of Global Optimization 31, 1, 1–16.
- Jorge, M., 2009. An algorithm for optimizing a linear function over an integer efficient set. European Journal of Operational Research 195, 1, 98–103.
- Kantour, N., Bouroubi, S., Chaabane, D., 2019. A parallel MOEA with criterion-based selection applied to the knapsack problem. Applied Soft Computing Journal 80, 358–373.
- Khurpia, N., Lee, S., Cho, Z., 1990. A parallel implementation of 3-D CT image reconstruction on hypercube multiprocessor. IEEE Transactions on Nuclear Science 37, 3, 1333–1346.
- Langerz, A., Venkataramanz, R., Palekar, U., Kalez, L., 2012. Performance optimization of a parallel, two stage stochastic linear program. 2012 IEEE 18th International Conference on Parallel and Distributed Systems. IEEE, Piscataway, NJ.
- Liu, Z., Ehrgott, M., 2018. Primal and dual algorithms for optimization over the efficient set. Optimization 67, 10, 1661–1686.
- Lokman, B., 2021. Optimizing a linear function over the nondominated set of multiobjective integer programs. International Transactions in Operational Research 28, 4, 2248–2267.
- Lokman, B., Koksalan, M., 2013. Finding all nondominated points of multi-objective integer programs. Journal of Global Optimization 57, 2, 347–365.
- Nguyen, N., 1992. An algorithm for optimizing a linear function over the integer efficient set. Konrad-Zuse-Zentrum fur Informationstechnik Berlin.
- Oorschot, V., Wiener, M., 1999. Parallel collision search with cryptanalytic applications. Journal of Cryptology 12, 1, 1–28.
- Philip, J., 1972. Algorithms for the vector maximization problem. Mathematical Programming 2, 1, 207–229.
10.1007/BF01584543 Google Scholar
- Sayin, S., 2000. Optimizing over the efficient set using a top-down search of faces. Operations Research 48, 1, 65–72.
- Steuer, R., 1986. Multiple Criteria Optimization: Theory, Computation and Application ( 1st edn). John Wiley & Sons, Inc., New York, NY.
- Sutter, D., Christiaens, M., Bosschere, K., Van Campenhout, J., 1998. On the use of subword parallelism in medical image processing. Parallel Computing 24, 9-10, 1537–1556.
- Sylva, J., Crema, A., 2004. A method for finding the set of non-dominated vectors for multiple objective integer linear programs. European Journal of Operational Research 158, 1, 46–55.
- Thach, P., Konno, H., Yokota, D., 1996. Dual approach to minimization on the set of Pareto optimal solutions. Journal of Optimization Theory and Applications 88, 3, 689–707.
- Thomaszewski, B., Pabst, S., Blochinger, W., 2007. Exploiting parallelism in physically-based simulations on multi-core processor architectures. EGPGV '07: Proceedings of the 7th Eurographics Conference on Parallel Graphics and Visualization. ACM, New York, NY.
- Ulungu, E., 1993. Détermination de l'ensemble des solutions efficaces et méthodes interactives. Ph.D. thesis, Mons-Hainaut, Faculty of Science, Belgium.
- White, D., 1996. The maximization of a function over the efficient set via a penalty function approach. European Journal of Operational Research 94, 1, 143–153.
- Yamamoto, Y., 2002. Optimization over the efficient set: overview, dedicated to Professor Reiner Horst on his 60th birthday. Journal of Global Optimization 22, 1, 285–317.
