一、变量对称性的例子：BIBD 问题

1. BIBD 问题的描述

• 问题描述：给出 $n, m, p, q, r$ 五个数。请你找到一个 $n \times m$ 大的 0-1 矩阵，使得：

  • 每一行内，数的和都为 $p$。
  • 每一列内，数的和都为 $q$。
  • 任意挑选两个不同的行，它们作逐位相乘后得到的新行内，数的和为 $r$。

• 问题可以被这样描述：

  range Rows = 1..n
  range Cols = 1..m
  
  var{int} m[Rows, Cols] in 0..1;
  
  solve {
  	forall (i in Rows)
  		sum(j in Cols) m[i, j] = p
  	forall (j in Cols)
  		sum(i in Rows) m[i, j] = q
  	forall (i1 in Rows, i2 in Rows: i2 > i1)
  		sum(j in Cols) (m[i1, j] & m[i2, j]) = r
  
  }
  

• 下面是一些例子。

  

  

• 这是一个组合设计 (combinatorial design) 问题。

2. BIBD 问题中的对称性及其优化

• 让我们考虑所有的行。

  • 请留意，问题中所有的约束都是关于各行自身或者任意两行间的。

  • 我们发现一个重要事实：交换两个行，可行解还是可行解；不可行解还是不可行解。

  • 因而我们可以将交换两个行作为一个等价关系。我们发现每个等价类中的解都能够通过交换行使得达到唯一的、字典序递增的状态。

  • 如果想要就此进行约束，我们可以添加这样一个约束：要求各列是字典序递增的。

    

• 对所有的列也是一样的。

• 我们就可以相应添加约束：

  forall (i in 1..(n-1))
  	lexleq(m[i, j] for j in Cols, m[i+1, j] for j in Cols);
  forall (j in 1..(m-1))
  	lexleq(m[i, j] for i in Rows, m[i, j+1] for i in Rows);
  

二、值对称性的例子：Scene Allocating

1. Scene Allocating 问题描述

• 要分配多个场次拍摄的日期。每个场次都定好了一批演员，场次之间的演员集合可能有重叠。演员是按日而非按场结算的，所以需要尽可能让同一演员的场次都排在同一天以节省工资；但是一天能安排的场次有一个上限，每个演员请一天的费用也不一样。

• 代码描述如下：

  enum Scenes = ...;
  enum Actors = ...;
  int fee[Actor] = ...;
  bool appearsIn[Actor, Scene] = ...;
  
  range Days = 1..5;
  int mostShotsInSingleDay = 5;
  var{int} allocatedAt[Scene] in Days;
  
  minimize
  	sum(d in Days) sum(a in Actor)
  		fee[a] * or(appearsIn[a, s] and allocatedAt[s] = d) for s in Scene));
  subject to
  	for (d in Days)
  		(sum(s in Scenes) (allocatedAt[s] = d)) <= mostShotsInSingleDay;
  
  

2. 对称性描述

• 我们留意到，对于这个问题而言，所有结果的日期取值怎么调换都是无所谓的（可行性不变、目标函数的值不变）。也就是结果中的日期无论如何打乱，只要保持与场次的对应关系一致，这些解都是等价的。
• 我们在搜索过程中，可以这样来消除对称性：

  • 第一个场次 $s_1$ 对应的日子为 $d_1$，由于目前来说现在所有日期都没有被取用、都是等价的，我们完全可以规定这个日子必须是第一天即 $d_1=1$，这之后就说我们目前已取用的日子就是第一天。

  • 第二个场次 $s_2$ 对应的日子 $d_2$，只可能有两种选择：

    • 它也是第一天，即 $d_2 = 1$。
    • 它不是第一天。这种时候由于所有还没有被取用的日子都是等价的，我们完全可以规定这下一个「新取用」的日子是第二天，即 $d_2 = 2$。

  • 因而方法论就是记录下目前已经取用到哪一天。假设当前有取用了 $l$ 个日期，那么下一个选择就可以取 $1, 2, \cdots, l$ 以及 $l+1$（表示一个新的日子）。数学地说就是：

    $$ D(d_k) = \left[1, \max_{i=1}^{k-1} d_i \right]\cap \Z $$

  • 对应地也就是新增这么一段约束：

    # 假设 range Scenes = 1..n;
    # 大概是的 可能
    allocatedAt[1] = 1;
    forall (s in Scenes: s>1)
    	allocatedAt[s] <= (max(k in 1..s-1) allocatedAt[k]) + 1