Current Science

Open Access Open Access  Restricted Access Subscription Access

Combinatorial Optimization in Science and Engineering


Affiliations
1 Department of Mathematical Sciences, Anchor University, Lagos, Nigeria
 

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.
User
Notifications
Font Size

  • 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.


Abstract Views: 403

PDF Views: 135




  • Combinatorial Optimization in Science and Engineering

Abstract Views: 403  |  PDF Views: 135

Authors

Julius Beneoluchi Odili
Department of Mathematical Sciences, Anchor University, Lagos, Nigeria

Abstract


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.

References





DOI: https://doi.org/10.18520/cs%2Fv113%2Fi12%2F2268-2274