Раздел $N$ предметы в $K$ разделы одинакового размера с сохранением групп в исходных элементах

Aug 16 2020

Предположим, есть $N$ предметы, которые входят $M$группы. Позволять$c_i \in \{1, ..., M\}$ для $i=1, ..., N$ представляют членство в группе для элемента $i$. Я хотел бы найти более грубое разделение предметов на$K$ новые группы, где $K < M$, с двумя ограничениями:

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

Моя первоначальная мысль - сформулировать это как нелинейную целочисленную программу, где $y_{ij} = 1$ если элемент $i$ закреплен за разделом $j$и равен нулю в противном случае. Тогда у меня был бы набор ограничений:

  1. $\sum_{j=1}^K y_{ij} = 1$ для $i=1,..., N$ (каждый элемент должен быть назначен ровно одному разделу)
  2. $y_{ij} = y_{\ell j}$ для всех $j=1, ..., K$ если $c_i = c_\ell$ (элементы в одной группе должны быть назначены в один раздел)

и тогда я мог определить $N_j = \sum_{i=1}^N y_{ij}$ и минимизировать

$$\sum_{j=1}^K \left(N_j - \frac NK \right)^2.$$

Однако конкретная цель здесь на самом деле не имеет значения. Пока$N_j$ близок к $N/K$ для всех $j$, Мне все равно, если это в $\ell_2$ или $\ell_1$ смысл или что-то еще в этом роде.

Мои вопросы:

  1. Есть ли лучшая постановка этой проблемы с особенно простым решением?
  2. Какие алгоритмы точно решат эту проблему? Есть ли способы получить быстрые жадные приблизительные решения?
  3. Я предполагаю, что мне нужно будет использовать существующее программное обеспечение для оптимизации, чтобы получить свое решение. Есть ли здесь какие-то стандартные варианты для пользователя Python / Julia / R? (Примеры кода очень ценятся!)

Некоторые дополнительные сведения: по сути, я ищу более эффективный (в вычислительном отношении) подход к перекрестной проверке исключения-группировки. Текущий стандарт - оставлять одну группу за раз, чтобы вы соответствовали$M$ модели, где $M$может быть довольно высоким. На практике что-то вроде$K=5$ или $K=10$достаточно для статистических целей, и перекрестная проверка будет иметь нужные нам свойства, если все в одной группе входят в одну и ту же складку, а складки примерно одинакового размера. Так подходит$M >> 10$ модели, когда есть много групп, часто неэффективны и ненужны.

Ответы

2 RobPratt Aug 16 2020 at 04:07

Один из подходов состоит в том, чтобы рассматривать группы как задания, при этом продолжительность каждого задания равна количеству элементов в его группе. Теперь запланируйте эти задания на$K$ идентичные машины, что сводит к минимуму время изготовления, то есть минимизирует $\max_j N_j$. Эвристика LPT выполняется быстро и дает$(2-1/K)$-приближение.

1 prubin Aug 17 2020 at 02:18

Первый вопрос: в модели IP вам не нужна двоичная переменная для каждой комбинации элемента и раздела. Учитывая ваше требование, чтобы группы хранились вместе, вам просто нужен двоичный файл для каждой комбинации группы и раздела. Ваш$y_{ij}=y_{\ell j}$Ограничения позволят функции предварительного решения решателя уменьшить модель до этого размера, но вы также можете начать с меньшей формулировки. Кроме того, вместо того, чтобы делать проблему квадратичной, я, вероятно, минимизировал бы разницу между наименьшим и наибольшим размером раздела, которая является линейной. Это не обязательно дает «особенно простую» модель для решения, но в зависимости от размеров вашей проблемы и вашего IP-решателя (и вашего терпения) это может быть достаточно просто.

Второй вопрос: вы можете решить проблему с помощью модели IP и решателя IP. Быстрая эвристика, которая могла бы работать достаточно хорошо, - это начать с$K$ пустые разделы, отсортируйте группы в порядке убывания размера, затем назначьте каждую группу самому маленькому в данный момент разделу.

Третий вопрос: я не могу говорить от имени Джулии или Python (хотя я знаю некоторые решатели IP для Python), но с RI был бы склонен использовать пакет OMPR (DSL для LP / IP) для написания модели. OMPR, в свою очередь, будет полагаться на рентабельность инвестиций для решения модели, и как OMPR, так и рентабельность инвестиций потребуют от вас загрузки подключаемого модуля для конкретного решателя (и, конечно же, установки соответствующего решателя).

Я взломал ноутбук R, используя OMPR и ROI с соответствующими плагинами CPLEX. На случайной тестовой задаче с$N=5700$, $M=130$ и $K=10$описанная мной эвристика обычно дает разброс размеров разделов 5 (размеры от 567 до 572), а модель IP имеет десять разделов по 570 каждый (разброс = 0). Эвристика заняла (небольшую) долю секунды. Построение модели IP и ее решение с помощью CPLEX заняло около девяти секунд.

Как всегда, ваш пробег будет другим.

ДОБАВЛЕНИЕ: я подозревал (правильно), что использование круглых чисел для размеров проблемы может сделать вещи лучше, поэтому я попробовал $N=5723$, $M=137$ и $K=10$(что гарантирует, что ни одно решение не имеет одинаковых размеров разделов). IP-решение управляло разбросом в 1 (в некоторых разделах было 572 элемента, в некоторых - 573, что все же лучше, чем я думаю в целом достижимо). Эвристическое решение имело разброс 30 (размеры разделов от 552 до 582).

ПРИЛОЖЕНИЕ 2: Я добавил эвристику попарного обмена после того, что Роб называет эвристикой LPT. В примере с$N=5723$и т. д. эвристика парного свопа уменьшила спред с 30 до 2, что не совсем оптимально (оптимальным является 1), но намного ближе. Как и LPT, эвристика подкачки в этом примере заняла менее одной секунды.