Discrete Optimization
Ценой огромных усилий закончил курс по дискретной оптимизации от Pascal Van Hentenryck из университета Мельбурна. Хочу поделиться впечатлениями.
Во-первых, что за курс. Курс про методы дискретной оптимизации, сосредоточен на трёх больших темах: constraint programming, local search и integer and mixed programming. Плюс вводная часть про динамическое программирование и метод ветвей и границ. Каждую неделю подразумевается просмотр 2-3 часов видеолекций и решение одной NP-сложной задачи :) Благодаря всему этому заявленные 10-15 часов в неделю - правда. На особо сложных задачах запросто может быть и 20-30 часов. При этом график курса свободный, все материалы доступны сразу, можно проходить в любом удобном порядке.
Задачи - это укладка рюкзака, раскраска графа, коммивояжер, оптимизация расположения складов, логистика (множественный коммивояжер с ограниченной вместимостью). Для каждой задачи есть подзадачи разных размеров, их 6-8 штук. И ещё дополнительные паззлы про N ферзей, магический квадрат и т.п. для тех, кому в конце не хватает баллов на сертификат.
Все решения оцениваются автоматом по шкале {0,3,7,10}, 0 - за неправильное решение, 3 - за валидное, но низкокачественное; 7 - за хорошее, 10 за отличное. Решать можно на чём угодно, изначально предоставляется готовый скелет и тупое решение на питоне. Это тупое решение сразу обеспечивает 3 балла. Семёрку получить в целом не очень сложно, но бывают исключения, а также большие задачи. Для десятки как правило приходится изрядно повозиться, кроме совсем маленьких по размеру задач. Да, ещё все задачи ограничены по времени - если решение занимает больше пяти часов, то десятка не светит.
Про подходы к решению.
Рюкзак я целиком решил динамическим программированием, лишь для самого большого рюкзака пришлось исхитряться, потому что таблица не влезала в память. Обошлось питоном + numpy. Векторизация, конечно, рулит.
В остальных задачах оправдывало себя начинать с жадного алгоритма, по ходу дела навешивая на него разные эвристики под задачу. Как правило это давало десятки на задачах малого размера, и 3-7 на остальных.
Раскраску графа я делал неким примитивным вариантом constraint programming, добился этим семёрок. Под конец курса переписал на итеративный жадный алгоритм и получил все десятки кроме одной. Если бы переписал на C++, наверное, и последнюю десятку тоже получил бы.
Коммивояжера пытался решить отжигом. Долго не мог добиться ничего хорошего, в лучшем случае семёрки, и то не везде. Переписал всё на плюсы, стало ощутимо быстрее, но достаточно хорошего результата всё равно не находило. Так и не понял, на чём конкретно он спотыкался, есть чувство, что расписание отжига (или как это по-русски?) было неидеальным. Хотя вроде делал так же, как и другие. Наверное, всё-таки в отжиге я чего-то не понимаю. В итоге плюнул и написал генетический алгоритм, в которых понимаю хорошо (и вообще, для стохастики я фанат population methods, в противовес single-state). Получил семёрки и десятки. Потом этот же генетический алгоритм с вариациями использовал и для остальных задач и тоже без проблем получал там семёрки, а иногда и десятки. В задаче про логистику пришлось ещё сделать предварительную кластеризацию точек (тупой K-means), иначе хороший результат не находился.
В курсе установили пороги в 224 балла за сертификат, и в 300 баллов за сертификат с отличием. На каком-то этапе я из курса выпал и за неделю до окончания у меня с трудом хватало на обычный сертификат. Думал, дотяну до сертификата, а отличия буду зарабатывать на следующей итерации курса. Но когда, как-то решив все основные задачи, оказалось, что у меня есть порядка 240 баллов, решил дотянуть до distinction’а и посвятил сколько мог времени на доведение программ до ума.
Добор баллов тоже превратился в задачу оптимизации - вариацию укладки рюкзака: какими именно задачами добрать недостающие баллы, ещё и имея в виду шансы на успех в этих задачах. Выбор курсов тоже, кстати, является конкретной задачей про рюкзак :) (По качеству представленных на Курсере курсов университет Мельбурна, кстати, рулит. Практически все представленные курсы интересны. Кроме дискретной оптимизации рулит эпигенетика, интересна физиология спорта. Да и поведение животных я тоже хочу послушать. Было бы достаточно времени, глянул бы и остальные)
Наоптимизировал всё что мог генетическими алгоритмами. Потом принялся за усовершенствования жадных алгоритмов, это позволило неплохо набрать баллов, но до 300 всё равно не хватало ещё порядка 20-30. В какой-то момент решил заюзать внешний солвер (SCIP). Мне изначально казалось, что это неспортивно, но написать свой солвер по материалам лекций казалось малореальным, а сделать это за несколько оставшихся дней тем более. К тому же авторы курса таки рассчитывали на использование подобных решений, ибо выложили материалы и рекомендовали это на форуме. Переписал задачу про расположение складов в терминах mixed integer programming, получил несколько десяток и семёрок. Добил хитрый жадный алгоритм для раскраски графа, набрал немного мелочи в паззлах (втупую собранные генетикой 15 баллов). Ноут непрерывно работал полностью загруженный несколько дней. В предпоследнюю ночь перед дедлайном не хватало нескольких баллов, но за ночь таки улучшил одну семёрку до десятки и что-то ещё получил за один из паззлов. Набрал в сумме 302 балла и со спокойной душой выключил компьютер.
В конечном счёте у меня осталась только одна тройка - за коммивояжера размером 33810 - это больше, чем задачка про Швецию, где было 24978 точек.
Пожалуй, на данный момент это самый сложный курс из всех пройденных. Второй по сложности - Хинтоновский Neural networks for machine learning, третий - NLP Маннинга и Журафского. Интересно, где бы тут оказался PGM, если бы я его брал.
По ходу курса неожиданно пригодились подзабытые на полке две книжки: Essentials of Metaheuristics от Sean Luke и шпрингеровская Design of Modern Heuristics. Они помогали мне вдохновляться.
А ещё Мила подарила мне прикольную игру про строительство железных дорог - Ticket to Ride. Конкретная графовая задача оптимизации :) Особенно прикольно играть вчетвером-впятером.
Optimization is everywhere. And for optimistic people.