Комментарии 4
Алексей, спасибо за статью!
В данном подходе интересует алгоритм выбора столбцов для добавления в базис. С одной стороны мы режем задачу на кусочки и постепенно решаем задачу, что уменьшает время на поиск конкретного решения. С другой - получаем тонну итераций, если переменных действительно много.
Возникает творческое желание добавлять в базис не по одной переменной, а батчами — сразу несколько. Очевидно, что в этом желании есть много подводных камней. Если у вас был опыт подобных экспериментов или, в целом, попыток уменьшить число итераций — буду благодарен.
В работе с алгоритмом генерации столбцов всегда добавлял группу столбцов. В самом простом случае на каждой итерации алгоритма добавлял все столбцы с отрицательной приведенной стоимостью.
В задачах с большим кол-вом "похожих" столбцов приходилось вводить дополнительные эвристики (основанные на доминировании), чтобы прореживать группу столбцов.
В статье отмечал, что при добавлении группы столбцов происходит снижение компрессии задачи. Зачастую, это оправдывает себя по производительности.
Какие проблемы встречались при использовании групп столбцов? И как их удавалось решать?
Самый первый кейс, добавление всех столбцов с отрицательной приведенной стоимостью. Очень быстро росла модель, компрессия доходила всего да 30-50% полной задачи. В этом случае перешли на выбор TopN столбцов с наиболее отрицательной приведенной стоимостью. Итого, 10-20% исходной задачи.
Второй кейс, выбор уникальных столбцов. Вводили метрику похожести. Из группы похожих столбцов брали только часть, около 10-15% столбцов из группы похожих.
Алгоритм генерации столбцов (Column Generation)