如何添加约束优化Minizinc布尔网格最小化求解模型？

问题背景 #

我最近用Minizinc求解一个布尔网格优化问题，需求如下：

• 给定H×W的布尔变量网格
• 核心约束：若某变量为false，则其上下左右（不含对角线）相邻变量中至少一个为true
• 目标：最小化网格中true值的数量

当前代码在H、W≤20时可正常运行，但求解32×32网格时速度极慢（运行1小时仍未得到最优解），使用OR-TOOLS求解器。想添加对角线对称性破缺约束，但不清楚非正方形网格的实现方式，寻求模型优化建议。

现有代码 #

include "globals.mzn";

int: H = 20;
int: W = 20;
array[1..H, 1..W] of var bool: grid;

% Objective
var int: totsum = sum(i in 1..H, j in 1..W)(grid[i, j]);

% 核心约束：false变量的上下左右至少一个为true
constraint forall(i in 1..H, j in 1..W)(
    not(grid[i, j]) -> grid[max(1, i-1), j] \/ grid[min(i+1, H), j] \/ grid[i, max(1, j-1)] \/ grid[i, min(W, j+1)]
);

% 额外约束：true变量周围至少有一个false
constraint forall(i in 1..H, j in 1..W)(
    grid[i, j] -> not(grid[max(1, i-1), j] /\ grid[min(i+1, H), j] /\ grid[i, max(1, j-1)] /\ grid[i, min(W, j+1)]
));

% 行和约束：每行true数量小于行长度
constraint forall(i in 1..H)(sum(row(grid, i)) < H);

% 列和约束：每列true数量小于列长度
constraint forall(j in 1..W)(sum(col(grid, j)) < W);

% 3×3全同约束：禁止3×3区域全为true或全为false
constraint forall(i in 1..H-2, j in 1..W-2)(
    not(all_equal(a in i..i+2, b in j..j+2)(grid[a, b]))
);

% 行对称破缺：前半行字典序小于等于对应后半行
constraint symmetry_breaking_constraint(
    forall(i in 1..(H div 2))(lex_lesseq(row(grid, i), row(grid, H+1-i)))
);

% 列对称破缺：前半列字典序小于等于对应后半列
constraint symmetry_breaking_constraint(
    forall(j in 1..(W div 2))(lex_lesseq(col(grid, j), col(grid, W+1-j)))
);

% 上界约束：交替列的情况
constraint totsum < H*(W div 2 + 1);

solve :: bool_search(grid, input_order, indomain_min, complete) minimize totsum;

优化建议 #

一、精简冗余约束 #

• 移除非必要约束：
  • 第二个约束（true变量周围至少有一个false）不属于问题原始要求，会排除部分合法最优解（比如某true变量四个邻居均为true，但满足所有false的相邻约束），直接增加求解负担，建议移除。
  • 3×3全同约束会生成大量子约束（32×32网格有900个这类约束），完全不属于核心需求，直接拖慢求解，建议移除。
• 简化行/列和约束：原sum(row(grid,i)) < H可简化为sum(row(grid,i)) ≤ W-1，但该约束已被核心约束隐含（一行全true无意义），若测试后对速度提升不大，可考虑移除。

二、对称性破缺优化 #

非正方形网格的对角线对称（主/反对角线）仅在H=W时成立，可改用以下更通用的对称破缺方式：

1. 180度旋转对称破缺

强制原网格字典序小于等于旋转180度后的网格，适用于所有尺寸的网格：

array[1..H,1..W] of var bool: rotated180 = array2d(1..H,1..W, 
    [grid[H+1-i, W+1-j] | i in 1..H, j in 1..W]
);
constraint symmetry_breaking_constraint(lex_lesseq(grid, rotated180));

2. 翻转对称破缺

破缺水平/垂直翻转的对称性，进一步减少搜索空间：

% 水平翻转对称破缺：每行字典序小于等于自身翻转
constraint symmetry_breaking_constraint(
    forall(i in 1..H) (lex_lesseq(row(grid,i), reverse(row(grid,i))))
);

% 垂直翻转对称破缺：每列字典序小于等于自身翻转
constraint symmetry_breaking_constraint(
    forall(j in 1..W) (lex_lesseq(col(grid,j), reverse(col(grid,j))))
);

三、求解器与搜索策略优化 #

• 更换搜索策略：当前input_order搜索效率极低，建议改用基于目标或变量重要性的策略：

  % 优先搜索目标变量，快速剪枝
  solve :: int_search([totsum], first_fail, indomain_min, complete) minimize totsum;
  
  % 或选择约束最多的变量优先搜索
  solve :: bool_search(grid, most_constrained, indomain_min, complete) minimize totsum;
  

• 调整求解器参数：OR-TOOLS支持并行搜索，可通过命令行开启：

  minizinc --solver ortools --solver-args "--num_search_workers=4" your_model.mzn
  

• 切换求解器：OR-TOOLS在布尔优化问题上表现不如专用CP求解器，可尝试Gecode、Chuffed（针对优化问题优化）等求解器。

四、利用问题结构特性 #

你的问题本质是网格支配集问题，可利用已知的最优解模式：

• 设置紧上界：网格最优支配集的密度约为1/4，对32×32网格可设置totsum ≤ 256（32*32/4），替换原来的宽松上界，帮助求解器快速剪枝。
• 2×2块约束：每个2×2块中最多放1个true（单个true可支配整个块），大幅减少搜索空间：

  constraint forall(i in 1..H step 2, j in 1..W step 2) (
      sum(grid[i..min(i+1,H), j..min(j+1,W)]) ≤ 1
  );
  

内容的提问来源于stack exchange，提问作者Kamugg