Проект LiFe
 Алгоритмы и методы решения задач линейного программирования
большой размерности в условиях неполных, противоречивых и изменяющихся
исходных данных
 

Проблематика
 

Участники
 

Гранты
 

Публикации
 

Апробация
 

Отчеты
 

ЛП-библиография
 

Программы
 

Диссертации
 

Web-ресурсы
 

 

  Rambler's Top100

Проблематика проекта

В практике экономико-математического моделирования часто встречаются задачи линейного программирования (ЛП) большой размерности (десятки тысяч переменных), обладающие такими "нерегулярными" свойствами как неполнота, противоречивость и изменчивость входных данных. Программные комплексы, базирующиеся на симплекс-методе и его модификациях, плохо приспособлены для решения такого рода задач. Кроме того, симплекс-метод обладает плохой масштабируемостью применительно к многопроцессорным вычислительным системам с массовым параллелизмом. В соответствии с этим необходимы иные алгоритмы и методы решения больших задач ЛП в условиях неполных, противоречивых и эволюционирующих исходных данных.

Целью проекта является разработка и исследование новых алгоритмов и методов решения задач линейного программирования большой размерности в условиях неполных, противоречивых и эволюционирующих исходных данных. Данные алгоритмы и методы должны допускать эффективное распараллеливание на многопроцессорных вычислительных системах с массовым параллелизмом, демонстрируя масштабируемость, близкую к линейной. Разрабатываемые алгоритмы и методы должны учитывать динамические изменения в исходных данных и вносить корректировки в вычислительный процесс в ходе поиска решения. Построенный на их основе программный комплекс должен сохранять эффективную работоспособность даже в тех случаях, когда исходная система ограничений становится противоречивой (случай несобственных задач ЛП) или неполной (случай задач ЛП с неформализованными ограничениями).

Актуальность проекта обоснована тем, что в настоящее время в мире отсутствуют программные комплексы, базирующиеся на алгоритмах и методах, удовлетворяющих описанным выше требования.

Методы реализации проекта основываются на использовании оригинальной S-технологии, а также на сочетании методов линейного программирования с методами дискриминантного анализа. Суть S-технологии заключается в следующем. Для задачи математического программирования формулируется двойственная задача. На основе исходной и двойственной задач конструируется симметрическая задача, представляющая собой систему неравенств. Данная система решается с помощью итерационных методов фейеровского типа. Из полученного решения выделяется решение исходной задачи. В основе S-технологии лежит фундаментальная теория двойственности в математическом программировании.
Фейеровские отображения являются естественным обобщением операции метрического проектирования. Они были введены венгерским математиком Липотом Фейером (1880-1959 гг.). Выбор фейеровских отображений в качестве основы итерационного процесса обусловлен тем, что они хорошо распараллеливаются, применимы к несобственным задачам ЛП и допускают динамическую корректировку. Важной особенностью фейеровских итерационных процессов является простота их реализации. Академиком РАН И.И. Ерёминым разработана фундаментальная теория по использованию фейеровских отображений для решения задач математического программирования.
Сочетание методов линейного программирования и дискриминантного анализа позволяет решать задачи ЛП с неформализованными ограничениями. Указанный подход предполагает участие в вычислительном процессе эксперта, способного определить соответствие точки неформализованному ограничении. По мере накопления образцов, роль эксперта может быть передана обучаемой нейронной сети.

Участники проекта

Руководитель проекта: академик РАН Ерёмин Иван Иванович (ermii@imm.uran.ru)

Основные исполнители проекта:

Гранты

Проект выполняется при поддержке Российского Фонда Фундаментальных Исследований.

  • Грант РФФИ № 09-01-00546-а (2009-2011 гг.): "Разработка параллельных алгоритмов на базе фейеровских отображений для решения задач дискриминантного анализа и линейной оптимизации на кластерных системах с многоядерными процессорами" (руководитель - академик РАН И.И. Ерёмин).

  • Грант РФФИ No. 06-01-00380 (2006-2008 гг.) "Алгоритмы и методы решения задач линейного программирования большой размерности в условиях неполных, противоречивых и изменяющихся исходных данных" (руководитель - академик РАН И.И. Ерёмин).

  • Грант РФФИ No. 03-01-00565 (2003-2005 гг.) "Разработка параллельных алгоритмов для решения несобственных задач линейного программирования большой размерности при эволюционирующей системе данных" (руководитель - академик РАН И.И. Ерёмин).

  • Грант Фонда содействия развитию малых форм предприятий в научно-технической сфере по Программе "У.М.Н.И.К."-2010 № 14004: "Исследование и анализ итерационных методов и алгоритмов сильной отделимости для выпуклых многогранников на базе фейеровских отображений" (руководитель - А.В. Ершова).

Публикации по проекту

Основные результаты, полученные в ходе выполнения данного проекта, опубликованы в следующих работах:

  1. Ершова А.В. Гибридный параллельный алгоритм решения задачи сильной отделимости на базе фейеровских отображений и операции проектирования // Статистика. Моделирование. Оптимизация: сборник трудов Всероссийской конференции (Челябинск, 28 ноября - 3 декабря 2011 г.). Челябинск: Издательский центр ЮУрГУ, 2011. С. 295-298. [Текст в формате PDF]

  2. Ершова А.В., Соколинская И.М. Параллельный алгоритм решения задачи сильной отделимости на основе фейеровских отображений // Вычислительные методы и программирование. 2011. Т. 12. С. 178-189. [Текст в формате PDF]

  3. Ершова А.В., Соколинская И.М. О сходимости масштабируемого алгоритма построения псевдопроекции на выпуклое замкнутое множество // Вестник ЮУрГУ. Серия "Математическое моделирование и программирование". 2011. No. 37(254), вып. 10. C. 12-21. [Текст в формате PDF]

  4. Ершова А.В., Соколинская И.М. Масштабируемый параллельный алгоритм построения псевдопроекций в задачах сильной отделимости // Научный сервис в сети Интернет: экзафлопсное будущее: Труды международной научной конференции (Новороссийск, 19-24 сентября 2011 г.). М.: Изд-во МГУ, 2011. С. 132-138. [Текст в формате PDF]

  5. Ершова А.В. Параллельный метод решения задачи сильной отделимости на базе фейеровских отображений. Информационный бюллетень Ассоциации математического программирования. № 12. Научное издание. Екатеринбург: УрО РАН, 2011. С. 85-86. [Текст в формате PDF]

  6. Соколинская И.М., Соколинский Л.Б. Параллельный сеточный метод линейной оптимизации на базе фейеровских отображений. Информационный бюллетень Ассоциации математического программирования. № 12. Научное издание. Екатеринбург: УрО РАН, 2011. С. 55-56. [Текст в формате PDF]

  7. Соколинский Л.Б., Соколинская И.М. Синтез методов оптимизации и дискриминантного анализа. Экономико-математическое моделирование. Lambert Academic Publishing. 2010. 84 с.

  8. Ершова А.В., Соколинская И.М. Параллельный алгоритм разделения двух выпуклых непересекающихся многогранников с использованием фейеровских отображений // Научный сервис в сети Интернет: суперкомпьютерные центры и задачи: Труды международной научной конференции (Новороссийск, 20-25 сентября 2010 г.). М.: Изд-во МГУ, 2010. С. 242-248. [Текст в формате PDF]

  9. Ершова А.В. Алгоритм решения задачи сильной отделимости на базе фейеровских отображений // Тезисы докладов XVIII Международной конференции "Математика. Экономика. Образование" (Новороссийск, 25 мая - 1 июня 2010 г.). Ростов-на-Дону: Изд-во СКНЦ ВШ ЮФУ, 2010. С. 131-132. [Текст в формате PDF]

  10. Ершова А.В. Последовательный алгоритм разделения двух выпуклых непересекающихся многогранников // Научный поиск: материалы второй научной конференции аспирантов и докторантов. Естественные науки. (Челябинск, апрель 2010 г.). Челябинск: Издательский центр ЮУрГУ, 2010. С. 30-34. [Текст в формате PDF]

  11. Ершова А.В. Метод решения задачи сильной отделимости для многопроцессорных систем с массовым параллелизмом // Параллельные вычислительные технологии (ПаВТ’2010): Труды международной научной конференции (Уфа, 29 марта - 2 апреля 2010 г.). Челябинск: Издательский центр ЮУрГУ, 2010. С. 660–661. [Текст в формате PDF]

  12. Ерёмин И.И. Фейеровские методы для задач выпуклой и линейной оптимизации. Челябинск: Изд-во ЮУрГУ, 2009. 200 с.

  13. Sokolinskaya I.M., Sokolinsky L.B. Hybrid method for solving incomplete linear optimization problem on distributed memory multiprocessor system // Proceedings of the 2009 International Conference on High Performance Computing, Networking and Communication Systems (HPCNCS-09), July 13-16 2009, Orlando, FL, USA. -ISRST 2009. P. 18-20. [Текст в формате PDF]

  14. Ершова А.В. Алгоритм разделения двух выпуклых непересекающихся многогранников с использованием фейеровских отображений // Системы управления и информационные технологии. -2009. -№ 1(35). -С. 53-56. [Текст в формате PDF]

  15. Ершова А.В. Задача разделения двух выпуклых многогранников с использованием фейеровских отображений // Алгоритмический анализ неустойчивых задач: Тезисы докладов Международной конференции (1-6 сентября 2008 г., Екатеринбург). -Екатеринбург: Изд-во Урал. ун-та, 2008. -С. 274-275. [Текст в формате PDF]

  16. Соколинская И.М., Соколинский Л.Б. Параллельный алгоритм решения задачи линейного программирования с неформализованными ограничениями // Системы управления и информационные технологии. -2008. -№ 1(31). -С. 37-43. [Текст в формате PDF]

  17. Асфандиярова Ю.С., Соколинская И.М. Применение S-технологии для решения задач линейного программирования на многопроцессорных системах с массовым параллелизмом  // Параллельные вычислительные технологии: Труды международной научной конференции (28 января - 1 февраля 2008 г., г. Санкт-Петербург). -Челябинск: Изд-во ЮУрГУ. -2008. -C. 516. [Текст в формате PDF]

  18. Соколинский Л.Б. Иерархический параллелизм: новая парадигма программирования // Информационный бюллетень Ассоциации математического программирования. -№ 11. -Екатеринбург: УрО РАН. -2007. -C. 76-77. [Текст в формате PDF]

  19. Ерёмин И.И. Методы распараллеливания фейеровских процессов // Параллельные вычислительные технологии: Труды международной научной конференции (29 января - 2 февраля 2007 г., г. Челябинск). -Челябинск: Изд-во ЮУрГУ. -2007. -Т. 1. -С. 24-27. [Текст в формате PDF]

  20. Шелудько А.С., Соколинский Л.Б. Исследование параллельного алгоритма для решения задач линейного программирования на основе фейеровских отображений // Параллельные вычислительные технологии: Труды международной научной конференции (29 января - 2 февраля 2007 г., г. Челябинск). -Челябинск: Изд-во ЮУрГУ. -2007. -Т. 2. -С. 277-280. [Текст в формате PDF]

  21. Цымблер Н.Ю., Соколинский Л.Б. Параллельный алгоритм решения задач линейного программирования на основе фейеровских отображений // Параллельные вычислительные технологии: Труды международной научной конференции (29 января - 2 февраля 2007 г., г. Челябинск). -Челябинск: Изд-во ЮУрГУ. -2007. -Т. 2. -С. 265. [Текст в формате PDF]

  22. Цымблер Н.Ю., Соколинский Л.Б. Параллельный алгоритм решения задач линейного программирования // Труды III Международной конференции "Параллельные вычисления и задачи управления" (Москва, 2-4 октября 2006 г.). [Электронное издание] -М.: Институт проблем управления РАН, 2006. -ISBN 5-201-14990-1. [Текст в формате PDF]

  23. Соколинская И.М., Соколинский Л.Б. Параллельный алгоритм решения задачи линейного программирования с неформализованными ограничениями // III Всероссийская конференция "Проблемы оптимизации и экономические приложения": Материалы конференции (Омск, 11-15 июля 2006 г.) / Омский филиал Института математики им. С.Л. Соболева СО РАН. -Омск: Изд-во ОмГТУ. -2006. ‑C. 156. [Текст в формате PDF]

  24. Ерёмин И.И. Фейеровские методы сильной отделимости выпуклых полиэдральных множеств // Известия вузов. Сер. математика. ‑2006. -No. 12. -C. 33-43. [Текст в формате PDF]

  25. Mazurov Vl.D., Sokolinskaya I.M. Discrimination analysis and randomization in linear optimization problems with not formalized restrictions // Pattern Recognition and Image Analysis. -2006. -Vol. 16, No. 2. -P. 170-178. [Текст в формате PDF]

  26. Ерёмин И.И. Прямо-двойственные фейеровские методы для задач квадратичного программирования // Труды Института математики и механики. Том 12, No. 1. Динамические системы: моделирование, оптимизация и управление. Сб. науч. трудов. -Екатеринбург: УрО РАН, 2006. -С. 86-97. [Текст в формате PDF]

  27. Соколинская И.М. Синтез симплекс-метода и метода линейной коррекции в задачах линейной оптимизации с неформализованными ограничениями // Вычислительные методы и программирование. -2005. -Том 6, No. 2. -C. 103-115. [Текст в формате PDF]

  28. Соколинская И.М., Соколинский Л.Б. Программный комплекс для решения задач линейного программирования с неформализованными ограничениями // Первая Международная Конференция "Системный Анализ и Информационные Технологии" САИТ-2005 (12-16 сентября 2005 г., Переславль-Залесский, Россия): Труды конференции. В 2 т. Т. 2. -М.: КомКнига. -2005. -C. 286-292. [Текст в формате PDF]

  29. Ерёмин И.И. Фейеровские процессы: синтез и рандомизация // Труды института математики и механики УрО РАН. -Т. 10. -No. 2. -2004. -С. 59-68. [Текст в формате PDF]

  30. Бердникова Е.А., Ерёмин И.И., Попов Л.Д. Распределенные фейеровские процессы для систем линейных неравенств и задач линейного программирования // Автоматика и телемеханика. -No. 2. -2004. -С. 16-32. [Текст в формате PDF]

  31. Соколинская И.М. Метод осцилляций в задачах линейного программирования с неформализованным ограничением // Алгоритмический анализ неустойчивых задач: Тез. докл. Всерос. науч. конф. (2-6 февраля 2004 г., Екатеринбург). -Екатеринбург: Изд.-во Урал. ун-та, 2004. -С. 302-303. [Текст в формате PDF]

  32. Ерёмин И.И., Рудакова Т.Н. Рандомизация фейеровских итерационных процессов для системы линейных неравенств и задач линейного программирования // Алгоритмический анализ неустойчивых задач: Тез. докл. Всерос. науч. конф. (2-6 февраля 2004 г., Екатеринбург). -Екатеринбург: Изд.-во Урал. ун-та, 2004. -С. 264-265. [Текст в формате PDF]

  33. Ерёмин И.И., Соколинская И.М. Фейеровские итерационные процессы для несобственных задач линейного программирования // Математические структуры и моделирование. [Сб. науч. тр.]. -Омск: Изд.-во Омск. гос. ун-та, 2002. -Вып. 9. -С. 10-26. [Текст в формате PDF]

Апробация проекта

Основные результаты, полученные в ходе выполнения данного проекта, докладывались на следующих научных конференциях, семинарах и совещаниях:

  1. На  Всероссийской конференции "Статистика. Моделирование. Оптимизация" (28 ноября - 3 декабря 2011 г.,  Челябинск ) А.В. Ершовой  [Презентация в формате PDF]

  2. На Международной конференции "Научный сервис в сети Интернет: экзафлопсное будущее" (19-24 сентября 2011 г., Новороссийск) А.В. Ершовой и И.М. Соколинской [Презентация в формате PDF]

  3. На XIV Всероссийской конференции "Математическое программирование и приложения" (28 февраля - 4 марта 2011 г., Екатеринбург) И.М. Соколинской и Л.Б. Соколинским [Презентация в формате PDF]

  4. На XIV Всероссийской конференции "Математическое программирование и приложения" (28 февраля - 4 марта 2011 г., Екатеринбург) А.В. Ершовой [Презентация в формате PowerPoint (zip-архив), PDF]

  5. На Международной конференции "Научный сервис в сети Интернет: суперкомпьютерные центры и задачи" (20-25 сентября 2010 г., Новороссийск) А.В. Ершовой и И.М. Соколинской [Презентация в формате PowerPoint (zip-архив), PDF]

  6. На XVIII Международной конференции "Математика. Экономика. Образование" (25 мая - 1 июня 2010 г., г. Новороссийск) А.В. Ершовой [Презентация в формате PowerPoint (zip-архив), PDF]

  7. На Международной конференции "Параллельные вычислительные технологии 2010" (29 марта  - 2 апреля 2010 г., Уфа) А.В. Ершовой [Плакат в формате PDF]

  8. На Международной конференции "Алгоритмический анализ неустойчивых задач" (1-6 сентября 2008 г., Екатеринбург) А.В. Ершовой [Презентация в формате PowerPoint (zip-архив), PDF]

  9. На Международной конференции "Параллельные вычислительные технологии 2008" (28 января - 1 февраля 2008 г., Санкт-Петербург) Ю.С. Асфандияровой и И.М. Соколинской [Плакат в формате PDF]

  10. На XIII Всероссийской конференции "Математическое программирование и приложения" (26 февраля - 2 марта 2007 г., Екатеринбург) Л.Б. Соколинским [Слайды в формате PowerPoint, PDF]

  11. На Международной конференции "Параллельные вычислительные технологии 2007" (29 января - 2 февраля 2007 г., Челябинск) Н.Ю. Цымблер и Л.Б. Соколинским.

  12. На III Международной конференции "Параллельные вычисления и задачи управления" (2-4 октября 2006 г., Москва) Н.Ю. Цымблер [Презентация в формате PowerPoint (zip-архив), PDF]

  13. На III Всероссийской конференции "Проблемы оптимизации и экономические приложения" (11-15 июля 2006 г., Омск) И.М. Соколинской [Презентация в формате PowerPoint (zip-архив), PDF]

  14. На Международной конференции "Системный Анализ и Информационные Технологии" САИТ-2005 (12-16 сентября 2005 г., Переславль-Залесский) И.М. Соколинской [Презентация в формате PowerPoint (zip-архив), PDF]

  15. На Всероссийской научной конференции "Алгоритмический анализ неустойчивых задач" (2-6 февраля 2004 г., Екатеринбург) И.М. Соколинской [Презентация в формате PowerPoint (zip-архив), PDF]

Диссертации, выполненные в рамках проекта

По теме данного проекта выполнены следующие диссертации:

Соколинская И.М. Синтез методов оптимизации и дискриминантного анализа в математических моделях экономики:
Дис. ... канд. физ.-мат. наук: 05.13.18 / Челябинский государственный университет. -Челябинск, 2006. -92 л.

[Автореферат диссертации в формате PDF. Полный текст диссертации в формате PDF. Презентация в формате PowerPoint (zip-архив), PDF]

Зарегистрированные программы

  1. Ершова А.В. Свидетельство Роспатента об официальной регистрации программы для ЭВМ "Гибридный параллельный алгоритм решения задачи сильной отделимости на базе фейеровских отображений и операции проектирования" № 2011618909 от 16.11.2011, правообладатель: ФГБОУ ВПО "ЮУрГУ" (НИУ).

  2. Соколинская И.М. Свидетельство Роспатента об официальной регистрации программы для ЭВМ "Программный комплекс для решения задач линейного программирования с неформализованными ограничениями: параллельная версия для MPI-2" № 2011610983 от 26.01.2011, правообладатель: ГОУ ВПО "ЮУрГУ".

  3. Ершова А.В. Свидетельство Роспатента об официальной регистрации программы для ЭВМ "Параллельный алгоритм решения задачи разделения двух выпуклых непересекающихся многогранников на базе фейеровских отображений" № 2011610980 от 26.01.2011, правообладатель: ГОУ ВПО "ЮУрГУ".

  4. Соколинская И.М. Свидетельство Роспатента об официальной регистрации программы для ЭВМ "Программный комплекс для решения задач линейного программирования с неформализованными ограничениями" № 2010615981 от 13.09.2010, правообладатель: ГОУ ВПО "ЮУрГУ".

  5. Ершова А.В. Свидетельство Роспатента об официальной регистрации программы для ЭВМ "Последовательный алгоритм решения задачи разделения двух выпуклых непересекающихся многогранников на базе фейеровских отображений" № 2010616104 от 16.09.2010, правообладатель: ГОУ ВПО "ЮУрГУ".

  6. Ершова А.В. Свидетельство Роспатента об официальной регистрации программы для ЭВМ "Генерация двух выпуклых непересекающихся многогранников" № 2010616105 от 16.09.2010, правообладатель: ГОУ ВПО "ЮУрГУ".

Исходные тексты программ, разработанных в рамках проекта.

Web-ресурсы по теме проекта

Исследовательские группы и персоналии

Copyright © Кафедра системного программирования ЮУрГУ