Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування
Розглядається паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування з фіксованою рекурсією, коли випадкові параметри мають скінченний дискретний розподіл ймовірностей. Алгоритм використовує методи недиференційовної оптимізації та орієнтований для реалізації на обчислювальн...
Saved in:
| Published in: | Теорія оптимальних рішень |
|---|---|
| Date: | 2019 |
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/161679 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування / О.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 88-93. — Бібліогр.: 10 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-161679 |
|---|---|
| record_format |
dspace |
| spelling |
Лиховид, О.П. 2019-12-18T13:04:53Z 2019-12-18T13:04:53Z 2019 Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування / О.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 88-93. — Бібліогр.: 10 назв. — укр. 2616-5619 https://nasplib.isofts.kiev.ua/handle/123456789/161679 519.8 Розглядається паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування з фіксованою рекурсією, коли випадкові параметри мають скінченний дискретний розподіл ймовірностей. Алгоритм використовує методи недиференційовної оптимізації та орієнтований для реалізації на обчислювальному кластері у програмному середовищі MPI. Рассматривается параллельный алгоритм решения двухэтапной задачи стохастического программирования с фиксированной рекурсией, когда случайные параметры имеют конечное дискретное распределение вероятностей. Алгоритм использует методы недифференцированой оптимизации и ориентирован для реализации на вычислительном кластере в программной среде MPI. A parallel algorithm for solving two-stage stochastic programming problem with fixed recourse, when random parameters have a finite discrete probability distribution is considered. The algorithm uses methods of non-differential optimization and is oriented for implementation on a computing cluster in the MPI software environment. uk Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування Параллельный алгоритм решения двухэтапной задачи стохастического программирования A parallel algorithm for solving two-stage stochastic programming problem Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування |
| spellingShingle |
Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування Лиховид, О.П. |
| title_short |
Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування |
| title_full |
Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування |
| title_fullStr |
Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування |
| title_full_unstemmed |
Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування |
| title_sort |
паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування |
| author |
Лиховид, О.П. |
| author_facet |
Лиховид, О.П. |
| publishDate |
2019 |
| language |
Ukrainian |
| container_title |
Теорія оптимальних рішень |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Параллельный алгоритм решения двухэтапной задачи стохастического программирования A parallel algorithm for solving two-stage stochastic programming problem |
| description |
Розглядається паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування з фіксованою рекурсією, коли випадкові параметри мають скінченний дискретний розподіл ймовірностей. Алгоритм використовує методи недиференційовної оптимізації та орієнтований для реалізації на обчислювальному кластері у програмному середовищі MPI.
Рассматривается параллельный алгоритм решения двухэтапной задачи стохастического программирования с фиксированной рекурсией, когда случайные параметры имеют конечное дискретное распределение вероятностей. Алгоритм использует методы недифференцированой оптимизации и ориентирован для реализации на вычислительном кластере в программной среде MPI.
A parallel algorithm for solving two-stage stochastic programming problem with fixed recourse, when random parameters have a finite discrete probability distribution is considered. The algorithm uses methods of non-differential optimization and is oriented for implementation on a computing cluster in the MPI software environment.
|
| issn |
2616-5619 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/161679 |
| citation_txt |
Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування / О.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 88-93. — Бібліогр.: 10 назв. — укр. |
| work_keys_str_mv |
AT lihovidop paralelʹniialgoritmrozvâzuvannâdvoetapnoízadačístohastičnogoprogramuvannâ AT lihovidop parallelʹnyialgoritmrešeniâdvuhétapnoizadačistohastičeskogoprogrammirovaniâ AT lihovidop aparallelalgorithmforsolvingtwostagestochasticprogrammingproblem |
| first_indexed |
2025-11-24T02:46:19Z |
| last_indexed |
2025-11-24T02:46:19Z |
| _version_ |
1850840235923996672 |
| fulltext |
88 ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18
ТЕОРІЯ
ОПТИМАЛЬНИХ
РІШЕНЬ
Розглядається паралельний алго-
ритм розв’язування двоетапної
задачі стохастичного програму-
вання з фіксованою рекурсією,
коли випадкові параметри ма-
ють скінченний дискретний роз-
поділ ймовірностей. Алгоритм
використовує методи недиферен-
ційовної оптимізації та орієнто-
ваний для реалізації на обчислю-
вальному кластері у програмному
середовищі MPI.
О.П. Лиховид, 2019
УДК 519.8
О.П. ЛИХОВИД
ПАРАЛЕЛЬНИЙ АЛГОРИТМ
РОЗВ’ЯЗУВАННЯ
ДВОЕТАПНОЇ ЗАДАЧІ
СТОХАСТИЧНОГО ПРОГРАМУВАННЯ
Вступ. Двоетапні моделі стохастичного
програмування використовуються у багатьох
прикладних задачах. Дослідженню цих мо-
делей присвячено багато публікацій (див.,
наприклад, [1 – 5]). Якщо випадкові пара-
метри моделі мають скінченний дискретний
розподіл ймовірностей, задачу можна подати
як детерміновану, і застосовувати весь арсе-
нал методів детермінованої оптимізації. Але
детерміновані моделі, як правило мають ве-
лику розмірність, і тому розробка ефек-
тивних алгоритмів для цих задач продовжує
бути актуальною. Щоб скоротити час пошу-
ку оптимальних розв'язків та досягти розум-
них значень часу обчислень можливо ви-
користання комп’ютерів паралельної архі-
тектури.
В роботі [6] розглядався алгоритм розв’я-
зування двоетапної задачі стохастичного
програмування з фіксованою рекурсією, коли
випадкові параметри мають скінченний
дискретний розподіл ймовірностей. В даній
роботі запропоновано паралельну версію та-
кого алгоритму. Вона орієнтована для реалі-
зації на обчислювальному кластері у програ-
мному середовищі MPI [7]. Слід відмітити,
що хоча в даній роботі розглядається лінійна
модель, підхід до її розв'язання дозволяє роз-
глянути й випадок, коли функціонал задачі
першого етапу є нелінійним, наприклад,
квадратичним чи кусочно-лінійним.
ПАРАЛЕЛЬНИЙ АЛГОРИТМ РОЗВ’ЯЗУВАННЯ ДВОЕТАПНОЇ ЗАДАЧІ …
ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 89
Математична модель задачі. Будемо розглядати лінійну двоетапну задачу
стохастичного програмування з фіксованою рекурсією і з дискретно розподіле-
ними випадковими технологічною матрицею ( )T і вектором правих частин
( )h у випадку, коли невизначеність представлена за допомогою випадкових
змінних , визначених в деякому дискретному ймовірнісному просторі, множи-
ною сценаріїв },1{ L з відповідними ймовірностями 1 }{ , , }.Lp p
Цю модель можна подати у вигляді наступної еквівалентної детермінованої
моделі:
1
min[( , ) ]
, .
, 1, , ,
0.
L
l l l
l
l l l
l
c x p q y
x X
T x Wy h l L
y
(1)
Тут
1nx R , 2n
ly R – змінні першого та другого етапу відповідно;
1nс R , 2n
lq R – коефіцієнти цільових функцій першого та другого етапу
відповідно;
X – опукла множина обмежень першого етапу;
W – детермінована (фіксована) матриця рекурсії.
Очевидно, що задача (1) має блочно-діагональну структуру:
1 1 1
1 1 1
min[( , ) ]
,
,
0, 1, ,
L L L
L L L
l
c x p q y p q y
x X
Wy h T x
Wy h T x
y l L
яка може бути використана при розробці ефективних алгоритмів.
Для розв’язання задачі (1) в [6] розглядався алгоритм, що використовує
схему декомпозиції за змінними [8] з поділом останніх на змінні «першого ета-
О.П. ЛИХОВИД
90 ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18
пу» x та «змінні другого етапу» y . Для врахування обмежень першого етапу
можна використовувати метод негладких штрафних функцій [8].
Використовуючи схему декомпозиції за змінними, зафіксуємо значення
змінних першого етапу xx . Задача (1) розпадається на L лінійних підзадач
зі змінними другого етапу )(xy :
знайти
min
, .
0.
l l l
l l l
l
p q y
Wy h T x
y
(2)
Задачу (2) замінюємо на наступну:
min[ ]
,
0, .
0,
0.
l l l l l
l l l l l
l
l
l
p q y R y R y
Wy y y h T x
y
y
y
(3)
Додаткові змінні
ly ,
ly додані в модель (3) для забезпечення сумісності
обмежень. Символи )0,(, RRRR позначають коефіцієнти штрафу.
Припустимо, що обмеження першого етапу сумісні. Очевидно, якщо в оптима-
льному розв'язку змінні
ll yy , модифікованої задачі (6) дорівнюють нулеві,
то він є також розв’язком початкової задачі.
Нехай )}({ * xu l – оптимальні значення двоїстих змінних для l -ої лінійної
підзадачі. Тоді, виходячи з схеми декомпозиції за змінними, субградієнт у точці
x можна обчислити, використовуючи оптимальні двоїсті змінні )}({ * xu l ,
за формулою:
*
1
( ) ( ) ( ),
L
T
I l l
l
g x g x T u x
(4)
де ( )Ig x – субградієнт у точці x для задачі першого етапу.
Лінійні підзадачі в схемі декомпозиції можна розв’язувати спеціалізованими
симплексними алгоритмами, а для розв’язання координуючої задачі відносно
змінних першого етапу x можна використовувати субградієнтні алгоритми,
наприклад, субградієнтний алгоритм з розтягом простору в напрямку двох пос-
лідовних субградієнтів – r-алгоритм [8].
ПАРАЛЕЛЬНИЙ АЛГОРИТМ РОЗВ’ЯЗУВАННЯ ДВОЕТАПНОЇ ЗАДАЧІ …
ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 91
З формули (4) для обчислення субградієнту видно, що даний алгоритм
розв’язання двохетапної моделі з рекурсією можна досить легко розпаралелити,
розв’язуючи лінійні підзадачі незалежно, і реалізувати обчислення, наприклад,
на кластері.
Паралельний алгоритм розв’язання двохетапної стохастичної задачі
з фіксованою рекурсією. Паралельний алгоритм розв’язання двохетапної сто-
хастичної задачі з фіксованою рекурсією можна представити у вигляді наступної
процедури.
Нехай процес розв'язання задачі проводиться на 1p процесорах. Будемо
використовувати модель “Master-Slave (Coordinator-Worker)”. Один з процесорів
умовно вибирається «провідним» (Master), а решта – «підлеглими» (Slave).
У Master процесорі відбувається розв’язання координуючої задачі, а на p Slave-
процесорах – розв’язання лінійних підзадач.
Master-процесор.
Крок 1. Обчислює поточну точку x згідно процедури субградієнтного
алгоритму.
Крок 2. Обчислення субградієнту в точці x .
Крок 2.1. Генерує параметри для l -ої лінійної підзадачі ( 1, ,l L ): lp , lq ,
l lh T x .
Крок 2.2. Згенеровані параметри для l -ої лінійної підзадачі пересилаються
у вільний Slave-процесор.
Крок 2.3. Очікування відповіді з будь-якого Slave-процесора.
Крок 2.4. Отримання розв’язку )}({ * xu l l -ої лінійної підзадачі i модифіка-
ція субградієнта згідно формули (4).
Крок 2.5. Якщо l L – перехід до кроку 2.1.
Крок 2.6. Якщо ще є активні Slave-процесори – перехід до кроку 2.3.
Крок 3. Якщо виконується деякий критерій зупинки субградієнтного алго-
ритму – посилає сигнал СТОП у всі Slave-процесори і завершує роботу; інакше –
перехід до кроку 1.
Slave-процесор.
Крок 1. Очікує на сигнал з Master-процесорa.
Крок 2. Якщо отримано сигнал СТОП вiд Master-процесорa – завершує
роботу.
О.П. ЛИХОВИД
92 ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18
Крок 3. Отримує значення параметрів лінійної підзадачи lp , lq , l lh T x
i знаходить оптимальні розв’язки )}({ * xu l .
Крок 4. Посилає значення )}({ * xu l у Master-процесор.
Крок 5. Перехід до кроку 1.
Висновки. В роботі розглянуто паралельний алгоритм розв’язання двох-
етапної стохастичної задачі з фіксованою рекурсією та з стохастичними правими
частинами та технологічною матрицею обмежень задачі другого етапу.
Алгоритм орієнтований для реалізації на обчислювальному кластері у програм-
ному середовищі MPI. Описаний підхід дозволяє розглянути й випадок, коли
функціонал задачі першого етапу є нелінійним, наприклад, квадратичним чи
кусочно-лінійним, а також його може бути використано і для інших застосувань.
Вищеописаний паралельний алгоритм реалізовано на мові програмування
С++ у програмному середовищі MPI. Для розв’язання координуючої задачі ви-
користовувався r -алгоритм. Вхідні дані задаються в SMPS форматі [9]. В тепе-
рішній час проводяться обчислювальні експерименти з перевірки ефективності
паралельного алгоритму на кластерному комплексі СКІТ-3 Інституту кібернети-
ки НАН України [10]. В майбутньому планується публікація результатів
обчислювальних експериментів.
А.П. Лиховид
ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ РЕШЕНИЯ ДВУХЭТАПНОЙ ЗАДАЧИ
СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ
Рассматривается параллельный алгоритм решения двухэтапной задачи стохастического про-
граммирования с фиксированной рекурсией, когда случайные параметры имеют конечное
дискретное распределение вероятностей. Алгоритм использует методы недифференцированой
оптимизации и ориентирован для реализации на вычислительном кластере в програм-мной
среде MPI.
O.P. Lykhovyd
A PARALLEL ALGORITHM FOR SOLVING TWO-STAGE STOCHASTIC PROGRAMMING
PROBLEM
A parallel algorithm for solving two-stage stochastic programming problem with fixed recourse,
when random parameters have a finite discrete probability distribution is considered. The algorithm
uses methods of non-differential optimization and is oriented for implementation on a computing
cluster in the MPI software environment.
ПАРАЛЕЛЬНИЙ АЛГОРИТМ РОЗВ’ЯЗУВАННЯ ДВОЕТАПНОЇ ЗАДАЧІ …
ISSN 2616-5619. Теорія оптимальних рішень. 2019, № 18 93
Список літератури
1. Ермольев Ю.М. Методы стохастического программирования. М.: Наука, 1976.
2. Шор Н.З., Бардадым Т.А., Журбенко Н.Г., Лиховид А.П., Стецюк П.И. Использование
методов негладкой оптимизации в задачах стохастического программирования. Киберне-
тика и системный анализ. Киев. Институт кибернетики имени В.М. Глушкова. 1999.
№ 5. С. 33 – 47.
3. Kall P., Wallace S.W. Stochastic programming. Chichester: Wiley, 1994.
4. Mayer J. Stochastic Linear Programming Algorithms: A Comparison Based on a Model Mane-
gement System. Amsterdam: ODP. 1998. 153 p.
5. Ruszczynski A. Decomposition methods in stochastic programming. Math. Prog. 1997. Vol.
79. P. 333 – 353.
6. Лиховид А.П. Использование методов негладкой оптимизации для решения некоторых
классов задач стохастического программирования. Праці міжнародного симпозіуму
“Питання оптимізації обчислень” (ПОО-XXXIII). Київ, 2007. С. 174.
7. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002.
608 с.
8. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. К.:
Наук. думка, 1979. 199 с.
9. Birge J.R., Dempster M.A.H., Gassmann H.I., Gunn E., King A.J., Wallace S.W. A standard
input format for multiperiod stochastic linear programs. Working Paper WP-87-118, IIASA,
Laxenburg, Austria, 1987.
10. Кластерний комплекс Інституту кібернетики. Кластерний комплекс СКІТ.
https://icybcluster.org.ua/.
Одержано 18.03.2019
https://icybcluster.org.ua/
|