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

Question

我正在做一个项目，我需要解决成千上万个从小到大的 "simple" 类似背包的问题。我的所有实例都具有相同的结构、相同的约束，但项目数量（因此变量）不同。可以为所有实例固定域。

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

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

我现在在大型实例的扁平化阶段遇到了性能瓶颈（参见详细的扁平化统计信息）。扁平化最多需要 30 秒，而求解最优需要不到 1 秒。

我试过禁用 "optimized flattening" 无济于事，我也试过拆分工具链（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）。我尝试过各种配方，但这个似乎是最有效的。

任何人都可以为我提供一些关于如何加速这个扁平化阶段的指导吗？您将如何处理解决数千个 "similar" 个实例的任务？

直接生成 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

Answer 1

如果您正在解决同一个问题的许多实例化 class 并且您运行进入大的展平时间，那么您可以采用两种通用方法：要么优化 MiniZinc 以最小化展平时间或者您可以在直接求解器中实现模型 API.

如果你想保持求解器之间的通用性，第一个选项是最好的。要优化展平时间，您要消除的主要内容是 "temporary" 变量：创建然后丢弃的变量。扁平化模型的很多时间都用于解决不必要的变量。这是为了在求解时尽量减少搜索space。临时变量可能会在理解、循环、let 表达式和具体化中生成。对于您的特定模型 Gleb posted 约束中 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]));

如果您想将模型集成到软件产品中，那么另一个选项可能是最好的选择，因为您可以提供与求解器的直接交互。您将不得不手动 "flatten" 您的 model/data，但您可以根据您的目的以更有限的方式进行。因为它不是通用的，所以它可以非常快。通过查看为不同实例生成的 FlatZinc，可以找到模型的提示。

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

Best practice to solve large number of similar knapsack instances

knapsack-problem

constraint-programming

minizinc