Разбор задачи «Назначение студентов в группы»
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
Строка 74: | Строка 74: | ||
* BigM не обязательно должно быть большой константой. | * BigM не обязательно должно быть большой константой. | ||
* Смело смотрите решения друг-друга, подглядывая интересное и полезное. | * Смело смотрите решения друг-друга, подглядывая интересное и полезное. | ||
+ | {{wl-publish: 2023-11-13 10:52:39 +0000 | StasFomin }} |
Текущая версия на 10:52, 13 ноября 2023
В рамках ревью ваших заданий (конкретно Участник:Bagurgl/Назначение студентов в группы), как-то возникло желание сделать разбор-решение задачи Optprob/Назначение_студентов_в_группы, прямо в ноутбуке Участник:Bagurgl.
Можете смотреть решение там, но если Участник:Bagurgl вдруг решит удалить сильно переписать, то на всякий случай, сохраню эту свое видение правильной компактной и верифицируемой бизнес-модели и тут.
def get_model(распределение_по_уровням, рейтинг_уровня, число_групп, макс_размер_группы): m = pe.ConcreteModel() число_уровней = len(распределение_по_уровням) блестящий = число_уровней - 1 отличник = блестящий - 1 m.I = range(число_уровней) m.J = range(число_групп) m.x = pe.Var(m.J, m.I, within=pe.NonNegativeIntegers) def рейтинг_группы(j): return sum([рейтинг_уровня[i] * m.x[j, i] for i in m.I]) m.макс_рейтинг = pe.Var() @m.Constraint(m.J) def макс_рейтинг_больше_всех(m, j): return m.макс_рейтинг >= рейтинг_группы(j) m.мин_рейтинг = pe.Var() @m.Constraint(m.J) def мин_рейтинг_меньше_всех(m, j): return m.мин_рейтинг <= рейтинг_группы(j) @m.Objective(sense=pe.minimize) def дисбаланс(m): return m.макс_рейтинг - m.мин_рейтинг @m.Constraint(m.I) def распределение_по_уровням_совпадает(m, i): return sum(m.x[..., i]) == распределение_по_уровням[i] @m.Constraint(m.I) def размер_группы_не_превосходит_заданный(m, j): return sum(m.x[j, ...]) <= макс_размер_группы m.есть_блестящий = pe.Var(m.J, within=pe.Binary) @m.Constraint(m.J, [0, 1]) def установим_блестящего(m, j, t): if t: return распределение_по_уровням[блестящий] * m.есть_блестящий[j] >= m.x[j, блестящий] return m.есть_блестящий[j] <= m.x[j, блестящий] @m.Constraint(m.J, m.J) def если_у_вас_есть_блестящий_а_у_нас_нет_докажите_что_у_вас_нет_лишнего(m, j, k): if j == k: return pe.Constraint.Skip return m.x[k, блестящий] <= 1 + распределение_по_уровням[блестящий] * (m.есть_блестящий[j] + 1 - m.есть_блестящий[k]) return m @m.Constraint(m.J, m.J) def если_у_вас_есть_блестящий_а_у_нас_нет_мы_требуем_не_меньше_отличников(m, j, k): if j == k: return pe.Constraint.Skip return m.x[j, отличник] - m.x[k, отличник] >= -распределение_по_уровням[отличник] * (m.есть_блестящий[j] + 1 - m.есть_блестящий[k]) return m
Краткие выводы (что вспомнил):
- Старайтесь сделать компактно и понятно (вам еще потом видео записывать, а кому-то его придется смотреть и все это читать).
- Если можно обойтись без формул-латеха — то и не надо. Это как раз бич бизнес-оптимизационных статей, куча невнятных переменных, запутанные формулы — это только затрудняет верификацию.
- Можно заводить промежуточные переменные-функции, для большей понятности
- Удобно модель возвращать функцией от входных данных (легче играть с параметрами).
- Делайте модель итерационно, смотрите что получается — и добавляйте и меняйте ограничения, поэкспериментируйте и с входными данными.
- Давайте использовать по умолчанию солвер «SCIP», меньше вероятности, что затупит даже на этих детских задачах (в этом году пока мы без Gurobi и других более эффективных солверов, хотя я пытаюсь их вернуть).
- Посмотрите в решении функции мои хелперы как быстро смотреть решение — ну можете доработать и свои, полезно сделать какую-нибудь интересную визуализацию (ну если там графы какие или еще что вдруг).
- BigM не обязательно должно быть большой константой.
- Смело смотрите решения друг-друга, подглядывая интересное и полезное.