Разбор задачи «Назначение студентов в группы»

Ссылки сюда (5) →

В рамках ревью ваших заданий (конкретно Участник: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 не обязательно должно быть большой константой.
• Смело смотрите решения друг-друга, подглядывая интересное и полезное.

[ Хронологический вид ]Комментарии

(нет элементов)

Войдите, чтобы комментировать.

— Стас Фомин • 10:52, 13 ноября 2023 • нет комментариев