Школа по алгоритмам дискретной оптимизации и конференция по теории графов
C 4 по 12 сентября в Гданьске (Польша) состоялась Летняя школа по алгоритмам дискретной оптимизации (Gdańsk Summer School of Advanced Science on Algorithms for Discrete Optimization). Мероприятие было организовано на базе Гданьского Политехнического университета. После завершения школы, с 13 по 15 сентября, в Сопоте (Польша) прошла Пятая Гданьская конференция по теории графов (the Fifth Gdańsk Workshop on Graph Theory).
В работе конференции и школы приняли участие ученые и исследователи 15 стран мира, в том числе молодые преподаватели департамента программной инженерии Екатерина Береснева и Мария Горденко, которые прослушали курсы лекций, а также представили свои работы “The Mixed Chinese Postman Problem” (Мария) и “Pareto-optimal algorithms for metric TSP” (Екатерина) на постерной сессии и в качестве докладов на конференции.
Екатерина Береснева
Преподаватель
За 8 дней летней школы было проведено 5 мини-курсов по различным областям дискретной оптимизации от известных исследователей из Польши и других стран. Каждый сопровождался семинарскими занятиями, где можно было задать вопросы, пообщаться с коллегами и выполнить упражнения по пройденной теме. Одним из самых полезных для меня оказался мини-курс «Линейное и смешанное программирование» (Linear and Mixed Programming) Бартека Савика (Bartek Sawik), где непосредственно рассматривались различные типы задачи TSP (Travelling Salesman Problem) и известные алгоритмы их решения. После курса лекций была организована постерная сессия, на которой можно было осветить актуальные проблемы в области теории графов и дискретной оптимизации, пообщаться с другими исследователями, получить полезные комментарии и советы.
На конференции, в частности на секции “Hamiltonicity and TSP”, собрались люди, которым интересна моя тематика исследований, а именно – задача коммивояжера. Кажется, что в этой области уже нечего изучать, однако, уже несколько десятков лет исследователи из разных стран пытаются получить точный не переборный алгоритм для решения этой задачи, увы, пока безуспешно. Мне удалось пообщаться с коллегами и почерпнуть новые идеи для дальнейшей работы. Например, коллега из Китая Моу Гау (Mou Gao), который занимается смежной проблемой поиска гамильтоновых циклов в графах, подсказал мне, как можно создавать свои собственные входные данные для оценки качества реализованных алгоритмов.
Мария Горденко
Преподаватель
Уже несколько лет я занимаюсь изучением смешанной задачи китайского почтальона (The Mixed Chinese Postman Problem), которая, несмотря на свою простую формулировку, до сих пор не имеет точного полиномиального алгоритма решения, так как принадлежит к классу NP-трудных задач. Участие в летней школе для меня – бесценный опыт и багаж приобретенных знаний. За эти несколько насыщенных дней я познакомилась с большим количеством людей, занимающихся смежными проблемами. На постерной сессии, проводимой в рамках мероприятия, мне удалось получить полезные для моих исследований и комментарии, которые, я надеюсь, удастся воплотить в жизнь. Так, Марек Кубале (Marek Kubale) из Политехнического Университета Гданьска задал вопрос: «Почему для не планарной задачи применение планарных алгоритмов приводит к получению хороших результатов?», на который я пока не могу дать ответа.
Насыщенная учебная программа сопровождалась экскурсиями по самым знаменитым местам Гданьска и окрестностям. В субботу, 9 сентября, была организована экскурсия в Старый город в Гданьске, который как будто застыл на границе Средневековья и современности; а в воскресенье, 10 сентября, состоялась экскурсия в средневековый замок Тевтонского ордена в Мальборке. К слову, Мальборк – замок, являющийся самым большим кирпичным сооружением, созданным руками людей. Занимает он территорию площадью около 21 гектара. В понедельник, 11 сентября, мы увидели настоящее чудо Гданьского Политехнического университета – суперкомпьютер Tryton, входящий в рейтинг ТОП500 (рейтинг 500 самых мощных общественно известных вычислительных систем мира).
Следом за летней школой мы отправились на Пятую ежегодную Гданьскую конференцию по теории графов, которая была организована на высшем уровне. Я выступала с докладом “The Mixed Chinese Postman Problem”, которым тут же заинтересовались мои коллеги. После доклада и бурных обсуждений я смогла для себя выделить направления дальнейшей работы в области задач маршрутизации. Стоит отметить, что задача китайского почтальона и задача коммивояжера являются всего лишь частными случаями обобщенной задачи маршрутизации, решения которых имеют массу потенциально полезных приложений.