解决大量类似背包实例的最佳实践

Question

我正在做一个项目，在这个项目中，我需要解决成千上万个类似背包问题的小到大的“简单”实例。我的所有实例都有相同的结构、相同的约束，但项的数量不同(因此变量)。可以为所有实例修复域。

我已经成功地将minizinc集成到一个工作流中

1. 从数据库中提取相关数据，
2. 生成.mzn模型(包括初始变量赋值)
3. 为CBC解算器调用minizinc驱动程序，
4. 解析并解释解决方案。

现在，对于大型实例(cf冗长的扁平统计数据)，我在平坦阶段遇到了性能瓶颈。平坦化需要30秒的时间，而求解到最优需要少于1秒。

我试图禁用“优化的扁平化”，但徒劳无功，我还试图拆分工具链(mzn2fzn，然后是mzn2fzn)；最后，我尝试分离模型和数据定义，但没有看到任何明显的改进。

如果有帮助，我已经确定了导致问题的一组约束：

...
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文件方面非常有效，但是也许我可以通过利用实例的重复结构来加快速度？然而，我担心这或多或少会归结为重新编码一个写得很差、半生不熟的伪定制版本的minizinc，这感觉不太对。

谢谢！

我的系统信息: Os和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

Answer 1

如果您正在解决同一个问题类的许多实例化问题，并且遇到了较大的扁平化时间，那么您可以采取两种通用方法:要么优化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，可以找到模型的提示。