我们可以增加一些约束，虽然它们是冗余的，但是能加速搜索的过程。

一、魔法序列问题的快速求优

比如还是魔法序列问题。
```
int n = 5;
range D = 0..(n-1);
var int s[D] in D;
solve {
	forall (k in D) {
		s[k] = sum((s[i]=k) for i in D)
	}
}
```
- 首先，我们能发现，序列自身逐项求和一定等于序列的长度，因为各个 s[k] 说的是有几个数值出现在序列中。
  - 因而我们可以加入一句 sum(k in D) (s[k]) = n 的约束。
- 其次，当我们考虑要为某位置填入 s[k] = p 的时候，它说明 k 这个数值出现了 p 次。这里面每个 k 又表示某个数值出现 k 次，这就要求序列至少有 k * p 长度。
  - 因而又可以加入一句 forall (k in D) (k * s[k]) <= n。
- 我们还留意到，如果想要对这个序列求和，除了直接作逐项求和 sum(k in D) (s[k]) 之外，还有这么一种方案：因为各处的 s[k] = p 说明 k 这个数值在序列中出现了 p 次。因而我们可以分组地进行求和，即 sum(k in D) (s[k] * k)，先在 $k=0$ 时得到 0 出现的次数×值，再 $k=1$ 时得到 1 出现的次数×值，以此类推。
  - 因而 sum(k in D) (s[k]) = (sum (k in D) (s[k] * k)) 。
  - 也就是说 (sum (k in D) (s[k] * k)) = n。

二、Market Split Problems

问题描述
- 你现在有 $N_C$ 个消费市场，每个市场 $c$ 有 $d[c]$ 个产品需求。你有 $N_V$ 个方案。每个方案 $v$ 都会给各个市场配给一些产品，具体而言方案 $v$ 对市场 $c$ 会配给 $w[v, c]$ 个产品。请你选择一部分方案，以达到刚好满足各个消费市场的需求。
```
range C = 1..NC;
int demand[C];
range V = 1..NV;
int weight[V, C] = ...;

var{int} x[V] in 0..1;

solve {
	forall (c in C)
		sum(v in V) weight[v, c] * x[v] = demand[c];
}
```
优化方案：留意到这 $C$ 个约束并非是互相悉知的。我们可以使用「代理约束 (surrogate constraint)」的方案将这些约束联系在一起。
- 每个原约束都是一个等式，将他们各自乘以每个公式而言的一个系数 $\alpha[c]$ 后再相加，当然结果仍然是一个成立的、冗余的等式，如下：
```
sum (v in V) (sum(c in C) alpha[c] * weight[c, v]) * x[v] = sum(c in C) alpha[c] * demand[c]
```
- 实际 $\alpha[c]$ 的选取（摘自 GPT）
  - 常见的方法是各个系数都相等，比如全 $\alpha[c] \equiv 1$。
  - 可对更加关键的约束分配更大的 $\alpha[c]$。
  - 有的可能使用指数序列比如 $\alpha[c] = 2^c$。

三、Car Sequencing

汽车装配工作流问题描述
- 现在有一条不断缓慢移动中的生产线，有几个小队（这里是 5 个，每行表示一个小队）会在上面工作。
- 你有一系列要装配的汽车，每辆汽车要完成的装配任务可能都不一样。下面给出的就是一个图示，每列表示一种类型的汽车，下方的数字表示这种类型汽车的数目。各行表示每辆车需要哪些生产小队进行工作。
- 你现在要找到一个顺序，将这些车以你给出的顺序放到生产线上。主要的问题是，每个工作小队都不能连轴转，有各自的要求，比如：
```
第 1 小队：每个连续 2 长的时间窗口最多有 1 份工作
第 2 小队：每个连续 3 长的时间窗口最多有 2 份工作
第 3 小队：每个连续 3 长的时间窗口最多有 1 份工作
第 4 小队：每个连续 5 长的时间窗口最多有 2 份工作
第 5 小队：每个连续 5 长的时间窗口最多有 1 份工作
```
- 下面是一个可行解的例子。
- 下面是一个题目例子。

问题建模

# 所有的需要分配的时间点的标识符
range Slots = 1..S;
# 所有的汽车类别的标识符
range Configs = ...;
# 所有汽车类别要完成的数目
int demant[Configs] = ...;
int numCars = sum(c in Configs) demand[c] = ...;
# 所有的生产队的标识符
range Teamst = ...;
# 各个生产队在连续 ub 时间内的工作数目不超过 lb 份
int lb[Teams] = ...;
int ub[Teams] = ...;
# 每个汽车类别需要哪些生产队完成任务
bool requires[Config, Teams] = ....;

# 各个时间点分配的任务
var{int} seq[Slots] in Configs;
# 松弛变量，表示在各个时间点需要完成任务的生产队
var{bool} setup[Slots, Teams] in 0..1;

solve {

	# 所有汽车类别都应该放到生产线上
	forall (c in Configs)
		sum (s in Slots) (seq[s] = c) = demand[c];
	
	# setup 与 requires 的一致性
	forall (s in Slot, t in Teams)
		setup[s, t] = requires[line[s], t];
	
	# 每个小组的工作时间的要求
	forall (t in Teams)
		forall (s in 1..S-ub[t]+1)
			sum(j in s..s+ub[t]-1) setup[s, t] <= lb[t];

}

可以看到约束是像这样扩散的。
还有一种情况是……