Просмотр исходного текста страницы Blog:Advanced Algorithms/Разбор задачи «Назначение студентов в группы»

В рамках ревью ваших заданий (конкретно [[Участник:Bagurgl/Назначение студентов в группы]]), как-то возникло желание сделать разбор-решение задачи [[Optprob/Назначение_студентов_в_группы]], прямо в ноутбуке [[Участник:Bagurgl]].

{{vimeoembed|883845305|800|450}}

Можете смотреть решение там, но если [[Участник:Bagurgl]] вдруг решит удалить сильно переписать, то на всякий случай, сохраню эту свое видение правильной компактной и верифицируемой бизнес-модели и тут.

<source lang="python">
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
</source>

Краткие выводы (что вспомнил):
* Старайтесь сделать компактно и понятно (вам еще потом видео записывать, а кому-то его придется смотреть и все это читать).
** Если можно обойтись без формул-латеха — то и не надо. Это как раз бич бизнес-оптимизационных статей, куча невнятных переменных, запутанные формулы — это только затрудняет верификацию.
** Можно заводить промежуточные переменные-функции, для большей понятности
* Удобно модель возвращать функцией от входных данных (легче играть с параметрами).
* Делайте модель итерационно, смотрите что получается — и добавляйте и меняйте ограничения, поэкспериментируйте и с входными данными.
* Давайте использовать по умолчанию солвер «SCIP», меньше вероятности, что затупит даже на этих детских задачах (в этом году пока мы без Gurobi и других более эффективных солверов, хотя я пытаюсь их вернуть).
* Посмотрите в решении функции мои хелперы как быстро смотреть решение — ну можете доработать и свои, полезно сделать какую-нибудь интересную визуализацию (ну если там графы какие или еще что вдруг). 
* BigM не обязательно должно быть большой константой.
* Смело смотрите решения друг-друга, подглядывая интересное и полезное.
{{wl-publish: 2023-11-13 10:52:39 +0000 | StasFomin }}