Кафедра прикладной математики и информатики (Нижний Новгород)

АБB
АБB
АБB

Обычная версия сайта

Кафедра ПМИ создана в 2006 году как выпускающая кафедра по направлению "Прикладная математика и информатика".

Целью деятельности кафедры «Прикладной математики и информатики» является подготовка высококвалифицированных специалистов (бакалавров и магистров) по направлению 010500 «Прикладная математика и информатика», обладающих знаниями и квалификацией, необходимыми для профессионального моделирования и информационного обеспечения экономических и бизнес процессов, анализа и обработки данных.

Научная деятельность

Кафедра выполняет межкафедральные (кафедры Информационных систем и технологий, Математики и др.) исследовательские проекты, национальные проекты в составе общих исследовательских групп (РФФИ, проекты Минобрнауки РФ и др.) с участием партнеров из Института прикладной математики им. М. Келдыша РАН, Математического института им. В. Стеклова РАН, Института прикладной физики РАН, МГУ им. М. Ломоносова, ННГУ им Н. Лобачевского. Осуществляется международное сотрудничество с различными научными центрами Европы и США.

Публикации

Книга

Integral Robot Technologies and Speech Behavior

Kharlamov A. A., Pantiukhin D., Borisov V. et al.

Newcastle upon Tyne: Cambridge Scholars Publishing, 2024.

Статья

On efficient algorithms for bottleneck path problems with many sources
В печати

Каймаков К. В., Malyshev D.

Optimization Letters. 2024. P. 1-11.

Глава в книге

Neural Networks for Speech Synthesis of Voice Assistants and Singing Machines

Pantiukhin D.

In bk.: Integral Robot Technologies and Speech Behavior. Newcastle upon Tyne: Cambridge Scholars Publishing, 2024. Ch. 9. P. 281-296.

Препринт

DAREL: Data Reduction with Losses for Training Acceleration of Real and Hypercomplex Neural Networks

Demidovskij A., Трутнев А. И., Тугарев А. М. et al.

NeurIPS 2023 Workshop. ZmuLcqwzkl. OpenReview, 2023

Все публикации

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

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

Когда читается:: 1-й курс, 1, 2 модуль

Преподаватель

Бацын Михаил Владимирович

Full 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 module
0.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

Discrete optimization and operations research