Курс "Технологии оптимизационного моделирования", база, ФИВТ

Семестровый курс  "Технологии оптимизационного моделирования"
к.ф.-м.н., Волошинов Владимир Владимирович, vladimir.voloshinov[at]gmail.com
Программа курса с контрольными вопросами для экзамена (раздел 6)

 

Разделы и темы лекционных занятий

Содержание

1

Предмет оптимизационного моделирования. Классификация и основные типы оптимизационных задач. Соотношения двойственности.

Концепция оптимизационных моделей, как одного из инструментов прикладной математики. Задачи линейного, выпуклого и математического программирования в т.ч. с частично целочисленными переменными, задачи дискретной и глобальной оптимизации. Правило формирования двойственной задачи. Соотношения двойственности.

2

Необходимые сведения из выпуклого анализа. Теоремы об оценках расстояния до множества решений систем линейных и нелинейных неравенств.

 Необходимые сведения из выпуклого анализа. Отделимость выпуклых множеств (теорема Хана-Банаха). Выпуклые конусы, теоремы об альтернативах (неравенствах-следствиях). Выпуклые функции и преобразования над ними, сохраняющие выпуклость. Дифференцируемость выпуклых функций.
Теорема Хоффмана об оценке расстояния до множества решений системы линейных неравенств.
Оценки расстояния для нелинейных систем. Условия Слейтера.

3Задачи линейного программирования. Свойства и методы решения. Постоптимальный анализ (маржинальные оценки). Связь с задачами квадратичного программирования (КП).

Общая и каноническая форма записи задач ЛП. Прямой и двойственный симплекс метод. Зависимость решения от параметров задачи, постоптимальный анализ и маржинальные оценки. «Параметрический» симплекс-метод.
Отличия и сходство задач ЛП с задачами квадратичного программирования. «Обобщение» симплекс метода для задач КП.

4

 Характеризация решений нелинейных гладких задач математического программирования (МП). Условия оптимальности.

Гладкие нелинейные задачи МП. Дифференцируемые функции с Липшицевыми производными. Теоремы Каруша-Джона и Куна-Таккера для гладких и выпуклых задач МП. Метод линеаризации и вспомогательная задача квадратичного программирования.
Обобщение на случай приближенных решений.
5

Эффективная разрешимость выпуклых задач. Метод внутренней точки как развитие метода Ньютона.  

Теоретические оценки для эффективного поиска решений выпуклых задач МП.
Об эффективной разрешимости задачи безусловной минимизации выпуклой функции
.
Метод Ньютона для гладких задач.
Самосогласованные функции. Метод внутренней точки и его вычислительная эффективность.

6

Задачи с блочной структурой и методы их решения.

Понятие и примеры линейных и выпуклых задач с блочной структурой. Методы декомпозиции (Данцига-Вульфа, Бендерса).
Возможности ускорения за счет распараллеливания.
7Метод ветвей-и-границ (ВиГ) для задач с частично-целочисленными переменными и задач глобальной оптимизации. Примеры задач.
Основные понятия и общая структура метода ВиГ. Обсуждение на примерах линейных и выпуклых задач с частично-целочисленными переменными.
Возможности ускорения для линейных задач за счет построения отсечений Гомори.
Приемы сведения прикладных задач к линейным и выпуклым задачам с частично-целочисленными переменными.
Дихотомические ограничения. Примеры задач составления расписаний и задач на графах (коммивояжера, поиска максимальных связных подграфов).
8Пакеты численных методов оптимизации.
Алгебраические языки и системы оптимизационного моделирования на их основе.
Классификация существующих пакетов оптимизации. Сведения о пакетах Lpsolve, GLPK. Семейство пакетов проекта COIN (Clp, Cbc, Ipopt, Bonmin). Принципы применения и типовые настройки.
Сведения о системах оптимизационного моделирования (AMPL, GAMS, Zimpl). Принципы интеграции пакетов.
*Сведения о пакете CVXOPT.
9Принципы создания распределенных систем оптимизационного моделирования.Понятие о сервисах оптимизационного моделирования. Сведения о проектах NEOS, COIN OS.
Принципы создания сервисов и систем оптимизации на основе инструментария MathCloud.

 

 


 

Электронные ресурсы, включая доступ к базам данных 

Сайт языка AMPL (A Modeling Language for Mathematical Programming)  http://www.ampl.com
Сайт системы Pyomo (Python Optimization Modeling Objects), в частности, представляет собой свободно доступную в исходных кодах альтернативу коммерческому AMPL, http://www.pyomo.org
Решатель SCIP (Solving Constrained Integer Programs) (MILP, MINLP с полиномиальными функциями), http://scip.zib.de  Имеет параллельные реализации МВГ для систем с общей памятью (FiberSCIP) и для кластеров (ParaSCIP), http://ug.zib.de 
 Сайт проекта COIN-OR (COmputational INfrastructure for Operations Research) ,   http://www.coin-or.org/
 пакеты
        Clp (LP, QP?),  https://projects.coin-or.org/Clp
        Cbc (MILP),  https://projects.coin-or.org/Cbc
        Ipopthttps://projects.coin-or.org/Ipopt/
        Bonminhttps://projects.coin-or.org/Bonmin, http://www.coin-or.org/Bonmin/Intro.html

   Пакет GLPK (Gnu LP Kit) http://www.gnu.org/software/glpk/glpk.html
   Пакет Lpsolve   http://lpsolve.sourceforge.net/

Инструментарий создания сервисов оптимизации COIN-OS, https://projects.coin-or.org/OS

Портал NEOS,  http://www.neos-server.org/neos/,  ссылки на доступные пакеты http://www.neos-server.org/neos/solvers/index.html

Сайт проекта MathCloud  (инструментарий распределенных систем,  включая средства развёртывания, публикации и композиции вычислительных REST-сервисов), www.mathcloud.org

   *Пакет CVX  http://abel.ee.ucla.edu/cvxopt/index.html

Самостоятельные работы

ТемыМатериалы
1Сравнить время решения задачи составления оптимального расписания работ (представленной в виде задачи линейного программирования с частично-целочисленными переменными) пакетами GLPK и COIN CBC 
2

Сравнить время решения задачи «о многомерном рюкзаке» пакетом COIN CBC при включенной и отключенной опции «отсечений (Гомори)»

 
3 Сравнить время и число итераций поиска минимума линейной функции на циклическом многограннике (размерности не менее 3) различными вариантами симплекс метода (пакеты GLPK, COIN CLP) и методом внутренней точки (пакет COIN Ipopt) 
4

Создание REST-сервисов решения задач оптимизации на основе пакетов COIN CLP, CBC и Ipopt

Примеры реализаций в предыдущей версии MathCloud (JSON-дескриптори и bash-скрипты)
5 Упражнения на использование системы обработки результатов физического эксперимента, созданной в среде MathCloud. Изменить содержание файла с исходными данными эксперимента и получить соответствующие графики, отображающие результат.

  Варианты
"Оптимизация на кластере"

"Оптимизация на сервере"

Исходные данные, для параметров start (*.zip), experiment (*.txt), noise (*.txt).

 

Список литературы (см. bookfi.org)

  1. Мину М. Математическое программирование. Теория и алгоритмы: Пер. с фр. и предисловие А.И. Штерна, - М.;Наука, 1990. - 488с.

  2. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. - М.: Наука. Главная редакция физико-математической литературы, 1980. - 320 с.
  3. Муртаф Б. Современное линейное программирование. М. Мир, 1984, 224 с.
  4. Васильев Ф. П., Иваницкий А. Ю. Линейное программирование. — М.: Изд-во «Факториал Пресс», 2003. — 352 с.
  5. Нестеров Ю.Е. Введение в выпуклую оптимизацию / Под ред. Б.Т. Поляка, С.А. Назина. - М.: МЦНМО, 2010. - 280 с.
  6. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. - 368 с.
  7. Robert Fourer, David M. Gay, and Brian W. Kernighan. AMPL: A Modeling Language for Mathematical Programming. Duxbury Press / Brooks/Cole Publishing Company, 2003. (http://www.ampl.com/BOOK/download.html)