AN INNOVATIVE APPROXIMATE SOLUTION METHOD FOR AN INTEGER PROGRAMMING PROBLEM
DOI:
https://doi.org/10.15588/1607-3274-2025-3-18Keywords:
integer programming problem, initial approximate solution, the interval in which the coordinates of the approximate solution may differ from the optimal solution, innovative approximate solution, computational experimentsAbstract
Context. There are certain methods for finding the optimal solution to integer programming problems. However, these methods cannot solve large-scale problems in real time. Therefore, approximate solutions to these problems that work quickly have been given. It should be noted that the solutions given by these methods often differ significantly from the optimal solution. Therefore, the problem of taking any known approximate solution as the initial solution and improving it further arises.
Objective. Initially, a certain approximate solution is found. Then, based on proven theorems, the coordinates of this solution that do not coincide with the optimal solution are determined. After that, new solutions are found by sequentially changing these coordinates. The one that gives the largest value to the functional among these solutions is accepted as the final solution.
Method. The method we propose in this work is implemented as follows:
First, a certain approximate solution to the problem is established, then the numbers of the coordinates of this solution that do not coincide with the optimal solution are determined. After that, new solutions are established by sequentially assigning values to these coordinates one by one in their intervals. The best of the solutions found in this process is accepted as the final innovative solution.
Results. A problem was solved in order to visually illustrate the quality and effectiveness of the proposed method.
Conclusions. The method we propose in this article cannot give worse results than any approximate solution method, is simple from an algorithmic point of view, is novel, can be easily programmed, and is important for solving real practical problems.
References
Garey M. R., Jhonson D. S. Computers and Intractability : a Guide to the Theory of NP-Completeness. San Francisco, Freeman, 1979, P. 314.
Martello S., Toth P. Knapsack problems: Algorithm and Computers İmplementations. New York, John Wiley & Sons, 1990, P. 296.
Erlebach T., Kellerer H., Pferschy U. Approximating multi-objective knapsack problems, Management Science, 2002, № 48, pp. 1603–1612. DOI: 10.1287/mnsc.48.12.1603.445
Kellerer H., Pferschy U., Pisinger D. Knapsack problems. Berlin, Heidelberg, New-york, SpringerVerlag, 2004, P.546 DOI:10.1007/978-3-540-24777-7
Vazirani V. V. Approximation algorithms. Berlin, Springer, 2001, P. 378. DOI:10.1057/palgrave.jors.2601377
Libura M. Integer programming problems with inexact objective function, Control Cyber, 1980, Vol. 9, No. 4. pp. 189–202.
Bukhtoyarov S. E., Emelichev V. A.Stability aspects of Multicriteria integer linear programming problem, Journal of Applied and Industrial mathematics, 2019, Vоl. (13), №1, pp. 1–10. DOI:10.33048/daio.2019.26.624
Mamedov K. Sh., Mammadli N. O. Two methods for construction of suboptimistic and subpessimistic solutions of the interval problem of mixed-Boolean programming, Radio Electronics, Computer Science, Control, 2018, № 3 (46), pp. 57–67.
Niyazova R. R., Huseynov S. Y. An İnnovative İmproved Approximate Method for the knapsack Problem with coefficients Given in the Interval Form, 8-th International Conference on Control and Optimization with Industrial Applications, Baku, 24–26 August, 2022,
Vol. II, pp. 210–212.
Mammadov K. Sh., Niyazova R. R., Huseynov S. Y. Innovative approximate method for solving Knapsack problems with interval coefficients, International Independent scientific journal, 2022, №44, pp. 8–12. doi.org/10.5281/zenodo.7311206. DOI: 10.15588/1607-
-2018-3-7.
Emelichev V. A., Podkopaev D. Quantitative stability analysis for vector problems of 0–1 programming, Discrete Optimization, 2010, Vol. 7, pp. 48–63. DOI: 10.1016/j.disopt.2010.02.001.
Li W., Liu X., Li H. Generalized solutions to interval linear programmers and related necessary and sufficient optimality conditions, Optimization Methods Software, 2015, Vol. 30, №3, pp. 516–530. DOI: 10.1080/10556788.2014.940948
Mamedov K. Sh., Huseinov S. Y. Method of Constructing Suboptimal Solutions of Integer Programming Problems and Successive Improvement of these Solutions, Automatic Control and Computer Science, 2007, Vol. 41, № 6, pp. 20–31. DOI:
3103/S014641160706003X
Mamedov K. Sh., Mamedova A. H. Ponyatie suboptimisticheskoqo i subpestimisticheskoqo resheniy i postroeniya ix v intervalnoy zadache Bulevoqo programmirovania, Radio Electronics Computer Science Control, 2016, No. 3, pp. 99–108. DOİ: 10.15588/1607-
-2016-3-13
Hifi M., Sadfi S., Sbihi A.. An efficient algorithm for the knapsack sharing problem, Computational Optimization and Applications, 2002, № 23, pp. 27–45. DOI:10.1023/A:1019920507008
Hifi M., Sadfi S. The knapsack sharing problem: An exact algorithm, Journal of Combinatorial Optimization, 2002, № 6, pp. 35–54. DOI:10.1023/A:1013385216761
Hladik M. On strong optimality of interval linear programming, Optimization Letters, 2017, No. 11 (7), pp. 1459–1468. DOI:10.1007/s11590-016-1088-3
Devyaterikova M. V., Kolokolov A. A., Kolosov A. P. Lclass enumeration algorithms for one discrete production planning problem with interval input data, Computers and Operations Research, 2009, Vol. 36, №2, pp. 316– 324. DOI:10.1016/j.cor.2007.10.005
Babayev D. A., Mardanov S. S. Reducing the number of variables in integer and linear programming problems, Computational Optimization and Applications, 1994, № 3, pp. 99–109. DOI: https://doi.org/10.1007/BF01300969.
Basso A., Viscolani B. Linear programming selection of internal financial laws and a knapsack problem, Calcolo, 2000, Vol. 37, № 1, рp. 47–57. DOI:10.1007/s100920050003
Bertisimas D., Demir R. An approximate dynamic programming approach to multidimensional knapsack problems, Management Science, 2002, № 48, pp. 550–565. DOI:10.1287/mnsc.48.4.550.208
Billionnet A. Approximation algorithms for fractional knapsack problems, Operation Research Letters, 2002, № 30, pp. 336–342. DOI:10.1016/S0167- 6377(02)00157-8
Broughan K., Zhu Nan An integer programming problem with a linear programming solution, Journal American Mathematical Monthly, 2000, Vol. 107, № 5, pp. 444– 446. DOI:10.1080/00029890.2000.12005218
Calvin J. M., Leung Y. T. Average-case analysis of a greedy algorithm for the 0–1 knapsack problem, Operation Research Letters, 2003, № 31, pp. 202–210. DOI:10.1016/S0167-6377(02)00222-5
Mamedov K. Sh., Musaeva T. M. Metodi postroeniya priblijennix resheniy mnoqomernoy zadachi o rance i naxojdenie verxney ocenki optimuma, Avtomatika i Vichislitelnaya Texnika, 2004, № 5, pp. 72–82.
Mamedov K. Sh., Niyazova R. R. Innovative Improved Approximate Solution Method For the Integer Knapsack Problem, Error Compression and Computational Experiments, Radio Electronics Computer Science Control, 2024, № 4,pp. 64–74. DOI: 10.15588/1607-3274-2024-4-6
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 K. Sh. Mamedov, R. R. Niyazova
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
