Дискретная оптимизация

2016/2017

Учебный год

RUS

Обучение ведется на русском языке

4

Кредиты

Кто читает:

Кафедра прикладной математики и информатики (Нижний Новгород) (Факультет информатики, математики и компьютерных наук (Нижний Новгород))

Статус:

Курс обязательный

Когда читается:

1-й курс, 1, 2 семестр

Программа дисциплины

Аннотация

Дисциплина «Дискретная оптимизация» нацелена на развитие способностей проводить исследования методов преобразования информации в данные и знания, модели данных и знаний, принципов создания и функционирования программных средств автоматизации этих методов. Рассматриваются современные задачи дискретной оптимизации, их математические модели и эффективные алгоритмы решения. Теоретические положения иллюстрируются практическими применениями рассматриваемых алгоритмов к решению прикладных задач высокой вычислительной сложности. В результате освоения дисциплины аспиранты получают современные знания по методам дискретной оптимизации и их применению к решению реальных задач (real life problems).

Цель освоения дисциплины

• Целью освоения дисциплины является знакомство учащихся с современными методами и алгоритмами дискретной оптимизации. В результате освоения дисциплины аспирант должен: Знать: основные положения построения моделей в задачах дискретной оптимизации, основы построения и анализа алгоритмов дискретной оптимизации. Уметь: использовать полученные знания в своей научной и педагогической деятельности Иметь навыки (приобрести опыт): работы с литературой, разработки компьютерных программ дискретной оптимизации

Планируемые результаты обучения

• Полнимает теоретические основы моделей целочисленного программирования и умеет строить модели.
• Понимает теоретические основы моделей ЛП и умеет строить модели.
• Знает основные принципы классических подходов к построению эвристик
• Знает основные принципы построения эвристик локального поиска
• Понимает основные принципы построения эвристик типа табу поиска
• Анализирует различные эвристики, проводит сравнение, выбирает наиболее адекватный алгоритм

Содержание учебной дисциплины

• Различные модели целочисленного программирования для задачи о раскраске. Метод ветвей и границ на примере задачи о раскраске
  Модели VCP-ASS (Assignment) и VCP-SC (Set Covering) для задачи о раскраске. Современные методы решения для этих моделей. Начальное упорядочение, эвристическое решение, глобальная и локальная нижние границы и другие способы повышения эффективности метода ветвей и границ.
• Модель математического программирования для практической задачи маршрутизации транспорта с большим числом ограничений.
  Задача маршрутизации с несколькими видами транспорта с прицепом, ограничением грузоподъемности, ограничениями заказчиков по виду транспорта, временными окнами, разделенной доставкой, несколькими выездами.
• Классические эвристики
  Классические эвристики: жадная эвристика (greedy), метод максимального сожаления (max-regret), multi-start подход, усеченный метод ветвей и границ. Описание алгоритма каждой из эвристик. Подробное рассмотрение каждой эвристики на небольших примерах различных задач комбинаторной оптимизации
• Локальный поиск
  Локальный поиск, или поиск в окрестности (local, or neighbourhood, search), итеративный локальный поиск (iterated local search). Поиск во многих окрестностях (variable neighbourhood search) Описание алгоритма локального поиска и итеративного локального поиска. Подробное рассмотрение локального поиска и итеративного локального поиска на небольших примерах различных задач комбинаторной оптимизации. Описание алгоритма поиска во многих окрестностях. Подробное рассмотрение поиска во многих окрестностях на небольших примерах различных задач комбинаторной оптимизации.
• Табу поиск
  Табу поиск (tabu search). Рассредоточенный поиск (scatter search) Описание алгоритма табу поиска. Подробное рассмотрение эвристики табу поиска на небольших примерах различных задач комбинаторной оптимизации. Описание алгоритма рассредоточенного поиска. Подробное рассмотрение эвристики рассредоточенного поиска на небольших примерах различных задач комбинаторной оптимизации.
• Алгоритмы инспирированные природой
  Генетические алгоритмы (genetic algorithms). Муравьиный алгоритм (ant colony optimization). Метод роя частиц (particle swarm optimization). Пчелиный алгоритм (bees algorithm) Описание генетического алгоритма общего вида. Подробное рассмотрение конкретных генетических алгоритмов на небольших примерах различных задач комбинаторной оптимизации. Описание муравьиного алгоритма в общем виде. Подробное рассмотрение конкретных муравьиных алгоритмов на небольших примерах различных задач комбинаторной оптимизации. Описание метода роя частиц в общем виде. Подробное рассмотрение конкретных алгоритмов роя частиц на небольших примерах различных задач комбинаторной оптимизации. Описание пчелиного алгоритма в общем виде. Подробное рассмотрение конкретных пчелиных алгоритмов на небольших примерах различных задач комбинаторной оптимизации.

Элементы контроля

• самостоятельная работа
• экзамен

Промежуточная аттестация

• Промежуточная аттестация (II семестр)
  0.3 * самостоятельная работа + 0.7 * экзамен

Список литературы

Рекомендуемая основная литература

• Du, D., & Pardalos, P. M. (2005). Handbook of Combinatorial Optimization : Supplement Volume B. [Berlin]: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=133080
• Pardalos, P. M., Du, D. Z., Graham, R. L. (ed.). Handbook of combinatorial optimization. – Springer, 2013. – 3409 pp.
• Potvin, J.-Y., & Gendreau, M. (2010). Handbook of Metaheuristics (Vol. 2nd ed). New York: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=373689
• Toth, P., & Vigo, D. (2002). Models, relaxations and exact approaches for the capacitated vehicle routing problem. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.E80A9B59

Рекомендуемая дополнительная литература

• Aarts, E. H. L., & Lenstra, J. K. (2003). Local Search in Combinatorial Optimization. Princeton: Princeton University Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1836915
• Bernhard Korte, Jens Vygen. Combinatorial Optimization. Theory and Algorithms. Fifth edition. Springer-Verlag, Berlin Heidelberg, 2012.
• Kochetov Y, Pardalos P., Nurminski E., Beresnev V., Khachay M. Discrete Optimization and Operations Research \\ Springer \\https://www.springer.com/gp/book/9783319449135