Hotdry.
归档
compiler-design

MiniZinc约束建模Partridge Packing Problem：高效2D正方形完美装箱策略

详解MiniZinc下Partridge Packing Problem的约束建模，包括diffn非重叠、精确填充与边缘放置限制、对称性打破技巧，提供OR-Tools CP-SAT求解参数与性能优化清单。

Partridge Packing Problem 是一个经典的 2D 完美装箱难题，源于 1996 年 G4G2 会议，由 Robert T. Wainwright 提出。其核心是将 1 个 1×1、2 个 2×2、...、n 个 n×n 正方形完美填充进边长为三角数 T_n = n (n+1)/2 的大正方形中。面积精确匹配：∑_{i=1}^n i・i^2 = [T_n]^2。由于组合爆炸，该问题是 NP 难题，n=2~7 无解，n≥8 有解，且难度随 n 二次增长。

使用 MiniZinc 高层次约束建模语言，可高效表达此类离散优化问题。MiniZinc 编译为 FlatZinc，兼容多种求解器如 CP-SAT、Chuffed，支持全局约束如 diffn（非重叠）和 cumulatives（资源轮廓）。本文聚焦单一技术点：通过基础 diffn 约束 + 强化隐含约束 + 对称打破，实现 n=8~11 高效求解，提供可落地模型参数与配置清单。

基础模型：变量与核心约束

定义参数 n（问题规模），生成 parts 枚举（总数 T_n），位置集 Pos=1..T_n，大小数组 sizes（逆序排列大方块优先，便于启发搜索）：

int: n;
set of int: N = 1..n;
int: triangular_n = (n * (n+1)) div 2;
enum Parts = P(1..triangular_n);
set of int: Pos = 1..triangular_n;
array[Parts] of N: sizes = array1d(Parts, reverse([size | size in N, copy in 1..size]));

决策变量：每个 parts 的左下角坐标 x [p]、y [p] ∈ Pos，确保方块不超出边界：

array[Parts] of var Pos: x;
array[Parts] of var Pos: y;
constraint forall(p in Parts) (x[p] + sizes[p] - 1 in Pos /\
                              y[p] + sizes[p] - 1 in Pos);

非重叠核心：diffn 全局约束，确保所有方块矩形不交叠（源于 1994 CHIP 论文）：

constraint diffn(x, y, sizes, sizes);

求解：satisfy（纯可满足），依赖求解器自由搜索。输出 ASCII 艺术或 vis_geost_2d 可视化，便于验证。

此基础模型对 n=8 需 3.5 小时（OR-Tools CP-SAT，10 线程），因缺乏强传播。

强化约束：隐含约束与精确填充

添加隐含约束（implied_constraint 注解，提升传播），首推精确行列表面填充：每行 / 列重叠方块大小总和精确等于 T_n（利用完美填充特性）：

predicate exact_fill(array[Parts] of var Pos: xy, Pos: rc) =
  let {
    array[Parts] of var bool: on_rc = [rc - sizes[p] < xy[p] /\ xy[p] <= rc | p in Parts]
  } in sum(p in Parts)(sizes[p] * on_rc[p]) = card(Pos);

constraint implied_constraint(forall(rc in Pos)(exact_fill(x, rc)));
constraint implied_constraint(forall(rc in Pos)(exact_fill(y, rc)));

此约束将 n=8 时间降至 4 分钟，远胜 cumulatives（轮廓约束，反倒变慢，凸显基准测试重要）。

边缘放置限制：大方块不能太靠近边框，否则小方块总面积不足填充间隙。计算 min_distance_from_edge = min {d | d * size> available_area (d)}，available_area (size) = [size*(size+1)/2]^2：

function int: available_area(int: size) = let {int: t = (size * (size + 1)) div 2;} in t * t;
constraint implied_constraint(
  forall(size in N where size > 1)(
    let {
      int: min_distance_from_edge = min({d | d in 1..size where d * size > available_area(d-1)});
      set of int: forbidden_placements = 2..(1+min_distance_from_edge) union
                                        max(Pos)-size-min_distance_from_edge..<max(Pos)-size;
      set of Pos: allowed_placements = Pos diff forbidden_placements;
    } in forall(p in Parts where sizes[p] = size)(x[p] in allowed_placements /\ y[p] in allowed_placements)
  )
);

结合精确填充，n=8 中位数 73 秒。

对称性打破：提升搜索效率

同大小方块不可区分，引入建模对称。按字典序链约束（lex_chain_less）排序同大小 parts 的 (x,y) 位置：

constraint symmetry_breaking_constraint(
  forall(size in N)(
    let {
      set of Parts: PartsWithSize = {p | p in Parts where sizes[p] == size};
      set of int: P = 1..card(PartsWithSize);
      array[1..2, P] of var Pos: placements = array2d(1..2, P, [[x[p], y[p]][x_or_y] | x_or_y in 1..2, p in PartsWithSize]);
    } in lex_chain_less(placements)
  )
);

最终模型 n=8 平均 1.9 秒（10 次运行 0.8~3.6 秒），板对称（旋转 / 翻转）可进一步打破，但需谨慎结合。

可落地参数与求解器配置清单

模型参数（n=8~11）：

  • 线程：CPU 核心数（e.g.,10）。
  • 搜索：free（自动），或 position smallest indomain_min（左下优先）。
  • 内存：n=11 超 3GB。

求解器性能（M1 Max 64GB，OR-Tools CP-SAT 9.14）：

n parts 边长 时间 失败数
8 36 36 1.4s 15k
9 45 45 61s 651k
10 55 55 13m 6.5M
11 66 66 51m 15M

其他求解器：Huub（n=8:8s，n=9 超时）；Pumpkin（n=9:10m）；SICStus geost 自定义模型更快（n=12:71m）。

监控与回滚：

  • 统计：failures<1M（好），propagations/T>10^7。
  • 超时阈值：n=10>30m 回滚基础模型。
  • 风险：随机性强，多跑 3 次取中位。

工程化清单：

  1. 下载模型：zayenz.se/files/blog/partridge-packing/partridge-packing-model.mzn。
  2. MiniZinc IDE：设 10 线程，free search。
  3. 验证：vis_geost_2d 或 ASCII，确保无隙 / 重叠。
  4. 扩展 3D：替换 diffn 为 geost（支持非矩形 / 旋转），sizes 为 (xlen,ylen,zlen)，Pos 扩展三维。
  5. 生产：嵌入 Python（minizinc.py），参数化 n，API 输出 JSON 位置。

此策略适用于物流 2D 裁切、PCB 布局等。MiniZinc 优势：求解器无关，易迭代。

资料来源：

查看归档