Open Access
Research Article
Two-phase gradient based search method for global optimum of constrained mixed integer programming problems using a tunneling function & comparison
*V. K. SrivastavaCorresponding authorvijayasrivastava@gmail.comOttawa Hospital Research Institute (OHRI) 501 Smyth Rd, Box 511Ottawa, ON, K1H 8L6, CanadaView full profile → , Vinit K. Srivastavavsrivastava@ohri.caOttawa Hospital Research Institute (OHRI) 501 Smyth Rd, Box 511Ottawa, ON, K1H 8L6, Canada0009-0007-9417-1802View full profile →
* Corresponding author · click or hover a name for details
- Received:
- 07 Jun 2023
- Published Online:
- 01 Jan 2026
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JIOS-1512
- Pages:
- 185–205
Abstract
In this paper, a gradient-based optimization approach with two stages is proposed that is designed to efficiently solve mixed-integer programming problems with linear and nonlinear objective functions and constraints. To find a viable local minimum in the first step, a gradient method with hemstitching modifications is used, which guarantees that the trajectory is redirected into the feasible region whenever constraint(s) violation take place. The purpose of the second phase is to identify another point on the opposite side of the barrier where the function value is approximately the same, by constructing a tunneling function at the current local minimum. This newly discovered point serves as the starting vector for the next cycle, which repeats the process of searching for the global optimum. The iterative procedure is repeated until no further reduction in the objective function value is observed. Several benchmark problems involving mixed-integer variables are tested. The gradient method involving 3n enumeration that the author previously proposed is compared with the results from this new optimization technique, with a minor change made in the first phase of the previous published method. The results are compared with other published results.
Keywords
Subject Classifications
90C1190C3090C59
References
[1] H. Land and A. G. Doig, “An automatic method for solving discrete programming problems,” Econometrica, vol. 28, no. 3, pp. 497-520 (1960). [Online]. Available: https://doi.org/10.2307/1910129[2] A. M. Geoffrion, “Generalized Benders decomposition,” J. Optim., vol. 10, pp. 237-260 (1972).[3] C. A. Floudas, A. Aggarwal, and A. R. Ciric, “Global optimum search for nonconvex NLP and MINLP problems,” Computers and Chemical Engineering, vol. 13, no. 10, pp. 1117-1132 (1989). [Online]. Available: https://doi.org/10.1007/BF00934810[4] A. Aggarwal and C. Floudas, “A decomposition approach for global optimum search in QP, NLP, and MINLP problems,” Computer Science (1990). [Online]. Available: https://doi.org/10.1007/BF00934810[5] K. Mompati and P. Kaelo, “An efficient hybrid conjugate gradient-based projection method for convex constrained nonlinear monotone equations,” Journal of Interdisciplinary Mathematics, vol. 22, no. 6, pp. 1031-1050 (2019). [Online]. Available: DOI: 10.1080/09720502.2019.1700889[6] J. E. Baker, “Adaptive selection methods for genetic algorithm,” in Proceedings of the First International Conference on Genetic Algorithms (1985). [Online]. Available: https://doi.org/dl.acm.org/doi/10.5555/645511.657075[7] D. E. Goldberg and K. Deb, “Foundations of genetic algorithms: A comparative analysis of selection schemes used in genetic algorithms,” in 1st ed., pp. 69-93, Elsevier (1991). [Online]. Available: https://doi.org/10.1016/B9780080506845500082[8] L. D. Whitley, “A genetic algorithm tutorial,” Statistics and Computing, vol. 4, no. 2, pp. 65–85, Jun. (1994). [Online]. Available: https://doi.org/10.1007/BF00175354[9] B. S. Cheung, A. Langevin, and H. Delmaire, “Coupling genetic algorithm with a grid search method to solve mixed integer nonlinear programming problems,” Computers and Mathematics with Applications, vol. 34, no. 12, pp. 13-23 (1997). [Online]. Available: www.sciencedirect.com/science/article/pii/S0898122197002290[10] K. Deep, K. P. Singh, M. Kansal, and C. Mohan, “A real coded genetic algorithm for solving integer and mixed integer optimization problems,” Applied Mathematics and Computation, vol. 212, no. 2, pp. 505-518 (2009).[11] K. Deb, “An efficient constraint handling method for genetic algorithms,” Computer Methods in Applied Mechanics and Engineering, vol. 186, no. 2, pp. 311–338 (2000).[12] Z. Hua and F. Huang, “An effective genetic algorithm approach to large scale mixed integer programming problems,” Applied Mathematics and Computation, vol. 174, no. 2, pp. 897-909 (2006).[13] D. Goldberg, Genetic Algorithms: Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley, MA (1989).[14] M. Thakur, S. S. Meghwani, and H. Jalota, “A modified real coded genetic algorithm for constrained optimization,” Applied Mathematics and Computation, vol. 23, pp. 292-317 (2014).[15] M. Crepinsek, M. Mernik, and S. H. Liu, “Analysis of exploration and exploitation in evolutionary algorithms by ancestry trees,” International Journal of Innovative Computing and Applications, vol. 3, no. 1, pp. 11-19 (2011).[16] L. Costa and P. Oliveira, “Evolutionary algorithms approach to the solution of mixed integer non-linear programming problems,” Computers and Chemical Engineering, vol. 25, no. 2, pp. 257-266 (2011).[17] Y. Lin, “Mixed-integer constrained optimization based on memetic algorithm,” Journal of Applied Research and Technology, vol. 11, no. 2, pp. 242-250 (2013).[18] T. Back, D. B. Fogel, and Z. Michalewicz, Handbook of Evolutionary Computation, Computational Intelligence Library, Oxford University Press, Inc., New York, NY, USA (1997). [Online]. Available: https://doi.org/. ISBN 0-7503-0392-1 and 0-7503-0895-8[19] J. Kennedy and R. C. Eberhart, “Particle swarm optimization,” in Proc. IEEE Int. Conf. Neural Network (ICNN), vol. 4, pp. 1942-1948 (1995).[20] J. Kennedy and R. C. Eberhart, “The particle swarm: Social adaptation in information-processing systems,” in New Ideas in Optimization, pp. 379-387, McGraw-Hill, London, UK (1999).[21] W. H. Lim, “A self-adaptive topologically connected-based particle swarm optimization,” IEEE Access, vol. 6, pp. 65347-65366 (2018).[22] L. C. Cagnina and S. C. Esquivel, “Solving engineering optimization problems with the simple constrained particle swarm optimizer,” Informatics, vol. 32, no. 2, pp. 319-328 (2008).[23] L. C. Cagnina, S. Esquivel, and R. Gallard, “Particle swarm optimization for sequencing problems: A case study,” in Proc. IEEE Congress on Evolutionary Computation (CEC), pp. 536-541 (2004). [Online]. Available: https://doi.org/10.1109/CEC2004.1330903.[24] Y. Shi and R. Eberhart, “A modified particle swarm optimizer,” in IEEE International Conference on Evolutionary Computation Proceedings: IEEE World Congress on Computational Intelligence (Cat. No.98TH8360), pp. 69-73 (1998). [Online]. Available: https://doi.org/10.1109/ICEC.1998.699146[25] A. A. Karim, N. M. Isa, and W. H. Lim, “Hovering swarm particle swarm optimization,” IEEE Access, vol. 9, pp. 115719-115749 (2021). [Online]. Available: https://doi.org/10.1109/ACCESS.2021.3106062[26] M. A. De Oca, T. Stutzle, M. Birattari, and M. Dorigo, “Frankenstein’s PSO: A composite particle swarm optimization algorithm,” IEEE Transactions on Evolutionary Computation, vol. 13, no. 5, pp. 1120-1132 (2009). [Online]. Available: https://doi.org/10.1109/TEVC.2009.2021465[27] Y. Fukuyama, “Fundamentals of particle swarm optimization,” in Modern Heuristic Optimization Techniques: Theory and Applications to Power Systems, Hoboken, NJ, USA, Wiley-IEEE Press (2008). [Online]. Available: https://doi.org/10.1002/9780470225868.ch4.25[28] Q. Chen and K. Yasuda, “Particle swarm optimization based global descent method,” Special issue on Electronics, Information and Systems / Special Issue Letter, vol. 26, pp. 1558 (2009). [Online]. Available: https://doi.org/10.1587/elex.6.1558[29] M. Mavrovouniotis, C. Li, and S. Yang, “A survey of swarm intelligence for dynamic optimization: Algorithms and applications,” Swarm and Evolutionary Computation, vol. 33, pp. 1–17 (2017). [Online]. Available: https://doi.org/10.1016/j.swevo.2016.12.005[30] F. Yang, P. Wang, Y. Zhang, L. Zheng, and J. Lu, “Survey of swarm intelligence optimization algorithms,” in 2017 IEEE International Conference on Unmanned Systems (ICUS), pp. 544-549 (2017).[31] F. Wang, H. Zhang, and A. Zhou, “A particle swarm optimization algorithm for mixed-variable optimization problems,” Swarm and Evolutionary Computation, vol. 60, 100879 (2021).[32] T. M. Shami, S. Mirjalili, Y. Al-Eryani, K. Daoudi, S. Izadi, and L. Abualiga, “Velocity pausing particle swarm optimization: A novel variant for global optimization,” Neural Computing and Applications, Advance online publication (2023). [Online]. Available: doi.org/10.1007/s00521-022-08179-0.[33] C. S. Adjiman and C. A. Floudas, “Rigorous convex under estimators for general twice-differentiable problems,” Journal of Global Optimization, vol. 9, no. 1, pp. 23–40 (1996). [Online]. Available: doi:10.1007/BF00121749[34] N. V. Sahinidis, “BARON: A general purpose global optimization software package,” Journal of Global Optimization, vol. 8, no. 2, pp. 201-204 (1996).[35] E. D. Smith and C. C. Pantelides, “A symbolic reformulation/spatial branch-and-bound algorithm for the global optimisation of nonconvex MINLPs,” Computers & Chemical Engineering, vol. 23, no. 4–5, pp. 457–478 (1999). doi: 10.1016/s0098-1354(98)00286-5.[36] P. Belotti, C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke, and A. Mahajan, “Mixed-integer nonlinear optimization,” Acta Numerica, vol. 22, pp. 1–131 (2013). doi: 10.1017/S0962492913000032.[37] S. Vigerske and A. Gleixner, “SCIP: Global optimization of mixed-integer nonlinear programs in a branch-and-cut framework,” Optimization Methods and Software, vol. 33, no. 3, pp. 563–593 (2017). doi: 10.1080/10556788.2017.1335312.[38] A. Gleixner, L. Eier, T. Gally, G. Gamrath, P. Gemander, R. L. Gottwald, G. Hendel, C. Hojny, T. Koch, M. Miltenberger, B. Müller, M. E. Pfetsch, C. Puchert, D. Rehfeldt, F. Schlösser, F. Serrano, Y. Shinano, J. M. Viernickel, S. Vigerske, D. Weninger, J. T. Witt, and J. Witzig, “The SCIP Optimization Suite 5.0,” ZIB Report 17-61, Zuse Institute Berlin (2017). urn:nbn:de:0297-zib-66297.[39] G. Gamrath, D. Anderson, K. Bestuzheva, W.-K. Chen, L. Eier, M. Gasse, P. Gemander, A. Gleixner, R. L. Gottwald, K. Halbig, G. Hendel, C. Hojny, T. Koch, P. L. Bodic, S. J. Maher, F. Matter, M. Miltenberger, E. Mühmer, B. Müller, M. E. Pfetsch, F. Schlösser, F. Serrano, Y. Shinano, C. Taw_k, S. Vigerske, F. Wegscheider, D. Weninger, and J. Witzig, “The SCIP Optimization Suite 7.0,” ZIB Report 20-10, Zuse Institute Berlin (2020). urn:nbn:de:0297-zib-78023.[40] A. Khajavirad and N. V. Sahinidis, “A hybrid LP/NLP paradigm for global optimization relaxations,” Mathematical Programming Computation, vol. 10, no. 3, pp. 383–421 (2018). doi: 10.1007/s12532-018-0138-5.[41] Y. Lin and L. Schrage, “The global solver in the LINDO API,” Optimization Methods & Software, vol. 24, no. 4–5, pp. 657–668 (2009). doi: 10.1080/10556780902753221.[42] G. Kocis and I. Grossmann, “Computational experience with DICOPT: Solving MINLP problems in process systems engineering,” Computers & Chemical Engineering, vol. 13, no. 3, pp. 307–315 (1989). doi: 10.1016/0098-1354(89)850082.[43] C. Buskens and D. Wassel, “The ESA NLP solver WORHP,” in Modeling and Optimization in Space Engineering, G. Fasano and J. D. Pinter, Eds., New York, NY: Springer, pp. 85–110 (2013). doi: 10.1007/978-1-4614-4469-5_4.[44] V. K. Srivastava and A. Fahim, “A two phase optimization procedure for integer programming problems,” Computers & Mathematics with Applications, vol. 42, no. 12, pp. 1475–1485 (2001). doi: 10.1016/S0898-1221(01)00264-4.[45] V. K. Srivastava and A. Fahim, “An optimization method for solving mixed discrete-continuous programming problems,” Computers & Mathematics with Applications, vol. 53, no. 12, pp. 1481–1491 (2007). doi: 10.1016/j.camwa.2006.09.007.[46] V. K. Srivastava and D. Spinello, “A two-phase combined gradient-tunneling based algorithm for constrained integer programming problems,” Journal of Information & Optimization Sciences, vol. 36, no. 4, pp. 339–365 (2015). doi: 10.1080/02522667.2014.932092.[47] V. K. Srivastava and D. Spinello, “Efficiency of robust heuristic gradient based enumerative and tunneling algorithms for constrained integer programming problems,” World Academy of Science, Engineering and Technology International Journal of Mathematical and Computational Sciences, vol. 11, no. 5, pp. 619–624 (2017).[48] V. K. Srivastava and D. Spinello, “Multi-objective optimization of combined system reliability and redundancy allocation problem,” World Academy of Science, Engineering and Technology International Journal of Mathematical and Computational Sciences, vol. 13, no. 8 (2019).[49] S. M. Roberts and H. I. Lyvers, “The gradient method in process control,” Industrial and Engineering Chemistry, vol. 53, no. 1, pp. 877–882 (1961).[50] W. R. Klingman and D. M. Himmelblau, “Nonlinear programming with the aid of a multiple-gradient summation technique,” Journal of the Association for Computing Machinery, vol. 11, no. 4, pp. 400–415 (1964).[51] A. V. Levy and A. Montalvo, “The tunneling algorithm for the global minimization of functions,” SIAM Journal on Scientific and Statistical Computing, vol. 6, no. 1, pp. 15–29 (1985). doi: 10.1137/0906003.[52] L. C. Cagnina, S. C. Esquivel, and C. A. Coello Coello, “Solving engineering optimization problems with the simple constrained particle swarm optimizer,” Informatica, vol. 32, pp. 319–326 (2008).[53] I. E. Grossmann, “Overview of mixed-integer nonlinear programming,” Computers and Chemical Engineering, vol. 29, pp. 2823–2835 (2005).[54] M. A. Duran and I. E. Grossmann, “An outer approximation algorithm for a class of mixed-integer nonlinear programs,” Mathematical Programming, vol. 36, pp. 307–339 (1986).[55] B. Öztürk, “Global and robust optimization for engineering design,” Ph.D. dissertation, Massachusetts Institute of Technology (2022).[56] J. W. Sitopu, H. Mawengkang, and R. S. Lubis, “An improved search approach for solving non-convex mixed-integer nonlinear programming problems,” in 4th International Conference on Operational Research (InteriOR), IOP Conf. Series: Materials Science and Engineering, vol. 300, pp. 012022 (2018). doi: 1
Views: 74Downloads: 3Citations: 0
