Master
2022/2023
Discrete optimization and operations research
Category 'Best Course for Career Development'
Category 'Best Course for Broadening Horizons and Diversity of Knowledge and Skills'
Category 'Best Course for New Knowledge and Skills'
Type:
Compulsory course (Data Mining)
Area of studies:
Applied Mathematics and Informatics
Delivered by:
Department of Applied Mathematics and Informatics
When:
1 year, 1, 2 module
Mode of studies:
offline
Open to:
students of all HSE University campuses
Instructors:
Mikhail Vladimirovich Batsyn
Master’s programme:
Интеллектуальный анализ данных
Language:
English
ECTS credits:
6
Contact hours:
56
Course Syllabus
Abstract
The course covers modern exact methods for solving combinatorial optimization problems, including methods of branches and bounds, branches and clippings, branches and prices. All algorithms are analyzed on the example of well-known optimization problems, such as the maximum clique problem, the traveling salesman problem, transport routing problems, and so on
Learning Objectives
- Целями освоения дисциплины является знакомство с современными классическими и прикладными задачами оптимизации, моделями математического программирования, точными алгоритмами ветвей и границ, ветвей и отсечений, ветвей и отсечений и цен и другими современными методами. Изучение данной дисциплины базируется на следующих дисциплинах: • Исследование операций • Разработка программного обеспечения Для освоения учебной дисциплины, студенты должны владеть следующими знаниями и компетенциями: • Задачи математического программирования, алгоритмы решения классических задач исследования операций Основные положения дисциплины могут быть использованы при написании курсовой и дипломной работы.
Expected Learning Outcomes
- По модели математического программирования для задачи студент получает оценку на целевую функцию с помощью Лагранжевой релаксации.
- Студент разрабатывает модель с большим (обычно экспоненциально большим) числом ограничений для задачи, программирует алгоритм ветвей и отсечений для решения задачи и решает задачу с помощью реализованной программы.
- Студент разрабатывает модель с большим (экспоненциально большим) числом переменных, программирует алгоритм ветвей и цен для решения задачи с такой моделью и решает задачу с помощью разработанной программы.
- Студент разрабатывает эвристику для решения задачи, программирует ее и решает задачу с помощью этой программы.
- Студент строит линейную модель по описанию задачи и решает задачу
- Студент строит модель целочисленного программирования по описанию задачи, программирует алгоритм ветвей и границ для решения задачи и решает задачу с помощью написанной программы.
Course Contents
- Linear problems
- Integer problems. Branch-and-bound method.
- Local search
- Branch-and-cut approach
- Branch-and-price approach.
- Lagrangian relaxation
Assessment Elements
- Метод ветвей и границ для задачи о максимальной кликеНужно реализовать классический метод ветвей и границ, в котором вы должны ветвиться по дробным переменным. Для задачи о макс. клике. Примеры для клики нужно искать в библиотеке DIMACS: http://iridia.ulb.ac.be/~fmascia/maximum_clique/DIMACS-benchmark#detC125.9 Возьмите самые маленькие файлы из архива (я вам давал список файлов): http://iridia.ulb.ac.be/~fmascia/files/DIMACS_all_ascii.tar.bz2 Простые: johnson8-2-4, 4 johnson16-2-4, 8 MANN_a9, 16 keller4, 11 haming8-4, 16 Средние: C125.9.clq, 34 brock200_1, 21 brock200_2, 12 brock200_3, 15 brock200_4, 17 gen200_p0.9_44, 44 gen200_p0.9_55, 55 p_hat1000-1, 10 san1000, 15 Сложные: brock400_1, 27 brock400_2, 29 brock400_3, 31 brock400_4, 33 MANN_a27, 126 MANN_a45, 345 sanr400_0.7, 21 p_hat1000-2, 46 p_hat500-3, 50 p_hat1500-1, 12 p_hat300-3, 36 sanr200_0.9, 42 Обязательно нужно реализовать метод check_clique(), который будет проверять в конце найденную клику, на то, что в ней никакие вершины не повторяются и каждая вершина соединена ребром с каждой. От каждого требуется исходный код, причем не ссылка на гитхаб и т п, откуда мне нужно самому все скачивать с кучей лишних файлов. Файл исходного кода нужна назвать в формате: batsyn_bnb.cpp, alperovich_bnb.py и т п Кроме этого нужно обязательно прислать результаты по каждому решенному или нерешенному графу в формате: CPU = 2.2 GHz Intel Core i7, Time limit = 7200 sec Graph Time Clique Size brock_200 300.5 12 phat500-1 7200.0 10 (best found clique before timeout) ... Оценивается в первую очередь правильность метода. Это должен быть точный метод, то есть все решения должны быть либо рассмотрены, либо корректно отброшены. В «нулевую» очередь программа должна просто работать. Далее оценивается эффективность метода. Реализована ли начальная эвристика, насколько она хорошая. Добавляете ли вы доп. усиленные ограничения. Считается ли граница и правильно ли она используется. Как хорошо сделано ветвление, нет ли лишних действий в каждом узле дерева. Если например вы сделали все корректно, но не стали делать начальную эвристику, никаких доп ограничений, ветвитесь по первой попавшейся дробной переменной и т п, то оценка будет около 7 баллов (хотя она может быть больше, если каким-то чудом алгоритм быстро работает). Если все корректно и вы среди первых по скорости работы, то оценка будет 10. Если вы сделали хотя бы начальную эвристику и программа работает со средней скоростью, то будет 8. Примерно так, но это примерно, я буду ориентироваться на все работы и ставить так, чтобы все было справедливо, более-менее Обратите внимание на работу с действительными числами. Вам нужно будет проверять дробность переменных, но в компьютере нет точных вычислений. Поэтому числа типа 0.99999 или 1.000001 – это на самом деле единица, а числа типа -0.000001 и 0.000001 – это ноль. Если вы неправильно реализуете проверку дробности, то будете лишний раз ветвится и оценка будет снижена. Здесь смотрите пункт про погрешности: https://notes.algoprog.ru/python_basics/5_float.html Дебажьте алгоритм и смотрите как все работает. Вы можете все проверять руками в текстовом интерфейсе СИПЛЕКСА, который я вам показывал на лекциях. Там вам нужны будут команды: read lalala.lp optimize display solution variables * Типичные замечания по работам: - Неправильные результаты (на каких-то примерах check_clique() находит ошибку в решении) - это резко снижает оценку - Решены только совсем простые графы, мало результатов - это снижает оценку - Нет начальной эвристики - это снижает оценку обычно на 1 балл, если результаты так себе - Дублирование кода, ужасный стиль кода, непонятный код - это может снизить оценку, особенно при плохих результатах - В каждом узле ветвление выполняется по очереди по всем дробным переменным, вместо одной - это резко замедляет программу и снижает оценку - В каждом узле дерева решений много раз вызывается медленный метод - это снижает оценку
- Метод ветвей и отсечений для задачи о максимальной кликеРеализовать метод BnC, получить результаты на тех же графах
Interim Assessment
- 2022/2023 2nd module0.5 * Метод ветвей и границ для задачи о максимальной клике + 0.5 * Метод ветвей и отсечений для задачи о максимальной клике
Bibliography
Recommended Core Bibliography
- Andreas S. Schulz, Martin Skutella, Sebastian Stiller, Dorothea Wagner. Gems of Combinatorial Optimization and Graph Algorithms. Springer International Publishing, Switzerland, 2015.
- 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
- Panos M. Pardalos, Ding-Zhu Du, Ronald L. Graham. Handbook of Combinatorial Optimization. Springer Science+Business Media, New York, 2013.
- Pardalos, P. M., Du, D. Z., Graham, R. L. (ed.). Handbook of combinatorial optimization. – Springer, 2013. – 3409 pp.
- Schulz, A. S., Skutella, M., Stiller, S., & Wagner, D. (2015). Gems of Combinatorial Optimization and Graph Algorithms. Cham: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1164017
Recommended Additional Bibliography
- Bernhard Korte, Jens Vygen. Combinatorial Optimization. Theory and Algorithms. Fifth edition. Springer-Verlag, Berlin Heidelberg, 2012.
- Ming-Yang Kao. Encyclopedia of Algorithms. Springer, New York, NY, 2016
- Taha H.A. Operations Research: An Introduction, 10-th Edition, Pearson Education Limited, 2017. – 849 p. – ISBN: 9781292165561
- 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