РОЗВ’ЯЗАННЯ ЗАДАЧІ ПРО РАНЕЦЬ: ПОСТОПТИМАЛЬНИЙ АНАЛІЗ ТА МЕТОД ГІЛОК І МЕЖ
It is proposed an algorithm of postoptimality analysis for determining exact solutions of family of knapsack problems including an initial problem. Computational experiment shows that the middle time of solving the problem of family at least 10 times less than time of solving initial problem by bran...
Gespeichert in:
| Datum: | 2025 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
2025
|
| Online Zugang: | https://jais.net.ua/index.php/files/article/view/609 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems of Control and Informatics |
Institution
Problems of Control and Informatics| id |
oai:ojs2.jais.net.ua:article-609 |
|---|---|
| record_format |
ojs |
| spelling |
oai:ojs2.jais.net.ua:article-6092025-10-08T16:58:06Z SOLVING KNAPSACK PROBLEM: POSTOPTIMALITY ANALYSIS AND BRANCH AND BOUND METHOD РОЗВ’ЯЗАННЯ ЗАДАЧІ ПРО РАНЕЦЬ: ПОСТОПТИМАЛЬНИЙ АНАЛІЗ ТА МЕТОД ГІЛОК І МЕЖ Mikhailyuk, V.A. It is proposed an algorithm of postoptimality analysis for determining exact solutions of family of knapsack problems including an initial problem. Computational experiment shows that the middle time of solving the problem of family at least 10 times less than time of solving initial problem by branch and bound method. Запропоновано алгоритм постоптимального аналізу для визначення точних розв’язків сімейства споріднених задач про ранець, до яких належить вихідна задача. Обчислювальний експеримент показує, що середній час розв’язання задачі сімейства принаймні в десять разів менший за час розв’язання вихідної задачі методом гілок і меж. V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2025-10-02 Article Article application/pdf https://jais.net.ua/index.php/files/article/view/609 10.1615/JAutomatInfScien.v43.i11.50 Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; Том 56 № 6 (2011): Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; 43-51 International Scientific Technical Journal "Problems of Control and Informatics; Том 56 № 6 (2011): International Scientific and Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 43-51 International Scientific Technical Journal "Problems of Control and Informatics"; Vol. 56 No. 6 (2011): International Scientific and Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 43-51 2786-6505 2786-6491 en https://jais.net.ua/index.php/files/article/view/609/678 https://creativecommons.org/licenses/by-nc-nd/4.0 |
| institution |
Problems of Control and Informatics |
| baseUrl_str |
|
| datestamp_date |
2025-10-08T16:58:06Z |
| collection |
OJS |
| language |
English |
| format |
Article |
| author |
Mikhailyuk, V.A. |
| spellingShingle |
Mikhailyuk, V.A. РОЗВ’ЯЗАННЯ ЗАДАЧІ ПРО РАНЕЦЬ: ПОСТОПТИМАЛЬНИЙ АНАЛІЗ ТА МЕТОД ГІЛОК І МЕЖ |
| author_facet |
Mikhailyuk, V.A. |
| author_sort |
Mikhailyuk, V.A. |
| title |
РОЗВ’ЯЗАННЯ ЗАДАЧІ ПРО РАНЕЦЬ: ПОСТОПТИМАЛЬНИЙ АНАЛІЗ ТА МЕТОД ГІЛОК І МЕЖ |
| title_short |
РОЗВ’ЯЗАННЯ ЗАДАЧІ ПРО РАНЕЦЬ: ПОСТОПТИМАЛЬНИЙ АНАЛІЗ ТА МЕТОД ГІЛОК І МЕЖ |
| title_full |
РОЗВ’ЯЗАННЯ ЗАДАЧІ ПРО РАНЕЦЬ: ПОСТОПТИМАЛЬНИЙ АНАЛІЗ ТА МЕТОД ГІЛОК І МЕЖ |
| title_fullStr |
РОЗВ’ЯЗАННЯ ЗАДАЧІ ПРО РАНЕЦЬ: ПОСТОПТИМАЛЬНИЙ АНАЛІЗ ТА МЕТОД ГІЛОК І МЕЖ |
| title_full_unstemmed |
РОЗВ’ЯЗАННЯ ЗАДАЧІ ПРО РАНЕЦЬ: ПОСТОПТИМАЛЬНИЙ АНАЛІЗ ТА МЕТОД ГІЛОК І МЕЖ |
| title_sort |
розв’язання задачі про ранець: постоптимальний аналіз та метод гілок і меж |
| title_alt |
SOLVING KNAPSACK PROBLEM: POSTOPTIMALITY ANALYSIS AND BRANCH AND BOUND METHOD |
| description |
It is proposed an algorithm of postoptimality analysis for determining exact solutions of family of knapsack problems including an initial problem. Computational experiment shows that the middle time of solving the problem of family at least 10 times less than time of solving initial problem by branch and bound method. |
| publisher |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine |
| publishDate |
2025 |
| url |
https://jais.net.ua/index.php/files/article/view/609 |
| work_keys_str_mv |
AT mikhailyukva solvingknapsackproblempostoptimalityanalysisandbranchandboundmethod AT mikhailyukva rozvâzannâzadačíproranecʹpostoptimalʹnijanalíztametodgílokímež |
| first_indexed |
2025-10-30T02:49:28Z |
| last_indexed |
2025-10-30T02:49:28Z |
| _version_ |
1847373404370370560 |