Developing an Enhanced Algorithms to Solve Mixed Integer Non-Linear Programming Problems Based on a Feasible Neighborhood Search Strategy

Authors

  • Mochamad Wahyudi Universitas Bina Sarana Informatika
  • Firmansyah Firmansyah Universitas Bina Sarana Informatika
  • Hengki Tamando Sihotang Institute of Computer Science
  • Lise Pujiastuti STMIK Antar Bangsa, Tangerang
  • Herman Mawengkang Universitas Sumatera Utara Medan

DOI:

https://doi.org/10.26594/register.v9i2.3706

Keywords:

Algorithm, Integer Programming, Large-Scale Problems, Neighborhood Search, Optimization

Abstract

Engineering optimization problems often involve nonlinear objective functions, which can capture complex relationships and dependencies between variables. This study focuses on a unique nonlinear mathematics programming problem characterized by a subset of variables that can only take discrete values and are linearly separable from the continuous variables. The combination of integer variables and non-linearities makes this problem much more complex than traditional nonlinear programming problems with only continuous variables. Furthermore, the presence of integer variables can result in a combinatorial explosion of potential solutions, significantly enlarging the search space and making it challenging to explore effectively. This issue becomes especially challenging for larger problems, leading to long computation times or even infeasibility. To address these challenges, we propose a method that employs the "active constraint" approach in conjunction with the release of nonbasic variables from their boundaries. This technique compels suitable non-integer fundamental variables to migrate to their neighboring integer positions. Additionally, we have researched selection criteria for choosing a nonbasic variable to use in the integerizing technique. Through implementation and testing on various problems, these techniques have proven to be successful.

Author Biographies

Mochamad Wahyudi, Universitas Bina Sarana Informatika

Department of Computer Science

Firmansyah Firmansyah, Universitas Bina Sarana Informatika

Department of Computer Science

Hengki Tamando Sihotang, Institute of Computer Science

Department of Operations Research

Lise Pujiastuti, STMIK Antar Bangsa, Tangerang

Department of Information System

References

B. A. Murtagh and S. J. Sugden, “A direct search approach to nonlinear integer programming,” Optim. Methods Softw., vol. 4, no. 3, pp. 171–189, 1994.

Y. Utami, D. Vinsensia, A. Nissa, and S. Sulastri, “Forecasting the Sum of New College Students with Linear Regression Approach,” J. Tek. Inform. CIT Medicom, vol. 14, no. 1, pp. 10–15, 2022.

P. Bonami et al., “An algorithmic framework for convex mixed integer nonlinear programs,” Discret. Optim., vol. 5, no. 2, pp. 186–204, 2008.

J. Li et al., “The application of nonlinear programming on ration formulation for dairy cattle,” J. Dairy Sci., vol. 105, no. 3, pp. 2180–2189, 2022.

P. Muts and I. Nowak, “Towards multi-tree methods for large-scale global optimization,” in Optimization of Complex Systems: Theory, Models, Algorithms and Applications, 2020, pp. 498–506.

P. Muts, I. Nowak, and E. M. T. Hendrix, “On decomposition and multiobjective-based column and disjunctive cut generation for MINLP,” Optim. Eng., vol. 22, pp. 1389–1418, 2021.

A. Msabawy and F. Mohammad, “Continuous sizing optimization of cold-formed steel portal frames with semi-rigid joints using generalized reduced gradient algorithm,” Mater. Today Proc., vol. 42, pp. 2290–2300, 2021.

T. Westerlund and F. Pettersson, “An extended cutting plane method for solving convex MINLP problems,” Comput. Chem. Eng., vol. 19, pp. 131–136, 1995.

C. Coey, M. Lubin, and J. P. Vielma, “Outer approximation with conic certificates for mixed-integer convex problems,” Math. Program. Comput., vol. 12, no. 2, pp. 249–293, 2020.

R. Quirynen and S. Di Cairano, “Tailored Presolve Techniques in Branch-and-Bound Method for Fast Mixed-Integer Optimal Control Applications,” arXiv Prepr. arXiv2211.12700, 2022.

M. Bussieck and S. Vigerske, “MINLP solver software,” Berlin, Germany, 691, 2010. doi: 0296-matheon-6848.

P. Belotti, J. Lee, L. Liberti, F. Margot, and A. Wächter, “Branching and bounds tighteningtechniques for non-convex MINLP,” Optim. Methods Softw., vol. 24, no. 4–5, pp. 597–634, 2009.

M. A. Lasemi, A. Arabkoohsar, A. Hajizadeh, and B. Mohammadi-Ivatloo, “A comprehensive review on optimization challenges of smart energy hubs under uncertainty factors,” Renew. Sustain. Energy Rev., vol. 160, p. 112320, 2022.

Z. Zhang, J. Wang, and J. Li, “Lossless convexification of nonconvex MINLP on the UAV path?planning problem,” Optim. Control Appl. Methods, vol. 39, no. 2, pp. 845–859, 2018, doi: https://doi.org/10.1002/oca.2380.

J. Lee and S. Leyffer, Mixed integer nonlinear programming, vol. 154. USA: Springer Science & Business Media, 2011.

E. Salajegheh, “Optimum design of plate structures using three-point approximation,” Struct. Optim., vol. 13, pp. 142–147, 1997.

P. M. F. Marsoit, “Quantum-inspired fuzzy genetic programming for enhanced rule generation in complex data analysis,” Int. J. Enterp. Model., vol. 15, no. 3, pp. 176–186, 2021.

M. Pyrz and J. Zawidzka, “Optimal discrete truss design using improved sequential and genetic algorithm,” Eng. Comput., vol. 18, no. 8, pp. 1078–1090, 2001.

S. Adadurov, Y. Fomenko, A. Khomonenko, and A. Krasnovidov, “Integration of the matlab system and the object-oriented programming system c# based on the microsoft com interface for solving computational and graphic tasks,” in Intelligent Algorithms in Software Engineering: Proceedings of the 9th Computer Science On-line Conference 2020, Volume 1 9, 2020, pp. 581–589.

J. A. Dauda, S. A. Rahmon, I. A. Tijani, F. Mohammad, and W. O. Okegbenro, “Design optimisation of reinforced concrete pile foundation using generalised reduced gradient algorithm,” Front. Eng. Built Environ., vol. 2, no. 3, pp. 133–153, 2022.

O. Yeniay, “A comparative study on optimization methods for the constrained nonlinear programming problems,” Math. Probl. Eng., vol. 2005, pp. 165–173, 2005.

K. S. Han and K. G. Ortizan, “Optimizing robust routing and production planning in stochastic supply chains: Addressing uncertainty of timing and demand for enhanced resilience and efficiency,” Int. J. Enterp. Model., vol. 16, no. 2, pp. 106–114, 2022.

H. T. Sihotang, P. M. F. Marsoit, and P. T. Marsoit, “Robust learning and optimization in distributionally robust stochastic variational inequalities under uncertainty,” Int. J. Enterp. Model., vol. 17, no. 1, pp. 24–34, 2023.

R. Fletcher and S. Leyffer, “Solving mixed integer nonlinear programs by outer approximation,” Math. Program., vol. 66, pp. 327–349, 1994.

J. B. Rosen, “The gradient projection method for nonlinear programming. Part I. Linear constraints,” J. Soc. Ind. Appl. Math., vol. 8, no. 1, pp. 181–217, 1960.

A. M. Geoffrion, “Generalized Benders decomposition,” J. Optim. Theory Appl., vol. 10, no. 4, pp. 237–260, 1972, doi: 10.1007/BF00934810.

A. O. Erick and K. A. Folly, “Power flow management in electric vehicles charging station using reinforcement learning,” in 2020 IEEE Congress on Evolutionary Computation (CEC), 2020, pp. 1–8.

T. Ahmad, R. Madonski, D. Zhang, C. Huang, and A. Mujeeb, “Data-driven probabilistic machine learning in sustainable smart energy/smart energy systems: Key developments, challenges, and future research opportunities in the context of smart grid paradigm,” Renew. Sustain. Energy Rev., vol. 160, p. 112128, 2022.

I. E. Grossmann and N. V Sahinidis, “Special issue on mixed integer programming and its application to engineering, part I,” Optim. Eng, vol. 3, no. 4, pp. 52–76, 2002.

J. Kronqvist and R. Misener, “A disjunctive cut strengthening technique for convex MINLP,” Optim. Eng., vol. 22, no. 3, pp. 1315–1345, 2021, doi: 10.1007/s11081-020-09551-6.

N. V Sahinidis, “Mixed-integer nonlinear programming 2018,” Optimization and Engineering, vol. 20. Springer, pp. 301–306, 2019.

M. A. Duran and I. E. Grossmann, “An outer-approximation algorithm for a class of mixed-integer nonlinear programs,” Math. Program., vol. 36, pp. 307–339, 1986.

T. Westerlund, H. Skrifvars, I. Harjunkoski, and R. Pörn, “An extended cutting plane method for a class of non-convex MINLP problems,” Comput. Chem. Eng., vol. 22, no. 3, pp. 357–365, 1998.

D. R. Morrison, S. H. Jacobson, J. J. Sauppe, and E. C. Sewell, “Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning,” Discret. Optim., vol. 19, pp. 79–102, 2016.

D. S. Nau, V. Kumar, and L. Kanal, “General branch and bound, and its relation to A? and AO?,” Artif. Intell., vol. 23, no. 1, pp. 29–58, 1984.

M. J. Bagajewicz and V. Manousiouthakis, “On the generalized Benders decomposition,” Comput. Chem. Eng., vol. 15, no. 10, pp. 691–700, 1991.

X. Cai, D. C. McKinney, L. S. Lasdon, and D. W. Watkins Jr, “Solving large nonconvex water resources management models using generalized benders decomposition,” Oper. Res., vol. 49, no. 2, pp. 235–245, 2001.

V. Vassilev and K. Genova, “An approximate algorithm for nonlinear integer programming,” Eur. J. Oper. Res., vol. 74, no. 1, pp. 170–178, 1994.

M. E. Mangram, “A simplified perspective of the Markowitz portfolio theory,” Glob. J. Bus. Res., vol. 7, no. 1, pp. 59–70, 2013.

C. Sansone and M. Vento, “Signature verification: increasing performance by a multi-stage system,” Pattern Anal. Appl., vol. 3, no. 2, pp. 169–181, 2000.

K. B. Misra and M. D. Ljubojevic, “Optimal Reliability Design of a System: A New Look,” IEEE Trans. Reliab., vol. R-22, no. 5, pp. 255–258, 1973, doi: 10.1109/TR.1973.5215673.

F. A. Tillman, C.-L. Hwang, and W. Kuo, “Optimization Techniques for System Reliability with Redundancy?A Review,” IEEE Trans. Reliab., vol. R-26, no. 3, pp. 148–155, 1977, doi: 10.1109/TR.1977.5220100.

R. Luus, “Optimization of system reliability by a new nonlinear integer programming procedure,” IEEE Trans. Reliab., vol. 24, no. 1, pp. 14–16, 1975.

Downloads

Published

2023-08-19

How to Cite

[1]
M. Wahyudi, F. Firmansyah, H. T. Sihotang, L. Pujiastuti, and H. Mawengkang, “Developing an Enhanced Algorithms to Solve Mixed Integer Non-Linear Programming Problems Based on a Feasible Neighborhood Search Strategy”, Register: Jurnal Ilmiah Teknologi Sistem Informasi, vol. 9, no. 2, pp. 112–121, Aug. 2023.

Issue

Section

Article