Лучшая практика для решения большого количества похожих экземпляров рюкзака

Я работаю над проектом, в котором мне нужно решить тысячи маленьких и больших «простых» примеров задач, подобных ранцу. Все мои экземпляры имеют одинаковую структуру, одинаковые ограничения, но различаются количеством элементов (т.е. переменных). Домены могут быть зафиксированы для всех экземпляров.

Я успешно интегрировал minizinc в рабочий процесс, который

  1. извлекать соответствующие данные из базы данных,
  2. сгенерировать модель .mzn (включая начальные присвоения переменных)
  3. вызовите драйвер minizinc для решателя CBC и,
  4. проанализировать и интерпретировать решение.

Теперь я столкнулся с узким местом производительности на этапе выравнивания для больших экземпляров (см. Подробную статистику выравнивания). Сглаживание занимает до 30 секунд, а оптимальное решение - менее 1 секунды.

Я безуспешно пытался отключить «оптимизированное выравнивание», я также пытался разделить цепочку инструментов (mzn2fzn, затем mzn-cbc); и, наконец, попытался разделить определения модели и данных, но не заметил каких-либо значительных улучшений.

Если это поможет, я определил набор ограничений, вызывающих проблему:

...
array[1..num_items] of int: item_label= [1,12,81,12, [10 000 more ints between 1..82], 53 ];

int: num_label = 82;
array[1..num_label] of var 0..num_items: cluster_distribution;
constraint forall(i in 1..num_label)(cluster_distribution[i]==sum(j in 1..num_items)(item_indicator[j] /\ item_label[j]==i));
var 1..num_label: nz_label;
constraint non_zero_label = sum(i in 1..num_label) (cluster_distribution[i]>0);
....

По сути, каждый из 5000 элементов имеет метку (из ~ 100 возможных меток), и я стараюсь (среди других целей) максимизировать количество разных меток (переменная non_zero_label). Я пробовал разные рецепты, но этот, кажется, самый эффективный.

Может ли кто-нибудь дать мне совет о том, как ускорить эту фазу выравнивания? Как бы вы подошли к задаче решения тысяч «похожих» случаев?

Было бы полезно напрямую сгенерировать файл MPS, а затем вызвать CBC изначально? Я ожидаю, что minizinc будет достаточно эффективным при компиляции файла MPS, но, может быть, я мог бы получить ускорение, используя повторяющуюся структуру экземпляров? Однако я опасаюсь, что это более или менее сведется к перекодировке плохо написанной полусырой псевдо-кастомной версии minizinc, что кажется неправильным.

Спасибо !

Моя системная информация: Os X и Ubuntu, mnz 2.1.7.

Compiling instance-2905-gd.mzn
MiniZinc to FlatZinc converter, version 2.1.7
Copyright (C) 2014-2018   Monash University, NICTA, Data61
Parsing file(s) 'instance-2905-gd.mzn' ...
processing file '../share/minizinc/std/stdlib.mzn'
processing file '../share/minizinc/std/builtins.mzn'
processing file '../share/minizinc/std/redefinitions-2.1.1.mzn'
processing file '../share/minizinc/std/redefinitions-2.1.mzn'
processing file '../share/minizinc/linear/redefinitions-2.0.2.mzn'
processing file '../share/minizinc/linear/redefinitions-2.0.mzn'
processing file '../share/minizinc/linear/redefinitions.mzn'
processing file '../share/minizinc/std/nosets.mzn'
processing file '../share/minizinc/linear/redefs_lin_halfreifs.mzn'
processing file '../share/minizinc/linear/redefs_lin_reifs.mzn'
processing file '../share/minizinc/linear/domain_encodings.mzn'
processing file '../share/minizinc/linear/redefs_bool_reifs.mzn'
processing file '../share/minizinc/linear/options.mzn'
processing file '../share/minizinc/std/flatzinc_builtins.mzn'
processing file 'instance-2905-gd.mzn'
 done parsing (70 ms)
Typechecking ... done (13 ms)
Flattening ... done (16504 ms), max stack depth 14
MIP domains ...82 POSTs [ 82,0,0,0,0,0,0,0,0,0, ], LINEQ [ 0,0,0,0,0,0,0,0,82, ], 82 / 82 vars, 82 cliques, 2 / 2 / 2 NSubIntv m/a/m, 0 / 127.085 / 20322 SubIntvSize m/a/m, 0 clq eq_encoded  ...  done (28 ms)
Optimizing ... done (8 ms)
Converting to old FlatZinc ... done (37 ms)
Generated FlatZinc statistics:
Variables: 21258 int, 20928 float
Constraints: 416 int, 20929 float
    This is a minimization problem.
Printing FlatZinc to '/var/folders/99/0zvzbfcj3h16g04d07w38wrw0000gn/T/MiniZinc IDE (bundled)-RzF4wk/instance-2905-gd.fzn' ... done (316 ms)
Printing .ozn to '/var/folders/99/0zvzbfcj3h16g04d07w38wrw0000gn/T/MiniZinc IDE (bundled)-RzF4wk/instance-2905-gd.ozn' ... done (111 ms)
Maximum memory 318 Mbytes.
  Flattening done, 17.09 s

knapsack-problem constraint-programming minizinc
person massyah    schedule 28.05.2018    source источник
comment
Я ожидал, что выполнение minizinc каждый раз приведет к увеличению накладных расходов. Поскольку проблемы просты, нельзя ли напрямую вызвать CBC API? Это будет быстрее, чем просмотр файла MPS.   -  person Erwin Kalvelagen    schedule 29.05.2018

Ответы (1)


arrow_upward
3
arrow_downward

Если вы решаете множество экземпляров одного и того же класса проблемы и у вас много времени на выравнивание, то есть два общих подхода, которые вы можете использовать: либо вы оптимизируете MiniZinc, чтобы минимизировать время выравнивания, либо вы можете реализовать модель в API прямого решения. .

Первый вариант лучше всего, если вы хотите сохранить универсальность решателей. Чтобы оптимизировать время выравнивания, главное, что вы хотели бы исключить, - это «временные» переменные: переменные, которые создаются, а затем отбрасываются. При выравнивании модели много времени уходит на разрешение переменных, в которых нет необходимости. Это необходимо для минимизации пространства поиска при решении. Временные переменные могут быть сгенерированы в пониманиях, циклах, let-выражениях и реификациях. Для вашей конкретной модели Глеб опубликовал оптимизацию для for- цикл в вашем ограничении:

constraint forall(i in 1..num_label)(cluster_distribution[i]==sum(j in 1..num_items where item_label[j]==i)(item_indicator[j]));

Другой вариант может быть лучшим, если вы хотите интегрировать свою модель в программный продукт, поскольку вы можете предложить прямое взаимодействие с решателем. Вам придется «сгладить» вашу модель / данные вручную, но вы можете сделать это более ограниченным способом, специфичным только для вашей цели. Поскольку это не универсальное средство, оно может быть очень быстрым. Подсказки для модели можно найти, просмотрев сгенерированный FlatZinc для разных экземпляров.

person Dekker1    schedule 01.06.2018
comment
Спасибо Деккеру (а также Глебу), это определенно сокращает время, необходимое для фазы выравнивания. - person massyah; 04.06.2018