Blog:Advanced Algorithms/Разбор задачи «Назначение студентов в группы» - История изменений

StasFomin в 10:52, 13 ноября 2023

2023-11-13T10:52:39Z

StasFomin в 03:27, 13 ноября 2023

2023-11-13T03:27:41Z

StasFomin: Новая страница: «В рамках ревью ваших заданий (конкретно Участник:Bagurgl/Назначение студентов в группы), к…»

2023-11-13T03:23:36Z

Новая страница: «В рамках ревью ваших заданий (конкретно Участник:Bagurgl/Назначение студентов в группы), к…»

Новая страница

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

Можете смотреть решение там, но если [[Участник: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 не обязательно должно быть большой константой.

← Предыдущая		Версия 10:52, 13 ноября 2023
Строка 74:		Строка 74:
	* BigM не обязательно должно быть большой константой.		* BigM не обязательно должно быть большой константой.
	* Смело смотрите решения друг-друга, подглядывая интересное и полезное.		* Смело смотрите решения друг-друга, подглядывая интересное и полезное.
		+	{{wl-publish: 2023-11-13 10:52:39 +0000 \| StasFomin }}

@@ Строка 1: / Строка 1: @@
 В рамках ревью ваших заданий (конкретно [[Участник:Bagurgl/Назначение студентов в группы]]), как-то возникло желание сделать разбор-решение задачи [[Optprob/Назначение_студентов_в_группы]], прямо в ноутбуке [[Участник:Bagurgl]].
 Можете смотреть решение там, но если [[Участник:Bagurgl]] вдруг решит удалить сильно переписать, то на всякий случай, сохраню эту свое видение правильной компактной и верифицируемой бизнес-модели и тут.
@@ Строка 71: / Строка 73: @@
 * Посмотрите в решении функции мои хелперы как быстро смотреть решение — ну можете доработать и свои, полезно сделать какую-нибудь интересную визуализацию (ну если там графы какие или еще что вдруг).
 * BigM не обязательно должно быть большой константой.