Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации
Розглянуто блочні локальні елімінаційні алгоритми розв’язання розріджених задач дискретної оптимізації. Наведено числовий приклад та результати обчислювального експерименту з встановлення реальних обчислювальних можливостей блочних локальних елімінаційних алгоритмів у поєднанні з розв’язувачем SYMPH...
Gespeichert in:
| Datum: | 2013 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Schriftenreihe: | Кибернетика и системный анализ |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.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| id |
irk-123456789-86299 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-862992015-09-13T03:02:04Z Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации Свириденко, А.В. Щербина, О.А. Системный анализ Розглянуто блочні локальні елімінаційні алгоритми розв’язання розріджених задач дискретної оптимізації. Наведено числовий приклад та результати обчислювального експерименту з встановлення реальних обчислювальних можливостей блочних локальних елімінаційних алгоритмів у поєднанні з розв’язувачем 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. 2013 Article Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации / А.В. Свириденко, О.А. Щербина // Кибернетика и системный анализ. — 2013. — Т. 49, № 6. — С. 150-154. — Бібліогр.: 12 назв. — рос. 0023-1274 http://dspace.nbuv.gov.ua/handle/123456789/86299 519.68 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Системный анализ Системный анализ |
| spellingShingle |
Системный анализ Системный анализ Свириденко, А.В. Щербина, О.А. Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации Кибернетика и системный анализ |
| description |
Розглянуто блочні локальні елімінаційні алгоритми розв’язання розріджених задач дискретної оптимізації. Наведено числовий приклад та результати обчислювального експерименту з встановлення реальних обчислювальних можливостей блочних локальних елімінаційних алгоритмів у поєднанні з розв’язувачем SYMPHONY. Аналіз отриманих результатів довів, що при великій кількості блоків і невеликих перемичках-сепараторах між блоками квазіблочної задачі цілочисельного лінійного програмування локальні елімінаційні алгоритми в поєднанні з розв’язувачем для розв’язання підзадач в блоках дозволяють розв’язувати задачі швидче, ніж розглянутий розв’язувач сам по собі при розв’язанні задачі в цілому. Досліджено можливості застосування постоптимального аналізу («теплого» старту) при розв’язанні пакетів задач цілочисельного програмування для відповідних блоків. |
| format |
Article |
| author |
Свириденко, А.В. Щербина, О.А. |
| author_facet |
Свириденко, А.В. Щербина, О.А. |
| author_sort |
Свириденко, А.В. |
| title |
Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации |
| title_short |
Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации |
| title_full |
Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации |
| title_fullStr |
Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации |
| title_full_unstemmed |
Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации |
| title_sort |
блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2013 |
| topic_facet |
Системный анализ |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/86299 |
| citation_txt |
Блочные локальные элиминационные алгоритмы для разреженных задач дискретной оптимизации / А.В. Свириденко, О.А. Щербина // Кибернетика и системный анализ. — 2013. — Т. 49, № 6. — С. 150-154. — Бібліогр.: 12 назв. — рос. |
| series |
Кибернетика и системный анализ |
| work_keys_str_mv |
AT sviridenkoav bločnyelokalʹnyeéliminacionnyealgoritmydlârazrežennyhzadačdiskretnojoptimizacii AT ŝerbinaoa bločnyelokalʹnyeéliminacionnyealgoritmydlârazrežennyhzadačdiskretnojoptimizacii |
| first_indexed |
2025-07-06T13:45:42Z |
| last_indexed |
2025-07-06T13:45:42Z |
| _version_ |
1836905443611377664 |
| fulltext |
ÓÄÊ 519.68
À.Â. ÑÂÈÐÈÄÅÍÊÎ, Î.À. ÙÅÐÁÈÍÀ
ÁËÎ×ÍÛÅ ËÎÊÀËÜÍÛÅ ÝËÈÌÈÍÀÖÈÎÍÍÛÅ ÀËÃÎÐÈÒÌÛ
ÄËß ÐÀÇÐÅÆÅÍÍÛÕ ÇÀÄÀ× ÄÈÑÊÐÅÒÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ
Êëþ÷åâûå ñëîâà: äèñêðåòíàÿ îïòèìèçàöèÿ, ëîêàëüíûå ýëèìèíàöèîííûå àëãî-
ðèòìû, äåêîìïîçèöèÿ, âû÷èñëèòåëüíûé ýêñïåðèìåíò.
ÂÂÅÄÅÍÈÅ
Èñïîëüçîâàíèå ìîäåëåé è àëãîðèòìîâ äèñêðåòíîé îïòèìèçàöèè (ÄÎ) ïîçâîëÿ-
åò ðåøàòü ìíîãèå ïðàêòè÷åñêèå çàäà÷è, êîòîðûå îáû÷íî èìåþò ñïåöèàëüíóþ
ñòðóêòóðó. Ïðè ýòîì ìàòðèöû îãðàíè÷åíèé â çàäà÷àõ áîëüøîé ðàçìåðíîñòè,
êàê ïðàâèëî, ñîäåðæàò áîëüøîå êîëè÷åñòâî íóëåâûõ ýëåìåíòîâ (ñèëüíî «ðàç-
ðåæåíû»), à íåíóëåâûå ìàòðè÷íûå ýëåìåíòû ÷àñòî ãðóïïèðóþòñÿ â áëîêè.
Áëî÷íîñòü ìíîãèõ ïðèêëàäíûõ çàäà÷ ÄÎ îáóñëîâëåíà ñëàáîé ñâÿçíîñòüþ ïîä-
ñèñòåì ìîäåëèðóåìûõ ðåàëüíûõ ñëîæíûõ ñèñòåì.
 íàñòîÿùåå âðåìÿ îñîáåííî àêòóàëüíà ðàçðàáîòêà â ÄÎ äåêîìïîçèöèîííûõ
ïîäõîäîâ, ïîçâîëÿþùèõ ðåøàòü çàäà÷è áîëüøîé ðàçìåðíîñòè [1, 2]. Ïåðñïåêòèâíû-
ìè äåêîìïîçèöèîííûìè ìåòîäàìè, èñïîëüçóþùèìè ðàçðåæåííîñòü ìàòðèöû îãðà-
íè÷åíèé çàäà÷ ÄÎ, ÿâëÿþòñÿ ëîêàëüíûå ýëèìèíàöèîííûå àëãîðèòìû (ËÝÀ) [3],
à äëÿ âûäåëåíèÿ ñïåöèàëüíûõ áëî÷íûõ ñòðóêòóð çàäà÷ ÄÎ — òàêèå ãðàôîâûå äå-
êîìïîçèöèîííûå ïîäõîäû, êàê ìåòîäû äðåâîâèäíîé äåêîìïîçèöèè (ÄÄ) [4–6]. Ñðå-
äè áëî÷íûõ ñòðóêòóð îñîáî âûäåëèì áëî÷íî-äðåâîâèäíóþ ñòðóêòóðó, ÷àñòíûì ñëó-
÷àåì êîòîðîé ÿâëÿåòñÿ êâàçèáëî÷íàÿ ñòðóêòóðà. Çàäà÷è ñ äàííîé ñòðóêòóðîé èñïîëü-
çîâàíû äëÿ ïðîâåäåíèÿ îïèñàííîãî íèæå âû÷èñëèòåëüíîãî ýêñïåðèìåíòà.
Öåëüþ íàñòîÿùåé ðàáîòû ÿâëÿåòñÿ âûÿâëåíèå ðåàëüíûõ âû÷èñëèòåëüíûõ
âîçìîæíîñòåé ëîêàëüíîãî àëãîðèòìà â ñî÷åòàíèè ñ ñîâðåìåííûìè ðåøàòåëÿìè
çàäà÷ ÄÎ.
ËÎÊÀËÜÍÛÅ ÝËÈÌÈÍÀÖÈÎÍÍÛÅ ÀËÃÎÐÈÒÌÛ Â ÇÀÄÀ×ÀÕ
ÄÈÑÊÐÅÒÍÎÉ ÎÏÒÈÌÈÇÀÖÈÈ
 ðàáîòàõ [3, 7] ïðåäëîæåí îáùèé êëàññ ëîêàëüíûõ ýëèìèíàöèîííûõ àëãîðèò-
ìîâ âû÷èñëåíèÿ èíôîðìàöèè [8], èìåþùèõ äåêîìïîçèöèîííûé õàðàêòåð è ïî-
çâîëÿþùèõ íà îñíîâå âû÷èñëåíèÿ ëîêàëüíîé èíôîðìàöèè ïîëó÷àòü ãëîáàëü-
íóþ èíôîðìàöèþ î ðåøåíèè âñåé çàäà÷è. Ëîêàëüíûé ýëèìèíàöèîííûé
àëãîðèòì âû÷èñëÿåò èíôîðìàöèþ î ëîêàëüíûõ ýëåìåíòàõ ñòðóêòóðû çàäà÷è,
êîòîðàÿ çàäàåòñÿ ñòðóêòóðíûì ãðàôîì, çàïèñûâàÿ ëîêàëüíóþ èíôîðìàöèþ îá
ýòèõ ýëåìåíòàõ â âèäå íîâûõ çàâèñèìîñòåé, äîáàâëÿåìûõ ê çàäà÷å, çàòåì ýëè-
ìèíèðóÿ ïðîñìîòðåííûå ýëåìåíòû è èñïîëüçîâàííûå çàâèñèìîñòè.
Ïðîöåäóðà ËÝÀ, òàêèì îáðàçîì, ðàçáèâàåòñÿ íà äâå ÷àñòè: ïðÿìóþ (ýëèìè-
íàöèÿ ýëåìåíòîâ, âû÷èñëåíèå è çàïîìèíàíèå èíôîðìàöèè â âèäå ëîêàëüíûõ ðå-
øåíèé è ïîëó÷åíèå â êîíöå çíà÷åíèÿ êðèòåðèÿ) è îáðàòíóþ (íàõîæäåíèå ãëî-
áàëüíîãî ðåøåíèÿ âñåé çàäà÷è ïî íàéäåííûì â ïðÿìîé ÷àñòè òàáëèöàì ñ ëîêàëü-
íûìè ðåøåíèÿìè, îáåñïå÷èâàþùåãî äîñòèæåíèå êðèòåðèÿ â ïðÿìîé ÷àñòè).
Ïðîöåäóðó ëîêàëüíîé ýëèìèíàöèè ìîæíî ïðèìåíèòü äëÿ ýëèìèíàöèè íå
òîëüêî îòäåëüíûõ ïåðåìåííûõ, íî è ìíîæåñòâ ïåðåìåííûõ â âèäå «áëî÷íîé ýëè-
ìèíàöèè ïåðåìåííûõ» [7, 9], ïîçâîëÿþùåé ýëèìèíèðîâàòü íåñêîëüêî
ïåðåìåííûõ îäíîâðåìåííî.
150 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6
© À.Â. Ñâèðèäåíêî, Î.À. Ùåðáèíà, 2013
Èñïîëüçîâàíèå ìåòîäà ñæàòèÿ ïîäìíîæåñòâ ïåðåìåííûõ â ñóïåðïåðåìåííûå
ïîçâîëÿåò ïîëó÷èòü êîíäåíñèðîâàííûå èëè ñóïåðçàäà÷è ÄÎ, èìåþùèå áîëåå ïðî-
ñòóþ ñòðóêòóðó (íàïðèìåð, äðåâîâèäíóþ), êîòîðûå ìîæíî ðåøèòü ýôôåêòèâíåå.
ÈÑÑËÅÄÎÂÀÍÈÅ ÂÛ×ÈÑËÈÒÅËÜÍÛÕ ÂÎÇÌÎÆÍÎÑÒÅÉ
ËÎÊÀËÜÍÛÕ ÀËÃÎÐÈÒÌÎÂ
Ñðåäè ÷ðåçâû÷àéíî âàæíûõ âîïðîñîâ ïðè èññëåäîâàíèè ýôôåêòèâíîñòè ëî-
êàëüíîãî àëãîðèòìà (ËÀ)1 âûäåëÿåòñÿ ñëåäóþùèé: «Âñåãäà ëè ïðèìåíåíèå ËÀ
â ñî÷åòàíèè ñ íåêîòîðûì àëãîðèòìîì ÄÎ (äëÿ ðåøåíèÿ çàäà÷ â áëîêàõ) ýô-
ôåêòèâíåå èñïîëüçîâàíèÿ óïîìÿíóòîãî àëãîðèòìà?».
Íàðÿäó ñ òåîðåòè÷åñêèì àíàëèçîì îöåíîê ýôôåêòèâíîñòè çíà÷èòåëüíûé èí-
òåðåñ ïðåäñòàâëÿåò ïðîâåäåíèå ñîîòâåòñòâóþùåãî ñðàâíèòåëüíîãî âû÷èñëèòåëü-
íîãî ýêñïåðèìåíòà ËÀ ñ äðóãèìè àëãîðèòìàìè ÄÎ. Ïîíÿòíî, ÷òî ïðîâåäåíèå èñ-
÷åðïûâàþùåãî âû÷èñëèòåëüíîãî ýêñïåðèìåíòà äëÿ ËÀ â ñî÷åòàíèè ñî âñåìè ñó-
ùåñòâóþùèìè àëãîðèòìàìè ÄÎ (èëè, ïî êðàéíåé ìåðå, íàèáîëåå èçâåñòíûìè èç
íèõ) ÷ðåçâû÷àéíî òðóäîåìêèé ïðîöåññ.
Î ôðåéìâîðêå SYMPHONY äëÿ ðåøåíèÿ çàäà÷ ÷àñòè÷íî-öåëî÷èñëåííî-
ãî ëèíåéíîãî ïðîãðàììèðîâàíèÿ. Äëÿ ïðîâåäåíèÿ âû÷èñëèòåëüíîãî ýêñïåðè-
ìåíòà ïî óñòàíîâëåíèþ âû÷èñëèòåëüíûõ âîçìîæíîñòåé ËÝÀ â ñî÷åòàíèè ñ ñî-
âðåìåííûìè ðåøàòåëÿìè ðåàëèçîâàí ËÝÀ ñîâìåñòíî ñ ðåøàòåëåì ôðåéìâîðêà
SYMPHONY [10], ÿâëÿþùåãîñÿ ÷àñòüþ ïðîåêòà COIN-OR [11] è èñïîëüçóþùå-
ãîñÿ äëÿ ïîñëåäîâàòåëüíîãî èëè ïàðàëëåëüíîãî ðåøåíèÿ çàäà÷ ÷àñòè÷íî-öåëî-
÷èñëåííîãî ëèíåéíîãî ïðîãðàììèðîâàíèÿ (×ÖËÏ). Äàííûé ôðåéìâîðê áûë âû-
áðàí èç-çà îòêðûòîãî èñõîäíîãî êîäà, ïåðåíîñèìîñòè, à òàêæå íàëè÷èÿ òåõíîëî-
ãèè «òåïëîãî» ñòàðòà (warm start), ðåàëèçóþùåé ïîñòîïòèìàëüíûé àíàëèç (ÏÀ)
çàäà÷ ÖËÏ.
Îòìåòèì, ÷òî SYMPHOMY íå èìååò ñîáñòâåííîãî ðåøàòåëÿ çàäà÷ ËÏ, íî
ïîçâîëÿåò ðàáîòàòü ñ òàêèìè ðåøàòåëÿìè ËÏ, êàê Clp, Cplex, Xpress, èñïîëüçóÿ
Osi-èíòåðôåéñ. Êðîìå òîãî, SYMPHONY ïîääåðæèâàåò ñïåöèàëèçèðîâàííûå ðå-
øàòåëè äëÿ çàäà÷è êîììèâîÿæåðà, çàäà÷è ìàðøðóòèçàöèè, ðàçáèåíèÿ è äð.
Òåõíîëîãèÿ «òåïëîãî» ñòàðòà äëÿ ðåàëèçàöèè ïîñòîïòèìàëüíîãî àíàëè-
çà. Îïèñûâàåìàÿ òåõíîëîãèÿ èñïîëüçóåòñÿ äëÿ ðåàëèçàöèè ïðîöåäóðû ÏÀ òàêè-
ìè ñîâðåìåííûìè ðåøàòåëÿìè, êàê Gurobi, SCIP, CBC, SYMPHONY è äð. Â [12]
èññëåäîâàíû âîçìîæíîñòè òåõíîëîãèè òåïëîãî ñòàðòà èç ôðåéìâîðêà
SYMPHONY äëÿ óìåíüøåíèÿ ïåðåáîðà ïðè ðåøåíèè ïîäçàäà÷, ãåíåðèðóåìûõ
âû÷èñëèòåëüíîé ñõåìîé ËÝÀ.
 ôðåéìâîðêå SYMPHONY òåïëûé ñòàðò ðåàëèçîâàí íà îñíîâå êîìïàêòíîãî
îïèñàíèÿ äåðåâà ïîèñêà â ìîìåíò ïðèîñòàíîâêè âû÷èñëåíèé. Èñïîëüçóÿ åãî, ïîëü-
çîâàòåëü ìîæåò ñîõðàíÿòü ïðîìåæóòî÷íûå âû÷èñëåíèÿ íà äèñêå, à â äàëüíåéøåì
ïðèìåíÿòü èõ, ïåðåçàïóñêàÿ ïðîöåññ âû÷èñëåíèé ïîñëå èçìåíåíèÿ äàííûõ çàäà÷è.
Îòìåòèì, ÷òî èñïîëüçîâàíèå ýòîé ïðîöåäóðû ÏÀ íå âñåãäà ãàðàíòèðóåò ïî-
ëîæèòåëüíûé ðåçóëüòàò.  ñëó÷àå SYMPHONY áûëî çàìå÷åíî, ÷òî, êàê ïðàâèëî,
ïðîöåäóðà òåïëîãî ñòàðòà ðàáîòàåò ëó÷øå âñåãî ïðè íåçíà÷èòåëüíîì èçìåíåíèè
óñëîâèé çàäà÷è.
Àíàëèç ðåçóëüòàòîâ âû÷èñëèòåëüíîãî ýêñïåðèìåíòà. Âñå âû÷èñëåíèÿ
ïðîâîäèëèñü íà áàçå ïðîöåññîðà Intel Core 2 Duo @ 2.66 GHz, 2 GB ÎÇÓ è îïåðà-
öèîííîé ñèñòåìû Linux, âåðñèÿ ÿäðà 2.6.35-24-generic.  êà÷åñòâå ðàáî÷åãî ôðåéì-
âîðêà äëÿ ðåàëèçàöèè ËÝÀ èñïîëüçîâàëàñü áèáëèîòåêà SYMPHONY âåðñèè 5.4.1.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6 151
1 Çäåñü ïîä ËÀ ïîíèìàåòñÿ ëîêàëüíûé àëãîðèòì äåêîìïîçèöèè, ÿâëÿþùèéñÿ ÷àñòíîé ðåàëèçàöèåé
ËÝÀ.
Ðåçóëüòàòû âû÷èñëèòåëüíîãî ýêñïåðèìåíòà ïðèâåäåíû â òàáë. 1, â êîòîðîé n,
m è k — ñîîòâåòñòâåííî ÷èñëî ïåðåìåííûõ, îãðàíè÷åíèé è áëîêîâ, s — ðàçìåð
ïåðåìû÷êè, ìèíèìàëüíîå âðåìÿ ðåøåíèÿ çàäà÷è ïðè èñïîëüçîâàíèè ñîîòâåòñòâó-
þùåãî àëãîðèòìà âûäåëåíî æèðíûì øðèôòîì.
152 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6
Ò à á ë è ö à 1
Íîìåð
çàäà÷è
Ïàðàìåòðû çàäà÷
Âðåìÿ ðåøåíèÿ èñêóññòâåííî
ñãåíåðèðîâàííûõ çàäà÷ ñ êâàçèáëî÷íîé
ñòðóêòóðîé ñ èñïîëüçîâàíèåì ðåøàòåëåé, ìèí
n m k s SYMPHONY SYMPHONY + ËÝÀ SYMPHONY + ËÝÀ + ÏÀ
1 180 12 6 1 9.503 0.028 0.026
2 180 12 6 2 3.019 0.046 0.047
3 180 12 6 4 1.164 0.493 0.485
4 180 12 6 5 0.084 5.667 5.295
5 180 12 6 6 0.186 12.4289 14.444
6 180 12 6 6 2.7167 5.321 5.057
7 240 24 12 3 3.831 0.16 0.158
8 240 24 12 3 6.958 0.290 0.289
9 240 24 12 3 1.057 0.133 0.132
10 240 24 12 3 2.751 0.157 0.162
11 240 24 12 4 1.45 0.477 0.475
12 240 20 10 4 22.143 0.513 0.517
13 240 6 3 6 0.172 8.361 7.488
14 240 6 3 6 1.07 8.447 7.688
15 240 16 8 6 5.463 11.422 11.681
16 240 16 8 6 3.667 12.046 11.572
17 320 12 6 6 31.065 24.313 24.249
18 320 12 6 6 44.556 21.534 21.636
19 320 16 8 1 9.605 0.025 0.024
20 320 20 10 1 24.435 0.029 0.026
21 320 20 10 2 18.464 0.092 0.093
22 320 20 10 3 31 0.289 0.289
23 320 20 10 6 13.178 15.519 15.146
24 320 20 10 6 23.853 14.327 14.043
25 320 40 20 1 3.943 0.016 0.015
26 320 40 20 2 2.519 0.048 0.049
27 320 40 20 3 3.382 0.158 0.157
28 320 40 20 3 1.807 0.182 0.181
29 420 6 3 1 2.965 0.04 0.041
30 420 6 3 1 4.686 0.057 0.056
31 420 6 3 2 5.69 0.156 0.157
32 420 6 3 2 15.116 0.251 0.25
33 420 6 3 3 4.201 0.682 0.678
34 420 6 3 3 10.211 0.899 0.893
35 420 6 3 4 3.703 1.922 1.933
36 420 6 3 4 4.101 1.865 1.878
37 420 6 3 5 17.812 16.154 16.201
38 420 6 3 5 19.145 2.696 2.66
39 420 6 3 5 6.185 2.571 2.584
40 420 6 3 6 11.544 12.111 12.112
41 420 6 3 6 9.7 23.254 23.234
42 420 60 30 1 5.51 0.019 0.018
43 420 60 30 2 14.414 0.066 0.065
44 500 50 25 1 90.02 0.021 0.022
Îïèñàíèå òåñòîâûõ çàäà÷.  õîäå ýêñïåðèìåíòà âñå òåñòîâûå çàäà÷è ÖËÏ
ñ áèíàðíûìè ïåðåìåííûìè èìåëè èñêóññòâåííî ñãåíåðèðîâàííóþ êâàçèáëî÷íóþ
ñòðóêòóðó, à âñå áëîêè â îòäåëüíî âçÿòîé çàäà÷å — îäèíàêîâîå êîëè÷åñòâî ïåðå-
ìåííûõ, à òàêæå îäèíàêîâîå ÷èñëî ïåðåìåííûõ â ïåðåìû÷êàõ ìåæäó íèìè. Âå-
ëè÷èíà ïåðåìû÷åê âàðüèðîâàëàñü äëÿ îäíèõ è òåõ æå ïàðàìåòðîâ çàäà÷è, ÷òî íå-
îáõîäèìî äëÿ îöåíêè âëèÿíèÿ ÏÀ íà âðåìÿ ðåøåíèÿ çàäà÷è ïðè óâåëè÷åíèè ðàç-
ìåðà ïåðåìû÷åê.
Òåñòîâûå çàäà÷è ÖËÏ ãåíåðèðîâàëèñü ïî çàäàííîìó ÷èñëó ïåðåìåííûõ,
îãðàíè÷åíèé è ðàçìåðó ïåðåìû÷åê ìåæäó áëîêàìè. Èñõîäÿ èç êîëè÷åñòâà ïåðå-
ìåííûõ è îãðàíè÷åíèé, âû÷èñëÿëèñü ðàçìåðû è ÷èñëî áëîêîâ. Äàëåå ñ ïîìîùüþ
äàò÷èêà ñëó÷àéíûõ ÷èñåë ãåíåðèðîâàëèñü êîýôôèöèåíòû öåëåâîé ôóíêöèè, à òàê-
æå êîýôôèöèåíòû ìàòðèöû îãðàíè÷åíèé è ïðàâûõ ÷àñòåé äëÿ êàæäîãî áëîêà.
Êàæäàÿ òåñòîâàÿ çàäà÷à ðåøàëàñü ñ ïîìîùüþ òðåõ àëãîðèòìîâ: áàçîâîãî ðå-
øàòåëÿ SYMPHONY äëÿ çàäà÷ ×ÖËÏ, èñïîëüçóþùåãî èíòåðôåéñ OsiSym; ËÝÀ
â ñî÷åòàíèè ñ ðåøàòåëåì SYMPHONY, ñ ïîìîùüþ êîòîðîãî ðåøàëèñü âûäåëåí-
íûå ïîäçàäà÷è, ñîîòâåòñòâóþùèå áëîêàì; ËÝÀ â ñî÷åòàíèè ñ ðåøàòåëåì
SYMPHONY ñ ïîääåðæêîé ÏÀ (ïðèìåíÿëàñü îïèñàííàÿ òåõíîëîãèÿ òåïëîãî
ñòàðòà). Âî âñåõ òðåõ ñëó÷àÿõ ðåøàòåëü SYMPHONY èñïîëüçîâàë ïðåïðîöåññèíã
(preprocessing).
 õîäå ïðîâåäåííîãî âû÷èñëèòåëüíîãî ýêñïåðèìåíòà áûëî óñòàíîâëåíî ÿâ-
íîå ïðåèìóùåñòâî ËÝÀ â ñî÷åòàíèè ñ ðåøàòåëåì SYMPHONY ïðè ðåøåíèè êâà-
çèáëî÷íûõ çàäà÷ ñ íåáîëüøèìè ïåðåìû÷êàìè ïî ñðàâíåíèþ ñ ðåøàòåëåì
SYMPHONY (ñì. òàáë. 1), à òàêæå îáíàðóæåíî, ÷òî ïðè óâåëè÷åíèè ðàçìåðà ïå-
ðåìû÷åê â çàäà÷àõ ñ îäíèì è òåì æå êîëè÷åñòâîì ïåðåìåííûõ è ðàçìåðîì áëî-
êîâ ËÝÀ ñòàíîâèëñÿ ìåíåå ýôôåêòèâíûì âñëåäñòâèå óâåëè÷åíèÿ îáúåìà ïåðåáî-
ðà ïðè ðåøåíèè ïîäçàäà÷ â áëîêàõ. Äëÿ ïîâûøåíèÿ ýôôåêòèâíîñòè ËÝÀ ïðè ðå-
øåíèè òàêèõ çàäà÷ èñïîëüçîâàëàñü òåõíîëîãèÿ òåïëîãî ñòàðòà. Ïîñêîëüêó çàäà÷è
ÖËÏ, ñîîòâåòñòâóþùèå îäíîìó è òîìó æå áëîêó, äëÿ ðàçíûõ çíà÷åíèé ïåðåìåí-
íûõ â ïåðåìû÷êàõ îòëè÷àþòñÿ îäíà îò äðóãîé ëèøü ïðàâûìè ÷àñòÿìè, ïðåäïîëà-
ãàëîñü, ÷òî èñïîëüçîâàíèå òåõíîëîãèè òåïëîãî ñòàðòà ïîìîæåò íå ðåøàòü ïîë-
íîñòüþ êàæäóþ çàäà÷ó ïðè ïåðåáîðå çíà÷åíèé ïåðåìåííûõ èç ïåðåìû÷åê,
à ëèøü ÷àñòè÷íî, èñïîëüçóÿ èíôîðìàöèþ, ïîëó÷åííóþ ïðè ðåøåíèè äðóãèõ çà-
äà÷, ÷òî äîëæíî áûëî â ïðèíöèïå óâåëè÷èòü ïðîèçâîäèòåëüíîñòü ËÝÀ. Îäíàêî
ðåçóëüòàò ýêñïåðèìåíòà îêàçàëñÿ íåîäíîçíà÷íûì. Âðåìÿ ðåøåíèÿ áîëüøèíñòâà
çàäà÷ áûëî ïðàêòè÷åñêè ñîïîñòàâèìî êàê ñ èñïîëüçîâàíèåì òåõíîëîãèè òåïëîãî
ñòàðòà, òàê è áåç íåãî. Íî äëÿ íåêîòîðûõ òåñòîâûõ çàäà÷ äàííàÿ òåõíîëîãèÿ áûëà
ýôôåêòèâíîé (ñì. òàáë. 1, çàäà÷è 7, 17, 24), à äëÿ äðóãèõ — îêàçàëàñü
íåýôôåêòèâíîé (ñì. òàáë. 1, çàäà÷è 5, 15, 40), ÷òî âûðàæàëîñü â ïîâûøåíèè
è ñîîòâåòñòâåííî ñíèæåíèè ïðîèçâîäèòåëüíîñòè ËÝÀ è èçìåðÿëîñü âðåìåíåì,
çàòðà÷èâàåìûì íà ðåøåíèå çàäà÷è.
ÇÀÊËÞ×ÅÍÈÅ
Âûÿâëåíû ðåàëüíûå âû÷èñëèòåëüíûå âîçìîæíîñòè áëî÷íûõ ëîêàëüíûõ ýëèìè-
íàöèîííûõ àëãîðèòìîâ (ËÝÀ) â ñî÷åòàíèè ñ ðåøàòåëåì SYMPHONY ïðè ðåøå-
íèè êâàçèáëî÷íûõ çàäà÷ öåëî÷èñëåííîãî ëèíåéíîãî ïðîãðàììèðîâàíèÿ (ÖËÏ).
 õîäå ïðîâåäåííîãî âû÷èñëèòåëüíîãî ýêñïåðèìåíòà óñòàíîâëåíî ÿâíîå ïðåè-
ìóùåñòâî ËÝÀ â ñî÷åòàíèè ñ ðåøàòåëåì SYMPHONY ïðè ðåøåíèè çàäà÷ ñ íå-
áîëüøèìè ïåðåìû÷êàìè ïî ñðàâíåíèþ ñ ðåøàòåëåì SYMPHONY, à òàêæå îáíà-
ðóæåíî, ÷òî ïðè óâåëè÷åíèè ðàçìåðà ïåðåìû÷åê â çàäà÷àõ ñ îäíèì è òåì æå
êîëè÷åñòâîì ïåðåìåííûõ è ðàçìåðîì áëîêîâ ËÝÀ ñòàíîâèëñÿ ìåíåå ýôôåêòèâ-
íûì âñëåäñòâèå óâåëè÷åíèÿ îáúåìà ïåðåáîðà ïðè ðåøåíèè ïîäçàäà÷ â áëîêàõ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6 153
Äëÿ ïîâûøåíèÿ ýôôåêòèâíîñòè ËÝÀ ïðè ðåøåíèè òàêèõ çàäà÷ èñïîëüçîâàëàñü
òåõíîëîãèÿ òåïëîãî ñòàðòà, ðåàëèçóþùàÿ ïîñòîïòèìàëüíûé àíàëèç.
Ïåðñïåêòèâíî íå òîëüêî ïðîäîëæåíèå äàííîãî èññëåäîâàíèÿ, íî è àíàëèç
âîçìîæíîñòè òåõíîëîãèè ïîñòîïòèìàëüíîãî àíàëèçà, ïðåäîñòàâëÿåìîé äðóãèìè
ñîâðåìåííûìè ðåøàòåëÿìè. Ïðåäñòàâëÿåò òàêæå èíòåðåñ èçó÷åíèå âû÷èñëèòåëü-
íûõ âîçìîæíîñòåé ëîêàëüíûõ àëãîðèòìîâ ïðè ðåøåíèè ðàçðåæåííûõ çàäà÷ ÖËÏ
èç ðåàëüíûõ ïðèëîæåíèé.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. X u J . , J i a o F . , B e r g e r B . A tree-decomposition approach to protein structure prediction //
Proc. of Comput. Syst. Bioinform. Conf. — 2005. — P. 247–256.
2. K h a n a f e r A . , C l a u t i a u x F . , T a l b i E l - G . Tree-decomposition based heuristics for the
two-dimensional bin packing problem with conflicts // Comput. & OR. — 2012. — 39, N 1. —
P. 54–63.
3. Ù å ð á è í à Î . À . Ëîêàëüíûå ýëèìèíàöèîííûå àëãîðèòìû ðåøåíèÿ ðàçðåæåííûõ äèñêðåò-
íûõ çàäà÷ // Æóðí. âû÷èñë. ìàòåìàòèêè è ìàò. ôèçèêè. — 2008. — 48, ¹ 1. — Ñ. 161–177.
4. Ù å ð á è í à Î . À . Äðåâîâèäíàÿ äåêîìïîçèöèÿ è çàäà÷è äèñêðåòíîé îïòèìèçàöèè (îáçîð)
// Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2007. — ¹ 4. — Ñ. 102–118.
5. B o d l a e n d e r H . L . , K o s t e r A . M . C . A . Treewidth computations I: Upper bounds // Inform.
and Comput. — 2010. — 208. — P. 259–275.
6. Á û ê î â à   . Âû÷èñëèòåëüíûå àñïåêòû äðåâîâèäíîé øèðèíû ãðàôà // Ïðèêë. äèñêðåò.
ìàòåìàòèêà. — 2011. — ¹ 3(13). — Ñ. 65–79.
7. S h c h e r b i n a O . Graph-based local elimination algorithms in discrete optimization // Foundations
of Computational Intelligence, Vol. 3. Global Optimization Series: Studies in Computational Intelli-
gence, Vol. 203 / A. Abraham, A.-E. Hassanien, P. Siarry, A. Engelbrecht (eds.). — Berlin; Heidel-
berg: Springer, 2009. — P. 235–266.
8. Æ ó ð à â ë å â Þ . È . Èçáðàííûå íàó÷íûå òðóäû. — Ì.: Ìàãèñòð, 1998. — 420 ñ.
9. B e r t e l e U . , B r i o s c h i F . Nonserial dynamic programming. — New York: Acad. press, 1972.
— 235 p.
10. https://projects.coin-or.org/SYMPHONY.
11. http://www.coin-or.org.
12. http://coin-or.org/download/source/SYMPHONY/.
Ïîñòóïèëà 01.11.2011
Ïîñëå äîðàáîòêè 03.12.2012
154 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 6
|