Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации
Розглянуто блочні локальні елімінаційні алгоритми розв’язання розріджених задач дискретної оптимізації. Наведено числовий приклад та результати обчислювального експерименту з встановлення реальних обчислювальних можливостей блочних локальних елімінаційних алгоритмів у поєднанні з розв’язувачем SYMPH...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2013 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/86299 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации / А.В. Свириденко, О.А. Щербина // Кибернетика и системный анализ. — 2013. — Т. 49, № 6. — С. 150-154. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862553350661210112 |
|---|---|
| author | Свириденко, А.В. Щербина, О.А. |
| author_facet | Свириденко, А.В. Щербина, О.А. |
| citation_txt | Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации / А.В. Свириденко, О.А. Щербина // Кибернетика и системный анализ. — 2013. — Т. 49, № 6. — С. 150-154. — Бібліогр.: 12 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Розглянуто блочні локальні елімінаційні алгоритми розв’язання розріджених задач дискретної оптимізації. Наведено числовий приклад та результати обчислювального експерименту з встановлення реальних обчислювальних можливостей блочних локальних елімінаційних алгоритмів у поєднанні з розв’язувачем SYMPHONY. Аналіз отриманих результатів довів, що при великій кількості блоків і невеликих перемичках-сепараторах між блоками квазіблочної задачі цілочисельного лінійного програмування локальні елімінаційні алгоритми в поєднанні з розв’язувачем для розв’язання підзадач в блоках дозволяють розв’язувати задачі швидче, ніж розглянутий розв’язувач сам по собі при розв’язанні задачі в цілому. Досліджено можливості застосування постоптимального аналізу («теплого» старту) при розв’язанні пакетів задач цілочисельного програмування для відповідних блоків.
Block local elimination algorithms for solving sparse discrete optimization problems are considered. The numerical example is provided. The benchmarking is done in order to define real computational capabilities of block elimination algorithms combined with SYMPHONY solver. The analysis of the results shows that for sufficiently large number of blocks and rather small size of separators between the blocks for staircase integer linear programming problem, the local elimination algorithms in combination with a solver for solving subproblems in blocks allow a much faster solution of such problems than the solver itself used to solve the whole problem. The capabilities of the postoptimal analysis (warm starting) are also considered for solving packages of integer linear programming problems for the corresponding blocks.
|
| first_indexed | 2025-11-25T21:07:17Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-86299 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-25T21:07:17Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Свириденко, А.В. Щербина, О.А. 2015-09-12T18:05:38Z 2015-09-12T18:05:38Z 2013 Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации / А.В. Свириденко, О.А. Щербина // Кибернетика и системный анализ. — 2013. — Т. 49, № 6. — С. 150-154. — Бібліогр.: 12 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/86299 519.68 Розглянуто блочні локальні елімінаційні алгоритми розв’язання розріджених задач дискретної оптимізації. Наведено числовий приклад та результати обчислювального експерименту з встановлення реальних обчислювальних можливостей блочних локальних елімінаційних алгоритмів у поєднанні з розв’язувачем SYMPHONY. Аналіз отриманих результатів довів, що при великій кількості блоків і невеликих перемичках-сепараторах між блоками квазіблочної задачі цілочисельного лінійного програмування локальні елімінаційні алгоритми в поєднанні з розв’язувачем для розв’язання підзадач в блоках дозволяють розв’язувати задачі швидче, ніж розглянутий розв’язувач сам по собі при розв’язанні задачі в цілому. Досліджено можливості застосування постоптимального аналізу («теплого» старту) при розв’язанні пакетів задач цілочисельного програмування для відповідних блоків. Block local elimination algorithms for solving sparse discrete optimization problems are considered. The numerical example is provided. The benchmarking is done in order to define real computational capabilities of block elimination algorithms combined with SYMPHONY solver. The analysis of the results shows that for sufficiently large number of blocks and rather small size of separators between the blocks for staircase integer linear programming problem, the local elimination algorithms in combination with a solver for solving subproblems in blocks allow a much faster solution of such problems than the solver itself used to solve the whole problem. The capabilities of the postoptimal analysis (warm starting) are also considered for solving packages of integer linear programming problems for the corresponding blocks. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации Блочні локальні елімінаційні алгоритми для розріджених задач дискретної оптимізації Block local elimination algorithms for solving sparse discrete optimization problems Article published earlier |
| spellingShingle | Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации Свириденко, А.В. Щербина, О.А. Системный анализ |
| title | Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации |
| title_alt | Блочні локальні елімінаційні алгоритми для розріджених задач дискретної оптимізації Block local elimination algorithms for solving sparse discrete optimization problems |
| title_full | Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации |
| title_fullStr | Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации |
| title_full_unstemmed | Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации |
| title_short | Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации |
| title_sort | блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/86299 |
| work_keys_str_mv | AT sviridenkoav bločnyelokalʹnyeéliminacionnyealgoritmydlârazrežennyhzadačdiskretnoioptimizacii AT ŝerbinaoa bločnyelokalʹnyeéliminacionnyealgoritmydlârazrežennyhzadačdiskretnoioptimizacii AT sviridenkoav bločnílokalʹníelímínacíiníalgoritmidlârozrídženihzadačdiskretnoíoptimízacíí AT ŝerbinaoa bločnílokalʹníelímínacíiníalgoritmidlârozrídženihzadačdiskretnoíoptimízacíí AT sviridenkoav blocklocaleliminationalgorithmsforsolvingsparsediscreteoptimizationproblems AT ŝerbinaoa blocklocaleliminationalgorithmsforsolvingsparsediscreteoptimizationproblems |