Лучшая практика для решения большого количества подобных экземпляров ранца - PullRequest
Новая
       28

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

0 голосов
/ 29 мая 2018

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

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

  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 var).Я пробовал различные формулировки, но этот, кажется, самый эффективный.

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

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

Спасибо!

Информация о моей системе: 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

1 Ответ

0 голосов
/ 01 июня 2018

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

Первый вариант является лучшим, если вы хотите сохранить общность между решателями.Чтобы оптимизировать время выравнивания, главное, что вы хотели бы удалить, - это «временные» переменные: переменные, которые создаются, а затем выбрасываются.Большая часть времени при выравнивании модели идет на разрешение переменных, которые не нужны.Это должно минимизировать пространство поиска при решении.Временные переменные могут быть сгенерированы в пониманиях, циклах, выражениях-выражениях и соотношениях.Для вашей конкретной модели Глеб опубликовал оптимизацию для цикла 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 для разных случаев.

...