Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування
Розглядається паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування з фіксованою рекурсією, коли випадкові параметри мають скінченний дискретний розподіл ймовірностей. Алгоритм використовує методи недиференційовної оптимізації та орієнтований для реалізації на обчислювальн...
Збережено в:
| Дата: | 2019 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Назва видання: | Теорія оптимальних рішень |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/161679 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування / О.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 88-93. — Бібліогр.: 10 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-161679 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1616792019-12-19T01:25:16Z Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування Лиховид, О.П. Розглядається паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування з фіксованою рекурсією, коли випадкові параметри мають скінченний дискретний розподіл ймовірностей. Алгоритм використовує методи недиференційовної оптимізації та орієнтований для реалізації на обчислювальному кластері у програмному середовищі 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. 2019 Article Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування / О.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 88-93. — Бібліогр.: 10 назв. — укр. 2616-5619 http://dspace.nbuv.gov.ua/handle/123456789/161679 519.8 uk Теорія оптимальних рішень Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Ukrainian |
| description |
Розглядається паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування з фіксованою рекурсією, коли випадкові параметри мають скінченний дискретний розподіл ймовірностей. Алгоритм використовує методи недиференційовної оптимізації та орієнтований для реалізації на обчислювальному кластері у програмному середовищі MPI. |
| format |
Article |
| author |
Лиховид, О.П. |
| spellingShingle |
Лиховид, О.П. Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування Теорія оптимальних рішень |
| author_facet |
Лиховид, О.П. |
| author_sort |
Лиховид, О.П. |
| title |
Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування |
| title_short |
Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування |
| title_full |
Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування |
| title_fullStr |
Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування |
| title_full_unstemmed |
Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування |
| title_sort |
паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2019 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/161679 |
| citation_txt |
Паралельний алгоритм розв’язування двоетапної задачі стохастичного програмування / О.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2019. — № 18. — С. 88-93. — Бібліогр.: 10 назв. — укр. |
| series |
Теорія оптимальних рішень |
| work_keys_str_mv |
AT lihovidop paralelʹnijalgoritmrozvâzuvannâdvoetapnoízadačístohastičnogoprogramuvannâ |
| first_indexed |
2025-07-14T14:16:07Z |
| last_indexed |
2025-07-14T14:16:07Z |
| _version_ |
1837632132224122880 |
| 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/
|