Author Details

This article is a review of combinatorial optimization in science and engineering applications. Combinatorial optimization has found wide applicability in most of our day-to-day affairs, ranging from industrial, academic, logistic to manufacturing applications, etc. This study introduces the concepts of optimization identifying the different types of optimization in the literature, before focusing on discrete optimization methods. Moreover, much emphasis is placed on the application areas, examples and the development of mathematical models in combinatorial optimization. The study concludes by highlighting the merits and demerits of combinatorial optimization models and recommends further studies on the development of more efficient and user-friendly combinatorial optimization methods.

Keywords

Combinatorial Optimization Models, Discrete Optimization, Mathematical Models, Science and Engineering Applications.

Full Text

References

Gigerenzer, G. and Gaissmaier, W., Heuristic decision making. Annu. Rev. Psychol., 2011, 62, 451–482.

Vazan, P. and Tanuska, P. (eds), A short reflection on the strengths and weaknesses of simulation optimization. Int. J. Comput. Inform. Eng., 2012, 6(5), 640–644.

Miller, B. M. and Rubinovich, E. Y., Impulsive Control in Continuous and Discrete–Continuous Systems, 2012; www.books.google.com

Wolsey, L. A. and Nemhauser, G. L., Integer and Combinatorial Optimization, John Wiley, 2014.

Huang, Z.-H. and Ni, T., Smoothing algorithms for complementarity problems over symmetric cones. Comput. Optim. Appl., 2010, 45(3), 557–579.

Bertsekas, D. P., Constrained Optimization and Lagrange Multiplier Methods, Academic Press, 2014.

Tuba, M., Subotic, M. and Stanarevic, N. (eds), Modified cuckoo search algorithm for unconstrained optimization problems. In Proceedings of the 5th European Conference on European Computing Conference, World Scientific and Engineering Academy and Society, Paris, France, 2011, pp. 263–268.

Crandall, D. et al. (eds), Discrete-continuous optimization for large-scale structure from motion. Computer Vision and Pattern Recognition, IEEE Conference on Computer Vision and Pattern Recognition, IEEE, 2011.

Kouvelis, P. and Yu, G., Robust Discrete Optimization and its Applications, Springer Science & Business Media, 2013.

Horst, R. and Tuy, H., Global Optimization: Deterministic Approaches, Springer Science & Business Media, 2013.

Morais, H., Kádár, P., Faria, P., Vale, Z. A. and Khodr, H. M., Optimal scheduling of a renewable micro-grid in an isolated load area using mixed-integer linear programming. Renew. Energy, 2010, 35(1), 151–156.

Bazaraa, M. S., Jarvis, J. J. and Sherali, H. D., Linear Programming and Network Flows, John Wiley, 2011.

Xie, C., Lin, D.-Y. and Waller, S. T., A dynamic evacuation network optimization problem with lane reversal and crossing elimination strategies. Transp. Res. Part E, 2010, 46(3), 295–316.

Rao, R., Savsani, V. and Vakharia, D., Teaching–learning-based optimization: an optimization method for continuous non-linear large scale problems. Inf. Sci., 2012, 183(1), 1–15.

Conti, S., Held, H., Pach, M., Rumpf, M. and Schultz, R., Shape optimization under uncertainty – a stochastic programming perspective. SIAM J. Optim., 2009, 19(4), 1610–1632.

Anstreicher, K. M., On convex relaxations for quadratically constrained quadratic programming. Math. Program., 2012, 136(2), 233–251.

Rodriguez-Lujan, I., Huerta, R., Elkan, C. and Cruz, C. S., Quadratic programming feature selection. J. Mach. Learn. Res., 2010, 11, 1491–1516.

Wolkowicz, H., Saigal, R. and Vandenberghe, L., Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, Springer Science & Business Media, 2012; www.springer.com/gp/book/9780792377719 (accessed on 8 December 2017).

Sivaramakrishnan, K. K., Linear programming approaches to semidefinite programming problems, Doctoral thesis, Rensselaer Polytechnic Institute, New York, USA, 2002.

Higle, J. L. and Sen, S., Stochastic Decomposition: A Statistical Method for Large Scale Stochastic Linear Programming, Springer Science & Business Media, 2013; www.springer.com/gp/book/9780792338406 (accessed on 8 December 2017).

Le, C. V., Gilbert, M. and Askes, H., Limit analysis of plates using the EFG method and second-order cone programming. Int. J. Num. Methods Eng., 2009, 78(13), 1532–1552.

Birge, J. R. and Louveaux, F., Introduction to Stochastic Programming, Springer Science & Business Media, 2011.

Kuhn, H. W., Nonlinear programming: a historical view. In Traces and Emergence of Nonlinear Programming, Springer, 2014, pp. 393–414; https://link.springer.com/978-1-4614-0237-4 (accessed on 8 December 2017).

Gratton, S., Lawless, A. S. and Nichols, N. K., Approximate Gauss–Newton methods for nonlinear least squares problems. SIAM J. Optim., 2007, 18(1), 106–132.

Lee, J. and Leyffer, S., Mixed Integer Nonlinear Programming, Springer Science & Business Media, 2011; http://neos-guide.org/content/mixed-integer-nonlinear-programming (accessed on 8 December 2017).

Morales, J. L. and Nocedal, J., Remark on Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound constrained optimization. ACM Trans. Math. Software (TOMS), 2011, 38(1), 7.

Luo, Z.-Q., Pang, J.-S. and Ralph, D., Mathematical Programs with Equilibrium Constraints, Cambridge University Press, 1996.

Deb, K., Multi-objective optimization. In Search Methodologies, Springer, 2014, pp. 403–449.

Rios, L. M. and Sahinidis, N. V., Derivative-free optimization: a review of algorithms and comparison of software implementations. J. Global Optim., 2013, 56(3), 1247–1293.

Streiner, D. L., Norman, G. R. and Cairney, J., Health Measurement Scales: A Practical Guide to their Development and Use, Oxford University Press, Kenya, 2014.

Davenport, T. H., Process Innovation: Reengineering Work through Information Technology, Harvard Business Press, 2013.

Nemhauser, G. and Bienstock, D., Integer Programming and Combinatorial Optimization, Springer, 2005; https://link.springer.com/book/10.1007/978-3-319-07557-0 (accessed on 8 December 2017).

Margot, F., Symmetry in integer linear programming. In 50 Years of Integer Programming 1958–2008, Springer, 2010, pp. 647–686.

Hemmecke, R., Köppe, M., Lee, J. and Weismantel, R., Nonlinear integer programming. In 50 Years of Integer Programming 1958–2008, Springer, 2010, pp. 561–618.

Finkelman, M. D., Kim, W., Roussos, L. and Verschoor, A., A binary programming approach to automated test assembly for cognitive diagnosis models. Appl. Psychol. Meas., 2010, 34(5), 310–326.

Edelsbrunner, H., Algorithms in Combinatorial Geometry, Springer Science & Business Media, 2012; www.springer.com/gp/book/9783540137221 (accessed on 8 December 2017).

Bianchi, L., Dorigo, M., Gambardella, L. M. and Gutjahr, W. J., A survey on metaheuristics for stochastic combinatorial optimization. Nat. Comput., 2009, 8(2), 239–287.

Odili, J. B., Kahar, M. N. M. and Anwar, S., African buffalo optimization: a swarm-intelligence technique. Proc. Comput. Sci., 2015, 76, 443–448.

Odili, J. B. et al., Application of ant colony optimization to solving the traveling salesman’s problem. Sci. J. Electr. Electron. Eng., 2013, 175–176.

Odili, J. B. and Mohmad Kahar, M. N., Solving the traveling salesman’s problem using the African buffalo optimization. Comput. Intell. Neurosci., 2016, 1–12.

Odili, J. B. and Kahar, M. N. M., African buffalo optimization (ABO): a new meta-heuristic algorithm. J. Adv. Appl. Sci., 2015, 101–106.

Dorigo, M. and Birattari, M., Ant colony optimization. In Encyclopedia of Machine Learning, Springer, 2010, pp. 36–39.

Akay, B. and Karaboga, D., A modified artificial bee colony algorithm for real-parameter optimization. Inf. Sci., 2012, 192, 120–142.

Kennedy, J., Particle swarm optimization. In Encyclopedia of Machine Learning, Springer, 2010, pp. 760–766; https:/link.springer.com/referencework/10.1007%2F978-0-387-30164-8 (accessed on 8 December 2017).

Nagy, G. and Salhi, S., Location-routing: issues, models and methods. Eur. J. Oper. Res., 2007, 177(2), 649–672.

Mitrovic-Minic, S., Krishnamurti, R. and Laporte, G., Double-horizon based heuristics for the dynamic pickup and delivery problem with time windows. Transp. Res. Part B, 2004, 38(8), 669–685.

Whitley, L. D., Starkweather, T. and Fuquay, D. A. (eds), Scheduling problems and traveling salesmen: the genetic edge recombination operator. In Proceedings of the 3rd International Conference on Genetic Algorithms, George Mason University, Fairfax, Virginia, USA, June 1989.

Applegate, D. L., Bixby, R. E., Chvatal, V. and Cook, W. J., The Traveling Salesman Problem: A Computational Study, Princeton University Press, 2011.

Laporte, G., The vehicle routing problem: an overview of exact and approximate algorithms. Eur. J. Oper. Res., 1992, 59(3), 345–358.

Nuortio, T., Kytöjoki, J., Niska, H. and Bräysy, O., Improved route planning and scheduling of waste collection and transport. Expert Syst. Appl., 2006, 30(2), 223–232.

Singh, A., An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem. Appl. Soft Comput., 2009, 9(2), 625–631.

Han, D.-M. and Lim, J.-H., Smart home energy management system using IEEE 802.15. 4 and zigbee. IEEE Transactions Consumer Electronics, 2010, 56(3), 1403–1410.

Manen, S., Guillaumin, M. and Van Gool, L. (eds), Prime object proposals with randomized Prim’s algorithm. In IEEE International Conference on Computer Vision, Sydney, NSW, Australia, 2013.

Bergantiños, G. and Vidal-Puga, J., The folk solution and Boruvka’s algorithm in minimum cost spanning tree problems. Discrete Appl. Math., 2011, 159(12), 1279–1283.

Belov, G. and Scheithauer, G., A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths. Eur. J. Oper. Res., 2002, 141(2), 274–294.

Wascher, G., Haußner, H. and Schumann, H., An improved typology of cutting and packing problems. Eur. J. Oper. Res., 2007, 183(3), 1109–1130.

African Buffalo Optimization for Global Optimization

Abstract Views :228 | PDF Views:76

Authors

Julius Beneoluchi Odili ¹, A. Noraziah ²

Affiliations
1 Department of Mathematical Sciences, Anchor University, Lagos, NG
2 Universiti Malaysia Pahang, Kuantan 26300, MY

Source

Current Science, Vol 114, No 03 (2018), Pagination: 627-636

Abstract

In this study we apply the African buffalo optimization (ABO) to solve benchmark global optimization problems. Such problems which are artificial representation of different search landscapes ranging from unimodal to multimodal, separable to non-separable, constrained to unconstrained search landscapes have become a veritable instrument to test the search capacities of optimization algorithms. After a number of experimental procedures involving 28 benchmark problems, results from ABO prove to be rather competitive leading to the conclusion that it is a worthy addition to the body of swarm intelligence techniques.

Keywords

African Buffalo Optimization, Global Optimization, Search Landscapes, Swarm Intelligence Techniques.

Full Text

References

Pricopie, A. and Costache, A., In The 1940 Vrancea Earthquake. Issues, Insights and Lessons Learnt, Springer, New York, 2016, pp. 363–375.

Kennedy, J. In Encyclopedia of Machine Learning, Springer, New York, 2011, pp. 760–766.

Karaboga, D., Artificial bee colony algorithm. Scholarpedia, 2010, 5, 6915.

Yang, X.-S., Firefly algorithm, stochastic test functions and design optimisation. Int. J. Bio-Inspired Comput., 2010, 2, 78–84.

Yang, X.-S., In Nature Inspired Cooperative Strategies for Optimization (NICSO 2010), Springer, New York, 2010, pp. 65–74.

Gandomi, A. H., Yang, X.-S. and Alavi, A. H., Cuckoo search algorithm: a metaheuristic approach to solve structural optimization problems. Eng. Comput., 2013, 29, 17–35.

Rao, R. V., Savsani, V. J. and Vakharia, D., Teaching–learningbased optimization: a novel method for constrained mechanical design optimization problems. Comput-Aided Des., 2011, 43, 303–315.

Rao, R., Jaya: a simple and new optimization algorithm for solving constrained and unconstrained optimization problems. Int. J. Ind. Eng. Comput., 2016, 7, 19–34.

Odili, J. B., Kahar, M. N. M. and Anwar, S., African buffalo optimization: a swarm-intelligence technique. Proc. Comput. Sci., 2015, 76, 443–448.

Odili, J. B. and Mohmad Kahar, M. N., Solving the traveling salesman’s problem using the African buffalo optimization. Comput. Intell. Neurosci., 2015, 501, 1–12.

Yeomans, J. S. and Yang, X.-S., Municipal waste management optimisation using a firefly algorithm–driven simulationoptimisation approach. Int. J. Process Manage. Benchmark., 2014, 4, 363–375.

Matsushita, H., In IEEE Congress on Evolutionary Computation, Sendai, Japan, 2015, pp. 2672–2677.

Fister, I., Yang, X.-S. and Brest, J., A comprehensive review of firefly algorithms. Swarm Evol. Comput., 2013, 13, 34–46.

Yang, X.-S. Nature-inspired metaheuristic algorithms: success and new challenges. arXiv preprint arXiv:1211.6658, 2012.

Kavousi-Fard, A., Samet, H. and Marzbani, F., A new hybrid modified firefly algorithm and support vector regression model for accurate short term load forecasting. Expert Syst. Appl., 2014, 41, 6047–6056.

Yang, X.-S. and Deb, S., In IEEE World Congress on Nature and Biologically Inspired Computing (NaBIC 2009), Coimbatore, India, 2009, pp. 210–214.

Kamat, S. and Karegowda, A., A brief survey on cuckoo search applications. Int. J. Innov. Res. Comput. Commun. Eng., 2014, 2, 7–14.

Ouaarab, A., Ahiod, B. and Yang, X.-S., Discrete cuckoo search algorithm for the travelling salesman problem. Neural Comput. Appl., 2014, 24, 1659–1669.

Marichelvam, M., Prabaharan, T. and Yang, X.-S., Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan. Appl. Soft Comput., 2014, 19, 93–101.

Fister, I., Rauter, S., Yang, X.-S. and Ljubič, K., Planning the sports training sessions with the bat algorithm. Neurocomputing, 2015, 149, 993–1002.

Yang, X.-S. and He, X., Bat algorithm: literature review and applications. Int. J. Bio-Inspired Comput., 2013, 5, 141–149.

Warid, W., Hizam, H., Mariun, N. and Abdul-Wahab, N. I., Optimal power flow using the Jaya algorithm. Energies, 2016, 9, 678.

Pandey, H. M., Cloud System and Big Data Engineering (Confluence), In 6th IEEE International Conference, Noida, India, 2016, pp. 728–730.

Rao, R. V., Savsani, V. J. and Vakharia, D., Teaching–learningbased optimization: an optimization method for continuous nonlinear large scale problems. Inf. Sci., 2012, 183, 1–15.

Baghlani, A. and Makiabadi, M., Teaching–learning-based optimization algorithm for shape and size optimization of truss structures with dynamic frequency constraints. Iran. J. Sci. Technol. Trans. Civil Eng., 2013, 37, 409.

Rao, R., Review of applications of TLBO algorithm and a tutorial for beginners to solve the unconstrained and constrained optimization problems. Decis. Sci. Lett., 2016, 5, 1–30.

Ge, F., Hong, L. and Shi, L., An autonomous teaching–learning based optimization algorithm for single objective global optimization. Int. J. Comput. Intel. Syst., 2016, 9, 506–524.

Ali, M. M., Khompatraporn, C. and Zabinsky, Z. B., A numerical evaluation of several stochastic algorithms on selected continuous global optimization test problems. J. Global Optim., 2005, 31, 635–672.

Hedar, A.-R. and Fukushima, M., Tabu search directed by direct search methods for nonlinear global optimization. Eur. J. Oper. Res., 2006, 170, 329–349.

Bingham, D., Virtual library of simulation experiments: test functions and databases, 2015; https://www.sfu.ca/~ssurjano.

Mishra, S. K., Some new test functions for global optimization and performance of repulsive particle swarm method, 2006; SSRN 926132.

Fateen, S.-E. K. and Bonilla-Petriciolet, A., In Cuckoo Search and Firefly Algorithm, Springer, 2014, pp. 315–330.

Odili, J. B., Kahar, M. N. M. and Noraziah, A., African buffalo optimization and the randomized insertion algorithm for the asymmetric travelling Salesman’s problems. J. Theoret. Appl. Infor. Technol., 2016, 87(3) 356–364.

Odili J. B., Kahar, M. N. M. and Noraziah, A., Convergence analysis of the African buffalo optimization algorithm. Int. J. Simul. Sci. Technol, United Kingdom Simulation Society, 2016, 17(33), 44.1–44.7.

Odili, J. B., Kahar, M. N. M. and Noraziah, A., African buffalo optimization strategy for tuning parameters of a PID controller in automatic voltage regulators. Int. J. Simul., Sci. Technol., 2016, 17(33), 45.1–45.6.

de Oliveira, J. V., Semantic constraints for membership function optimization. IEEE Trans. Syst. Man, Cybern. – Part A, 1999, 29, 128–138.

Comparative Implementation of the Benchmark Dejong 5 Function using Flower Pollination Algorithm and the African Buffalo Optimization

Abstract Views :233 | PDF Views:71

Authors

Julius Beneoluchi Odili ¹, A. Noraziah ²

Affiliations
1 Department of Mathematical Sciences, Anchor University Lagos, Ipaja, Lagos, NG
2 IBM Centre of Excellence, Universiti Malaysia Pahang, Kuantan 26300, MY

Source

Current Science, Vol 117, No 5 (2019), Pagination: 871-877

Abstract

This communication presents experimental research findings on the application of the flower pollination algorithm (FPA) and the African buffalo optimization (ABO) to implement the complex and fairly popular benchmark Dejong 5 function. The study aims to unravel the untapped potential of FPA and the ABO in providing good solutions to optimization problems. In addition, it explores the Dejong 5 function with the hope of attracting the attention of the research community to evaluate the capacity of the two comparative algorithms as well as the Dejong 5 function. We conclude from this study that in implementing FPA and ABO for solving the benchmark Dejong 5 problem, a population of 10 search agents and using 1000 iterations can produce effective and efficient outcomes.

Keywords

Benchmark, Comparative Implementation, Iteration, Optimization Algorithms, Search Agents, Test Functions.

Full Text

References

http://www.cs.unm.edu/~neal.holts/dga/benchmarkFunction/quartic.html (accessed on 30 January 2017).

De Jong, K. A., Analysis of the behavior of a class of genetic adaptive systems, 1975; https://deepblue.lib.umich.edu/handle/2027.42/4507 (accessed on 20 August 2019).

http://www-optima.amp.i.kyotou.ac.jp/member/student/hedar/Hedar_ files/TestGO_files/Page1113.htm (accessed on 30 January 2017).

Foxholes, S., Electric power systems analysis and nature-inspired optimization algorithms, http://www.al-roomi.org/benchmarks/unconstrained/2-dimensions/7-shekel-s-foxholes-function (accessed on 2 February 2017).

http://www.cs.unm.edu/~neal.holts/dga/benchmarkFunction/rosen-brock.html (accessed on 30 January 2017).

http://www.al-roomi.org/benchmarks/unconstrained/n-dimensions/192-step-function-no-1 (accessed on 30 January 2017).

Yang, X.-S., Flower pollination algorithm for global optimization. In International Conference on Unconventional Computing and Natural Computation, Springer, pp. 240–249.

Odili, J. B., Kahar, M. N. M. and Anwar, S., African buffalo optimization: a swarm-intelligence technique. Proc. Comput. Sci., 2015, 76, 443–448.

Odili, J. B. and Mohmad Kahar, M. N., African buffalo optimization approach to the design of PID controller in automatic voltage regulator system. In National Conference for Postgraduate Research, Universiti Malaysia Pahang, Malyasia, 2016, pp. 641–648.

Odili, J. B., Kahar, M. N. M., Anwar, S. and Azrag, M. A. K., In IEEE 4th International Conference on Software Engineering and Computer Systems (ICSECS), 2015, pp. 90–95.

Odili, J. B. and Kahar, M. N. M., Numerical function optimization solutions using the African buffalo optimization algorithm (ABO). Br. J. Math. Comput. Sci., 2015, 10, 1–12.

Yang, X.-S., Karamanoglu, M. and He, X., Flower pollination algorithm: a novel approach for multiobjective optimization. Eng. Optim., 2014, 46, 1222–1237.

Lakshmi, D., Fathima, A. P. and Muthu, R., A novel flower pollination algorithm to solve load frequency control for a hydrothermal deregulated power system. Circuits Syst., 2016, 7, 166.

Balasubramani, K. and Marcus, K., A study on flower pollination algorithm and its applications. Int. J. Appl. Innov. Eng. Manage., 2014, 3, 230–235.

Odili, J. B. and Kahar, M. N. M., African buffalo optimization (ABO): a new meta-heuristic algorithm. J. Adv. Appl. Sci., 2015, 3, 101–106.

Hassan, M. H. and Muniyandi, R. C., An improved hybrid technique for energy and delay routing in mobile ad hoc networks. Int. J. Appl. Eng. Res., 2017, 12, 134–139.

Odili, J. B., Kahar, M. N. and Noraziah, A., Solving traveling salesman’s problem using African buffalo optimization, honey bee mating optimization and Lin-Kerninghan algorithms. World Appl. Sci. J., 2016, 34, 911–916.

Odili, J. B. and Mohmad Kahar, M. N., Solving the traveling salesman’s problem using the African buffalo optimization. Comput. Intell. Neurosci., 2016, 1–12.

Odili, J. B. and Noraziah, A., African buffalo optimization for global optimization. Curr. Sci., 2018, 114, 627–636.

Wolpert, D. H. and Macready, W. G., No free lunch theorems for optimization. IEEE Trans. Evol. Comput., 1997, 1, 67–82.

Khompatraporn, C., Pintér, J. D. and Zabinsky, Z. B., Comparative assessment of algorithms and software for global optimization. J. Global Optim., 2005, 31, 613–633.

Username
Password
Remember me