Создание сбалансированных теннисных раундов

Question

Мы группа из 20 человек, и нам нравится играть в 2 против 2 теннисных матчей. Каждый из нас играет по одному матчу в каждом раунде, и мы делаем всего 5 раундов, поэтому каждый играет 5 матчей. Похожие есть два ограничения:

• Каждые имеют различный уровень (от 1 до 5), так что матчи должны быть сбалансированы: два игрока с уровнями 5 и 5 shoulnd't быть согласованы с двумя уровнями 1. Таким образом, между две команды, разница в уровне должна быть ниже или равна 1,5.
  Ej .: уровень 1.5 и уровень 2 против уровня 2 и уровень 2.5. Разница в уровне между командами - 1, поэтому матч принимается.
• Если два игрока играют вместе в одном матче, они не должны играть снова в следующих раундах.

Мне удалось создать скрипт python, который делает указанное выше, но для завершения в зависимости от уровня людей требуется около 20 минут: /. То, что я делаю, это перетасовать список с каждым в нем, разбить его на 5 списков из 4 человек, проверить, удовлетворены ли условия и повторить для каждого раунда.

Я пробовал моделировать проблему, чтобы решить ее с помощью линейного программирования (LP), но я не знаю, для чего моя функция оптимизирована для начала ... Любые идеи о том, как это сделать с LP или без него?

Заранее благодарен!

Answer 1

Вы можете использовать фиктивный объект или даже попытаться свести к минимуму максимальную разницу в уровнях.

Моя модель MIP не является полностью тривиальной, но она решает довольно быстро (примерно через секунду, используя коммерческий решатель).

Результаты выглядят хорошо на первый взгляд:

Я предположил, два игрока не могут быть в одной команде более одного раза. То есть не только в одной игре. То есть в моем случае вы можете играть против другого игрока более одного раза.

Более сложный пример можно найти here.