| Peer-Reviewed

Application of the Plant Propagation Algorithm and NSGA-II to Multiple Objective Linear Programming

Received: 3 May 2022     Accepted: 31 May 2022     Published: 10 February 2023
Views:       Downloads:
Abstract

Multiple Objective Linear Programming (MOLP) problems are usually solved by exact methods. However, nature-inspired population based stochastic algorithms such as the plant propagation algorithm are becoming more and more prominent. This paper applies the multiple objective plant propagation algorithm (MOPPA) and nondominated sorting genetic algorithm II (NSGA-II) for the first time to MOLP and compares their outcomes with those of prominent exact methods. Computational results from a collection of 51 existing MOLP instances suggests that MOPPA compares favourably with four of the most prominent exact methods namely extended multiple objective simplex algorithm (EMSA), affine scaling interior MOLP algorithm (ASIMOLP), Benson’s outer-approximation algorithm (BOA) and parametric simplex algorithm (PSA), and returns best nondominated points which are of higher quality than those returned by NSGA-II. However, the nondominated points approximated by NSGA-II are evenly distributed across the nondominated front. The methods compare well with the four exact methods especially on the large instances which the exact methods failed to solve even when given generous amounts of computation times.

Published in Mathematics and Computer Science (Volume 8, Issue 1)
DOI 10.11648/j.mcs.20230801.13
Page(s) 19-38
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2023. Published by Science Publishing Group

Keywords

Multiple Objective Linear Programming, Plant Propagation Algorithm, Nondominated Sorting Genetic Algorithm II, Penalty Function Method, Best Nondominated Point

References
[1] SS Abhyankar, TL Morin, and T Trafalis. Efficient faces of polytopes: Interior point algorithms, parametrization of algebraic varieties, and multiple objective optimization. Contemporary Mathematics, 114: 319-341, 1990.
[2] Maria João Alves and João Paulo Costa. An exact method for computing the nadir values in multiple objective linear programming. European Journal of Operational Research, 198 (2): 637-646, 2009.
[3] Maria João Alves, Carlos Henggeler Antunes, and João Clĺmaco. Interactive MOLP explorer: aATa graphical-based computational tool for teaching and decision support in multi-objective linear programming models. Computer Applications in Engineering Education, 23 (2): 314-326, 2015.
[4] Ami Arbel. An interior multiobjective linear programming algorithm. Computers and Operations Research, 20 (7): 723-735, 1993.
[5] Ami Arbel. A weighted-gradient approach to multi-objective linear programming problems using the analytic hierarchy process. Mathematical and computer modelling, 17 (4): 27-39, 1993.
[6] Ami Arbel. Anchoring points and cones of opportunities in interior multiobjective linear programming. Journal of the Operational Research Society, 45 (1): 83-96, 1994.
[7] Paul Armand and Christian Malivert. Determination of the efficient set in multiobjective linear programming. Journal of Optimization Theory and Applications, 70 (3): 467-489, 1991.
[8] Tapan P Bagchi. Multiobjective scheduling by genetic algorithms. Springer Science and Business Media, 1999.
[9] Vu Thien Ban. A finite algorithm for minimizing a concave function under linear constraints and its applications. In Proceedings of IFIP Working Conference on Recent Advances in System Modelling and Optimization, 1983.
[10] Harold P Benson. An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem. Journal of Global Optimization, 13 (1): 1-24, 1998.
[11] Herold P Benson. Further analysis of an outcome set-based algorithm for multiple objective linear programming. Journal of Optimization Theory and Applications, 97 (1): 1-10, 1998.
[12] Herold P Benson. Hybrid approach for solving multiple- objective linear programs in outcome space. Journal of Optimization Theory and Applications, 98 (1): 17-35, 1998.
[13] Victor Blanco, Justo Puerto, and Safae El Haj Ben Ali. A semidefinite programming approach for solving multiobjective linear programming. Journal of Global Optimization, 58 (3): 465-480, 2014.
[14] M Chakraborty and Ananya Ray. Parametric approach and genetic algorithm for multi objective linear programming with imprecise parameters. Opsearch, 47 (1): 73-92, 2010.
[15] László Csirmaz. Using multiobjective optimization to map the entropy region. Computational Optimization and Applications, 63 (1): 45-67, 2013.
[16] Jerald P Dauer. Analysis of the objective space in multiple objective linear programming. Journal of Mathematical Analysis and Applications, 126 (2): 579-593, 1987.
[17] Jerald P Dauer and Yi-Hsin Liu. Solving multiple objective linear programs in objective space. European Journal of Operational Research, 46 (3): 350-357, 1990.
[18] Jerald P Dauer and OA Saleh. Constructing the set of efficient objective values in multiple objective linear programs. European Journal of Operational Research, 46 (3): 358-365, 1990.
[19] Kalyanmoy Deb, Samir Agrawal, Amrit Pratap, and Tanaka Meyarivan. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGAII. In International Conference on Parallel Problem Solving from Nature, pages 849-858. Springer, 2000.
[20] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation, 6 (2): 182-197, 2002.
[21] S Dhanalakshmi, S Kannan, K Mahadevan, and S Baskar. Application of modified NSGA-II algorithm to combined economic and emission dispatch problem. International Journal of Electrical Power and Energy Systems, 33 (4): 992-1002, 2011.
[22] Daniel Dörfler, Andreas Löhne, Christopher Schneider, and Benjamin WeiBing. A benson-type algorithm for bounded convex vector optimization problems with vertex selection. Optimization Methods and Software, pages 1-21, 2021.
[23] JG Ecker, Nancy Shoemaker Hegner, and IA Kouada. Generating all maximal efficient faces for multiple objective linear programs. Journal of Optimization Theory and Applications, 30 (3): 353-381, 1980.
[24] JG Ecker and IA Kouada. Finding all efficient extreme points for multiple objective linear programs. Mathematical Programming, 14 (1): 249-261, 1978.
[25] M Ehrgott, J Puerto, and AM Rodriguez-Chia. Primal-dual simplex method for multiobjective linear programming. Journal of optimization theory and applications, 134 (3): 483-497, 2007.
[26] Matthias Ehrgott. Multicriteria optimization. Springer Science and Business Media, 2006.
[27] Matthias Ehrgott, Andreas Löhne, and Lizhen Shao. A dual variant of BensonâAÚs âAIJouter approximation algorithmâAI for multiple objective linear programming. Journal of Global Optimization, 52 (4): 757-778, 2012.
[28] Matthias Ehrgott and Dagmar Tenfelde-Podehl. Computation of ideal and nadir values and implications for their use in mcdm methods. European Journal of Operational Research, 151 (1): 119-139, 2003.
[29] Horst A Eiselt and C-L Sandblom. Linear programming and its applications. Springer Science and Business Media, 2007.
[30] Philippe Erlanger. Louis XIV. Weidenfeld and Nicolson, 1970.
[31] J Po Evans and RE Steuer. A revised simplex method for linear multiple objective programs. Mathematical Programming, 5 (1): 54-72, 1973.
[32] Eric S Fraga. http://www.ucl.ac.uk/ ucecesf/strawberry.html#orgec 5771e.2018.
[33] Eric S Fraga and Oluwamayowa Amusat. Understanding the impact of constraints: a rank based fitness function for evolutionary methods. In Advances in Stochastic and Deterministic Global Optimization, pages 243-254. Springer, 2016.
[34] Eric S Fraga, Abdellah Salhi, Di Zhang, and Lazaros G Papageorgiou. Optimisation as a tool for gaining insight: An application to the built environment. Journal of Algorithms and Computational Technology, 9 (1): 13- 26, 2015.
[35] Tomas Gal. A general method for determining the set of all efficient solutions to a linear vector maximum problem. European Journal of Operational Research, 1 (5): 307- 322, 1977.
[36] Ashish Ghosh and Mrinal Kanti Das. Non-dominated rank based sorting genetic algorithms. Fundamenta Informaticae, 83 (3): 231-252, 2008.
[37] Andreas H Hamel, Andreas Löhne, and Birgit Rudloff. Benson type algorithms for linear vector optimization and applications. Journal of Global Optimization, 59 (4): 811-836, 2014.
[38] John H Holland. Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence. The University of Michigan Press, 1975.
[39] Yuan Hu, Zhaohong Bie, Tao Ding, and Yanling Lin. An NSGA-II based multiobjective optimization for combined gas and electricity network expansion planning. Applied energy, 167: 280-293, 2016.
[40] H Isermann and G Naujoks. Operating manual for the EFFACET multiple objective linear programming package. Fakultaet fuer Wirtschaftswissenschaften, University of Bielefeld, Bielefeld, Germany, 1984.
[41] Heinz Isermann. The enumeration of the set of all efficient solutions for a linear multiple objective program. Journal of the Operational Research Society, 28 (3): 711- 725, 1977.
[42] HV Junior and Marcos Pereira Estellita Lins. A win-win approach to multiple objective linear programming problems. Journal of the Operational Research Society, 60 (5): 728-733, 2009.
[43] Deb Kalyanmoy. Multi objective optimization using evolutionary algorithms. John Wiley and Sons, 2001.
[44] S Kannan, S Baskar, James D McCalley, and P Murugan. Application of NSGA-II algorithm to generation expansion planning. IEEE Transactions on Power systems, 24 (1): 454-461, 2009.
[45] Narendra Karmarkar. A new polynomial-time algorithm for linear programming. In Proceedings of the sixteenth annual ACM symposium on Theory of computing, pages 302-311. ACM, 1984.
[46] Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, and Vladimir Gurvich. Generating all vertices of a polyhedron is hard. Discrete and Computational Geometry, 39 (1-3): 174-190, 2008.
[47] K-H Küfer. On the asymptotic average number of efficient vertices in multiple objective linear programming. Journal of Complexity, 14 (3): 333-377, 1998.
[48] C Lin, C Chen, and P Chen. On the modified interior point algorithm for solving multi-objective linear programming problems. International Journal of Information and Management Sciences, 17 (1): 107, 2006.
[49] Andreas Löhne. Vector optimization with infimum and supremum. Springer Science and Business Media, 2011.
[50] Andreas Löhne. Bensolve: VLP solver, version 1.2, www.bensolve.org. 2012.
[51] Andreas Löhne, Birgit Rudloff, and Firdevs Ulus. Primal and dual approximation algorithms for convex vector optimization problems. Journal of Global Optimization, 60 (4): 713-736, 2014.
[52] Andreas Löhne and Sebastian Schenker. MOPLIB: Multi-Objective Problem Library, http://moplib.uni- jena.de. Accessed 13 March 2017, 2015.
[53] Andreas Löhne and Benjamin WeiBing. Bensolve: VLP solver, version 2.0.x, www.bensolve.org. 2015.
[54] Anabel Martinez-Vargas, Josué Domĺnguez-Guerrero, ángel G Andrade, Roberto Sepúlveda, and Oscar Montiel-Ross. Application of NSGA-II algorithm to the spectrum assignment problem in spectrum sharing networks. Applied Soft Computing, 39: 188-198, 2016.
[55] Renzo Massobrio, G Fagúndez, and S Nesmachnow. Multiobjective taxi sharing optimization using the NSGA-II evolutionary algorithm. In 11th Metaheuristic International Conference, 2015.
[56] Zbigniew Michalewicz and Marc Schoenauer. Evolutionary algorithms for constrained parameter optimization problems. Evolutionary computation, 4 (1): 1-32, 1996.
[57] Anjana D Nandasana, Ajay Kumar Ray, and Santosh K Gupta. Applications of the non-dominated sorting genetic algorithm (NSGA) in chemical reaction engineering. International Journal of Chemical and Reactor Engineering, 1: 1018, 2003.
[58] Paschal B Nyiam and Abdellah Salhi. A comparative study of two key algorithms in multiple objective linear programming. Journal of Algorithms and Computational Technology, 13: 1748302619870424, 2019.
[59] Paschal B Nyiam and Abdellah Salhi. A comparison of benson outer approximation algorithm with an extended version of multiobjective simplex algorithm. Advances in Operations Research, 2021.
[60] Paschal B Nyiam and Abdellah Salhi. On the simplex, interior point and objective space approaches to multiple objective linear programming. Journal of Algorithms and Computational Technology, 15: 17483026211008414, 2021.
[61] P Pandian and M Jayalakshmi. Determining efficient solutions to multiple objective linear programming problems. Applied Mathematical Sciences, 7 (26): 1275-1282, 2013.
[62] Yan Pei and Jia Hao. Non-dominated sorting and crowding distance based multiobjective chaotic evolution. In International Conference in Swarm Intelligence, pages 15-22. Springer, 2017.
[63] Johan Philip. Algorithms for the vector maximization problem. Mathematical Programming, 2 (1): 207-229, 1972.
[64] Johan Philip. Vector maximization at a degenerate vertex. Mathematical Programming, 13 (1): 357-359, 1977.
[65] L Pourkarimi, MA Yaghoobi, and M Mashinchi. Determining maximal efficient faces in multiobjective linear programming problem. Journal of Mathematical Analysis and Applications, 354 (1): 234-248, 2009.
[66] Noraini Mohd Razali, John Geraghty, et al. Genetic algorithm performance with different selection strategies in solving TSP. In Proceedings of the world congress on engineering, volume 2, pages 1134-1139. International Association of Engineers Hong Kong, 2011.
[67] Alistair D Rodman, Eric S Fraga, and Dimitrios Gerogiorgis. On the application of a nature-inspired stochastic evolutionary algorithm to constrained multi-objective beer fermentation optimisation. Computers and Chemical Engineering, 108: 448-459, 2018.
[68] Birgit Rudloff, Firdevs Ulus, and Robert Vanderbei. A parametric simplex algorithm for linear vector optimization problems. Mathematical Programming, pages 1-30, 2015.
[69] Andrzej Ruszczyński and Robert J Vanderbei. Frontiers of stochastically nondominated portfolios. Econometrica, pages 1287-1297, 2003.
[70] Thomas L Saaty. The analytic hierarchy process: planning, priority setting, resources allocation. New York: McGraw, 1980.
[71] Abdellah Salhi and Eric S Fraga. Nature-inspired optimisation approaches and the new plant propagation algorithm. In Proceedings of the International Conference on Numerical Analysis and Optimisation (ICeMATH’11), Yogyakarta, Indonesia, 2011.
[72] J David Schaffer. Multiple objective optimization with vector evaluated genetic algorithms. In Proceedings of the 1st International Conference on Genetic Algorithms, Pittsburgh, PA, USA, July 1985, pages 93-100, 1985.
[73] Murray Schechter and Ralph E Steuer. A correction to the connectedness of the Evans-Steuer algorithm of multiple objective linear programming. Foundations of Computing and Decision Sciences, 30 (4): 351-360, 2005.
[74] Birsen I Selamoglu and Abdellah Salhi. The plant propagation algorithm for discrete optimisation: The case of the travelling salesman problem. In Nature-inspired computation in engineering, pages 43-61. Springer, 2016.
[75] Lizhen Shao and Matthias Ehrgott. Approximately solving multiobjective linear programmes in objective space and an application in radiotherapy treatment planning. Mathematical Methods of Operations Research, 68 (2): 257-276, 2008.
[76] Lizhen Shao and Matthias Ehrgott. Approximating the nondominated set of an molp by approximately solving its dual problem. Mathematical Methods of Operations Research, 68 (3): 469-492, 2008.
[77] Alice E Smith and David W Coit. Constraint handling techniques: aAT penalty functions. Handbook of evolutionary computation, pages 5-2, 1997.
[78] N Srinivas and K Deb. Multi-objective function optimisation using non-dominated sorting genetic algorithm. Evolutionary Comp, 2 (3): 221-248, 1995.
[79] Ralph E Steuer. Multiple criteria optimization: theory, computation, and applications. Wiley, 1986.
[80] Ralph E Steuer. Adbase: A multiple objective linear programming solver for all efficient extreme points and all unbounded efficient edges. Terry college of Business, University of Georgia, Athens, 2003.
[81] Muhammad Sulaiman, Abdellah Salhi, Birsen Irem Selamoglu, and Omar Bahaaldin Kirikchi. A plant propagation algorithm for constrained engineering optimisation problems. Mathematical Problems in Engineering, 2014.
[82] Ue-Pyng Wen and Wei-Tai Weng. An interior algorithm for solving multiobjective linear programming problem. Institute for Operations Research and the Management Sciences International Meeting: Tel Aviv - Israel, 1998.
[83] Wei-Tai Weng and Ue-Pyng Wen. An interior point algorithm for solving linear optimization over the efficient set problems. Journal of the Chinese Institute of Industrial Engineers, 18 (3): 21-30, 2001.
[84] Özgür Yeniay. Penalty function methods for constrained optimization with genetic algorithms. Mathematical and computational Applications, 10 (1): 45-56, 2005.
[85] PL Yu and M Zeleny. The techniques of linear multiobjective programming. Revue franc¸aise d’Automatique, d’Informatique et de Recherche Opérationnelle. Recherche Opérationnelle, 8 (3): 51-71, 1974.
[86] PL Yu and M Zeleny. Linear multiparametric programming by multicriteria simplex method. Management Science, 23 (2): 159-170, 1976.
[87] PL Yu and Milan Zeleny. The set of all nondominated solutions in linear cases and a multicriteria simplex method. Journal of Mathematical Analysis and Applications, 49 (2): 430-468, 1975.
[88] Tey Jing Yuen and Rahizar Ramli. Comparision of compuational efficiency of MOEAnD and NSGA-II for passive vehicle suspension optimization. ECMS, 2010: 219-225, 2010.
[89] Milan Zeleny. Compromise programming. In Cochrane JL, Zeleny M (eds), Multiple criteria decision making, pages 262-301. University of South Carolina Press, Columbia, SC, 1973.
[90] Milan Zeleny. Linear multiobjective programming, volume 95. Springer-Verlag, 1974.
[91] Milan Zeleny. Multiple criteria decision making. McGraw-Hill New York, 1982.
[92] WH Zhang. A compromise programming method using multibounds formulation and dual approach for multicriteria structural optimization. International journal for numerical methods in engineering, 58 (4): 661-678, 2003.
Cite This Article
  • APA Style

    Paschal Bisong Nyiam, Abdellah Salhi. (2023). Application of the Plant Propagation Algorithm and NSGA-II to Multiple Objective Linear Programming. Mathematics and Computer Science, 8(1), 19-38. https://doi.org/10.11648/j.mcs.20230801.13

    Copy | Download

    ACS Style

    Paschal Bisong Nyiam; Abdellah Salhi. Application of the Plant Propagation Algorithm and NSGA-II to Multiple Objective Linear Programming. Math. Comput. Sci. 2023, 8(1), 19-38. doi: 10.11648/j.mcs.20230801.13

    Copy | Download

    AMA Style

    Paschal Bisong Nyiam, Abdellah Salhi. Application of the Plant Propagation Algorithm and NSGA-II to Multiple Objective Linear Programming. Math Comput Sci. 2023;8(1):19-38. doi: 10.11648/j.mcs.20230801.13

    Copy | Download

  • @article{10.11648/j.mcs.20230801.13,
      author = {Paschal Bisong Nyiam and Abdellah Salhi},
      title = {Application of the Plant Propagation Algorithm and NSGA-II to Multiple Objective Linear Programming},
      journal = {Mathematics and Computer Science},
      volume = {8},
      number = {1},
      pages = {19-38},
      doi = {10.11648/j.mcs.20230801.13},
      url = {https://doi.org/10.11648/j.mcs.20230801.13},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.mcs.20230801.13},
      abstract = {Multiple Objective Linear Programming (MOLP) problems are usually solved by exact methods. However, nature-inspired population based stochastic algorithms such as the plant propagation algorithm are becoming more and more prominent. This paper applies the multiple objective plant propagation algorithm (MOPPA) and nondominated sorting genetic algorithm II (NSGA-II) for the first time to MOLP and compares their outcomes with those of prominent exact methods. Computational results from a collection of 51 existing MOLP instances suggests that MOPPA compares favourably with four of the most prominent exact methods namely extended multiple objective simplex algorithm (EMSA), affine scaling interior MOLP algorithm (ASIMOLP), Benson’s outer-approximation algorithm (BOA) and parametric simplex algorithm (PSA), and returns best nondominated points which are of higher quality than those returned by NSGA-II. However, the nondominated points approximated by NSGA-II are evenly distributed across the nondominated front. The methods compare well with the four exact methods especially on the large instances which the exact methods failed to solve even when given generous amounts of computation times.},
     year = {2023}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - Application of the Plant Propagation Algorithm and NSGA-II to Multiple Objective Linear Programming
    AU  - Paschal Bisong Nyiam
    AU  - Abdellah Salhi
    Y1  - 2023/02/10
    PY  - 2023
    N1  - https://doi.org/10.11648/j.mcs.20230801.13
    DO  - 10.11648/j.mcs.20230801.13
    T2  - Mathematics and Computer Science
    JF  - Mathematics and Computer Science
    JO  - Mathematics and Computer Science
    SP  - 19
    EP  - 38
    PB  - Science Publishing Group
    SN  - 2575-6028
    UR  - https://doi.org/10.11648/j.mcs.20230801.13
    AB  - Multiple Objective Linear Programming (MOLP) problems are usually solved by exact methods. However, nature-inspired population based stochastic algorithms such as the plant propagation algorithm are becoming more and more prominent. This paper applies the multiple objective plant propagation algorithm (MOPPA) and nondominated sorting genetic algorithm II (NSGA-II) for the first time to MOLP and compares their outcomes with those of prominent exact methods. Computational results from a collection of 51 existing MOLP instances suggests that MOPPA compares favourably with four of the most prominent exact methods namely extended multiple objective simplex algorithm (EMSA), affine scaling interior MOLP algorithm (ASIMOLP), Benson’s outer-approximation algorithm (BOA) and parametric simplex algorithm (PSA), and returns best nondominated points which are of higher quality than those returned by NSGA-II. However, the nondominated points approximated by NSGA-II are evenly distributed across the nondominated front. The methods compare well with the four exact methods especially on the large instances which the exact methods failed to solve even when given generous amounts of computation times.
    VL  - 8
    IS  - 1
    ER  - 

    Copy | Download

Author Information
  • Department of Mathematical Sciences, University of Essex, Colchester, United Kingdom

  • Department of Mathematical Sciences, University of Essex, Colchester, United Kingdom

  • Sections