Developing an Enhanced Algorithms to Solve Mixed Integer Non-Linear Programming Problems Based on a Feasible Neighborhood Search Strategy
DOI:
https://doi.org/10.26594/register.v9i2.3706Keywords:
Algorithm, Integer Programming, Large-Scale Problems, Neighborhood Search, OptimizationAbstract
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.
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
How to Cite
Issue
Section
License
Copyright (c) 2023 Mochamad Wahyudi, Firmansyah Firmansyah, Hengki Tamando Sihotang, Lise Pujiastuti, Herman Mawengkang
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Please find the rights and licenses in Register: Jurnal Ilmiah Teknologi Sistem Informasi. By submitting the article/manuscript of the article, the author(s) agree with this policy. No specific document sign-off is required.
1. License
The non-commercial use of the article will be governed by the Creative Commons Attribution license as currently displayed on Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
2. Author(s)' Warranties
The author warrants that the article is original, written by stated author(s), has not been published before, contains no unlawful statements, does not infringe the rights of others, is subject to copyright that is vested exclusively in the author and free of any third party rights, and that any necessary written permissions to quote from other sources have been obtained by the author(s).
3. User/Public Rights
Register's spirit is to disseminate articles published are as free as possible. Under the Creative Commons license, Register permits users to copy, distribute, display, and perform the work for non-commercial purposes only. Users will also need to attribute authors and Register on distributing works in the journal and other media of publications. Unless otherwise stated, the authors are public entities as soon as their articles got published.
4. Rights of Authors
Authors retain all their rights to the published works, such as (but not limited to) the following rights;
Copyright and other proprietary rights relating to the article, such as patent rights,
The right to use the substance of the article in own future works, including lectures and books,
The right to reproduce the article for own purposes,
The right to self-archive the article (please read out deposit policy),
The right to enter into separate, additional contractual arrangements for the non-exclusive distribution of the article's published version (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal (Register: Jurnal Ilmiah Teknologi Sistem Informasi).
5. Co-Authorship
If the article was jointly prepared by more than one author, any authors submitting the manuscript warrants that he/she has been authorized by all co-authors to be agreed on this copyright and license notice (agreement) on their behalf, and agrees to inform his/her co-authors of the terms of this policy. Register will not be held liable for anything that may arise due to the author(s) internal dispute. Register will only communicate with the corresponding author.
6. Royalties
Being an open accessed journal and disseminating articles for free under the Creative Commons license term mentioned, author(s) aware that Register entitles the author(s) to no royalties or other fees.
7. Miscellaneous
Register will publish the article (or have it published) in the journal if the article’s editorial process is successfully completed. Register's editors may modify the article to a style of punctuation, spelling, capitalization, referencing and usage that deems appropriate. The author acknowledges that the article may be published so that it will be publicly accessible and such access will be free of charge for the readers as mentioned in point 3.
Editorial Board
Author Guidelines
Focus and Scope
Online Submissions
Author Fees 
Journal History
