优化问题是一种常见的决策问题，它在我们的社会中很常见。它的应用可以从数独问题的解决涵盖到婚礼的座次安排。同样的技术可以用于航班与机组成员的安排，钢铁生产的调节，和钢铁从矿区到港口的调度问题。在生产中，人力资源与生产材料的合理决策可以使企业获得成千上万的利润提升。类似的问题也存在于我们的日常生活中，它们包括决定包裹的运输路径，调整学校课程时间，和传输能源到千家万户。尽管这些问题很基础，不过以一般本科教育的知识来解决这些问题都会十分困难。 这个课程是设计给已完成离散优化建模基础篇的同学。你将学习到更多关于如何使用先进的高级建模语言表述清楚具有挑战性的离散优化问题，并让约束求解器完成其余工作。本课程将重点介绍模型调试与改良，如何把一个复杂的约束定义封装到一个谓词里面，及如何着手各种复杂的项目调度和打包问题。当你掌握这种先进的技术，你将能够解决以前难以想象的问题。
2.5.3 值对称
Loading...
来自 The Chinese University of Hong Kong 的课程
离散优化建模高阶篇 Advanced Modeling for Discrete Optimization
3 个评分
从本节课中
对称与支配
在最后的单元中，我们将会探讨在离散优化问题中不同类型的对称。你将会学到如何用不同的方法和特殊的约束来打破这种对称性从而提升解决的效率。你也将会学到支配的概念，一种更广义上的对称，还有打破支配的技巧。你的学习目标有：1. 在问题的陈述中发现对称性; 2. 通过增加适当的打破对称性的约束来更改具有对称性的MiniZinc的模型; 3. 总结模型中存在的不同类型的对称; 4. 通过发现支配来提升模型。
与讲师见面
Prof. Jimmy Ho Man LeeProfessor
Department of Computer Science and Engineering
Prof. Peter James StuckeyProfessor
Computing and Information Systems
借助七星灯阵停雨后 诸葛亮还需要一个条件，方能发动火攻
就是吹向曹军的东风。
在赤壁，秋冬常刮 西北风，诸葛亮在从太平要素中寻得借东风之术
准备设置祭坛，摆设贡品，求风 祭坛共有三层，每层均成六边形状
在每层的顶点上，将放置不同的贡品
而贡品具有六种不同等级，两层之间同一位置的
贡品间需放置与两贡品等级差，相同数量的铜币
书中记载 祭坛因此放置的铜币数量，将决定求风之力
铜币越多，威力越强 为确保求得东风，诸葛亮需尽可能多的放置铜币
因此他取出神算法板
>> 诸葛亮为了要借东风 所以呢他要布置一个祭坛。
他要做的就是，要把 不同的贡品呢安排到这个祭坛不同的地方上面去摆放
我们看见这个祭坛呢，有三层，每一层呢都有一个六边形
而每一个六边形上面的每一个顶点呢，就是我们可以放贡品的地方了
这个呢就是我们这个祭坛的一个鸟瞰图了
我们先来看看我们不同的贡品 原来呢，我们的贡品是分这个等级的
我们可以看见，越贵重的贡品呢，它的等级呢就越高
除了贡品之外，诸葛亮还是需要在这个
祭坛上面要放一些铜钱的，在什么地方要放铜钱呢？要放的地方呢就是
在两个相邻的层同一个位置的顶点，放的
贡品中间我们就基于两个贡品呢它们的 等级来决定要放铜钱的数量的
我们看看下面的例子。
我们这里面有一个等级 1 的贡品 有一个等级
5 的贡品，我们要放的铜钱的数量呢就是这两个等级的它的
绝对差，所以呢 1 跟 5 它的绝对差呢就是
4 了，所以呢在这两个贡品中间呢，我们需要放 4 个铜钱
另外一个例子，第一个贡品呢它的等级是 6
，另外 一个是 4 ，所以呢它们等级的差呢就是 2 ，所以呢我们要放
2 个铜钱 如果两个相邻的贡品呢，它们是有同一个等级的话
所以我们就也可以不放任何的铜钱呢，因为它们等级差为
0 好了，我们决定了在每一个顶点要放什么的贡品之后
我们就可以利用它们的等级来 决定，我们在它们之间要放多少数量的铜钱
我们看看这个例子，我们总共呢可以放 27
个铜钱 但是这个求风之术的要求呢
就是我们的铜钱的数量是越多越好，那我们这个祭坛呢 才会越有效的。
这个呢就是我们求东风 这个问题的一个文字的描述。
我们呢这个祭坛呢一共有 m 层 我们在问题里面呢这个 m
为 3 ，而且呢这个 m 层里面呢，我们有 m 个 同心的正
n 边形，这个 n 呢在这个故事里面为 6
然后呢，我们有 m 个 n 边形，所以呢我们顶点的数目 就是
n*m 我们在这 n*m 的顶点上面呢，都要放不同的贡品
而且呢，这些不同的贡品呢我们可以把它们分为
m 组，而且呢每一组呢都有给定的等级
而且呢，我们也要求呢相邻两层两个相同位置的 顶点之间，要放置
k 个铜钱，这个 k 呢基本上就是这两个顶点所放的 贡品的它们的等级差。
我们这个 问题的目标呢就是要把铜钱的数量最大化
看看我们这个问题的模型 刚才已经提到过了，我们有
n 跟 m 就是分别了 m 就是层数 n
呢就是我们我们每一层有一个 n 边形 然后呢，我们就利用 n
跟 m 可以定义不同的范围，这个就是每一层 顶点的数量的范围，而且呢
n 也可以帮助我们定义，我们有多少个 不同的贡品的等级。
m 1 到 m 这个范围呢 就是代表我们 n 边形的数量就是我们的层数了
我们当然了也需要一个枚举类型的数据了 来把我们所有不同的贡品呢列出来
但是我们也需要小心，就是这个枚举类型呢
虽然它是一个集合，但是它是一个有序的集合，所以呢当我们
把这个贡品列出来的时候呢，我们要把这个贡品它们的等级的 值的要顺序。
然后呢我们就可以利用一个非常简单的表达式的 去定义一个我们叫
rank 的 整型数组来代表每一个贡品呢，它的等级是什么来的
然后呢，我们就有两个不同的变量
数组，第一个变量数组呢就是一个二维的数组，这个二维的数组呢就是代表
每一个多边形的 每一个顶点，我们应该呢放什么的贡品在哪里？
然后我们也需要知道呢 同一个位置的顶点在两个相邻的层
它们之间应该放多少数量的这个铜钱呢？
这个呢就是我们这个问题里面的数据文件呢 n
就是 6， m 为 3 ，然后呢我们也把我们所有的贡品呢都列出来
刚才已经讲过，我们应该把这个列出来的时候要把贡品呢，它们的等级呢
要顺序的，所以呢我们可以看见我们是 1、 2、 3、 4、 5、 6 这样子把它们列出来的
我们可以来看，我们模型里面的约束 第一个条件呢，很简单，当然就是要求呢我们在不同
顶点放的贡品呢它们都是互不相同的，我们当然就要利用到 我们这个
all different 的全局约束，而且呢也利用这个 array1d
把一个二维的变量数组 数组把它拉平变成一个一维的数组，然后就要求它们里面的所有的值呢都是互不相同
另外一个条件呢，就是要确定在 相邻两层每一对相同位置的顶点之间
它们要放的铜钱的数量，我们呢就 这个要放的铜钱的数量呢其实是决定于放在这两个不同的
顶点，它的贡品它们的等级，它们的差
然后呢就决定这个地方我们放的这个铜钱的数量
然后我们把所有的要放铜钱的地方，它的
数量都加起来，然后我们就要这个铜钱的总数量要最大化
当然呢，在这个问题里面呢我们都有 不同的对称问题的。
我们先看看第一个，我们发现呢
在不同的层，但是在同一个地方的顶点的话它们可以连为一个直线的
而且呢，我们也发觉呢我们放在这 3
个不同顶点上面的贡品，跟另外一条直线 上面放的这个贡品呢，是它们是可以互换的
换过之后呢，其实对我们要计算多少个铜钱呢，是
完全没有这个影响的，所以呢如果我们这个是一个解的话
我们把两个不同的直线上面要放的贡品都互换的话，我们之后
得到的还是应该是一个解来的，这个呢其实是一个变量的对称
另外一个对称呢是，我们发觉我们可以交换
我们多边形上面每一个顶点放的贡品
我们先看看这个例子，因为我们这个祭坛呢只有三层，我们先看第一层
如果我们只是放了这几个贡品，然后 第三层也是放了不同的贡品，我们发觉呢
如果我们把第一层跟第三层的贡品互相调换
这个也不会影响我们铜钱的总数量这个值的
所以如果这个是一个解的话，我们做了这个 调换之后呢，我们还是一个解来的
其实我们刚才就说把第一层这个多边形上面的贡品跟
第三层的多边形上面的贡品互相这个调换，其实呢 也可以看为呢把第一层到第三层
把它们倒转过来，去摆放这个贡品也可以的 这个呢也是一个变量对称
好啦，有了变量对称，我们当然知道了我们就可以利用我们 熟悉的
LexLeader 这个方案呢来帮助我们把这两个的 变量对称呢都移除了。
我们先看看 LexLeader 怎么可以帮助我们移除我们的第一个对称
我们第一个对称呢，就是说在每一条 线上面的贡品跟另外一条线上面的贡品呢
它们是可以互相地调换，所以呢 LexLeader
就会建议呢我们 把这个多边形上面的
相邻的两条线呢就加 添加一个字典序的一个要求
在我们的模型里面，我们只需要加入这一组的 约束呢，就可以了，因为我们
j 呢就是每一条线 在 j 这条线跟 j+1，就是相邻的一条
线呢，我们要求它满足了这个 lex_lesseq 这个全局约束。
但是如果我们再看清楚呢，我们有这个 全局约束要求两个数组要满足这个
lex_lesseq，但是我们 之前呢已经知道，在我们这个问题里面，每一个顶点
放的贡品呢都是互不相同的，所以我们知道呢
这个黄色这个贡品跟这个蓝色这个贡品呢，一定是 不同的，所以呢我们利用比较第一个
元素呢，我们已经可以知道它们是不是满足 这个 lex_lesseq
了，所以我们就可以把这个 约束呢简化成为下面这一条，我们直接就去比较它们第一个
元素就可以了，所以呢我们的约束就更为简单，而且呢我们也不需要 lex_lesseq
这个全局约束 另外一个对称呢，就是我们可以把
第一层跟第三层的这个多边形上面放的贡品
呢把它们互相调换，出来的结果呢还是另外一个解 我们当然也可以利用
LexLeader 来把这个对称呢移 除，我们在上面呢就要求，这个就是利用一个推导式把
第一层的这个多边形上面的所有的贡品呢都 收集起来，变成一个一维的数组，这个呢就是第三层的
这个多边形上面所有的贡品把它收集起来，变成一个
一维的数组，然后我们要求呢它是满足这个 lex_lesseq 这个排序的。
下面呢就是我们一个表示的方法啦 好啦，其实跟之前的原因
也是一样，我们是知道在这个祭坛上面，所有的贡品 都是应该互不相同的，所以呢这个那么复杂的利用
这个 lex 来比较的一个顺序呢，其实我们就只需要
比较我们两个数组的第一个元素呢 就可以了，而且呢我们也不需要利用这个
lex_ lesseq，就利用这个小于这个简单的比较就可以了
好啦，对我们的模型里面添加了这个 对称移除的约束之后，我们就可以要求
MiniZinc 给我们的模型去求解了，但是呢求解的过程不十分之顺利
过了 10 分钟之后，我们只找到一个 12 个铜钱的一个解
然后过了 20 分钟，也只有一个 23 个铜钱的解，所以呢
这个还没有把这个问题完全解决的 其实我们再看清楚了，发觉这个问题里面我们还有另外
一种的对称，我们叫它是值的对称，其实呢大家在之前已经
见过值对称了，但是呢我们从来没有把
给这个值对称呢，给它一个正规的一个 定义，我们下面就看一看。
我们叫一个 g 这个双射的函数，如果它满足下面这个条件呢，我们就叫它一个
值的对称了，就是说如果这个 X1 等于 V1
到了 Xn 等于 Vn 是一个解的话 然后我们把
g 呢应用到我们这个解当中的值当中，然后
得到另外一个赋值，这个赋值就是 X1 = g(V1)
到了 Xn 等于 g(Vn)，而且这个新的赋值呢，也
是一个解，而且呢相反来讲，如果这个是一个解 这个也是一个解的话，那我们就说这个
g 呢，这个双射的函数呢，就是一个值的对称了
其实我刚才也提到过，大家在之前，譬如说在我们这个投石
车这个问题里面，我们是需要把这个投石的区域，要把它划分起来的
我们发现呢划分类的名字其实是无关重要的，所以呢在这个问题里面，我们 也是有一个值的对称的。
另外一个例子呢就是我们在安排宴会 里面，每一个宾客他要坐哪一个桌子？我们发现桌子
的号码其实也不重要的，所以呢我们也有另外一个值的对称的例子
那在我们这个问题里面，哪里有值的对称呢？
我们再来看看我们不同的贡品它们的等级
这三种不同的贡品呢它们都是有同一个等级的，另外三种也是 另外一个等级。
其实我们也发现就是，每三种贡品呢它为一组 每一组里面的贡品呢它们都有相同的这个等级
好啦，如果我们拿到一个解
我们发现呢如果把，在这个解里面把这个放着三种不同的贡品的地方
互相这个调换，其实呢我们也没有影响我们在这个贡品的安排上面
这个铜钱的数目的，所以呢其实如果我们从一个，把一个解里面的
同一个等级的贡品它们互相地调换呢，我们也可以拿到
另外一个解，那所以我们这个问题里面呢就有这个值对称这个问题了
好啦，我们去 说明怎么把这个值对称这个问题呢去解决之前呢
我们要提到一点，就是呢，我们发现在这个 问题里面呢，我们有多于一种的对称，我们之前看见过一个
线可以互相地交换，我们发现那个多边形上面的贡品呢也可以互相交换
刚才就提到呢，相同等级的贡品呢它们也是可以互相交换，它们就是不同的 对称了。
当然呢我们也希望把所有的对称呢
都移除，所以呢我们就需要利用不同的移除对称的 约束呢来把它们移除了。
当我们这样子做的时候，我们要 比较小心，就是呢我们要求要保证呢我们不同的
对称移除的约束呢，它们要 保证它们的一致性，就是说它们需要是兼容的
就是说，我们需要呢加入了这些的约束 之后，每一个对称类当中，我们至少还有一个会
还有一个解呢会给保留下来 我们刚才提到的移除对称的技术，都是基于
确保呢我们的解都是基于这个字典序里面而言，是最小的解
所以呢我们就是，应该是希望加入了不同的约束之后
我们对于字典序而言，最小的解呢还是可以保留
下来的，所以譬如说如果我们刚才要移除我们第二个
对称的时候，把这个小于改成了大于 那我们就变成了要这个，移除这个
多边形的交换的时候，我们要求就是保留基于这个字典序而言，最大
它的一个解要把它保留下来，但是我们在做移除这个交换线这个对称的时候，
我们是要求呢，保留字典序最小的解，那它们就
有矛盾的，很可能呢会把一些我们应该留下来的解 呢，都可以把它们移除了，所以这个是不正确的
去把这个对称移除的一个方法。
所以呢，在这里呢我们要特别的小心，
好了，刚才提到这个值对称这个问题，我们可以怎么把它们移除呢？ 那当然了，之前我们看过了，我们可以利用这个
"value_precede_chain" 这个全局约束来移除这个值的对称。
我们在这里呢，就介绍一个新的方法，这个新的方法呢，是基于一个
一个观察的，这个观察呢就是说
如果我们面对的是一个排列的问题，在一个视角
里面如果我们有一个值的对称的话，我们发现呢，
在另外一个视角呢，这个值的对称呢，就会变成那个变量的对称了。
在我们这个贡品的放置的问题里面，首先我们是
一个排列的问题，我们呢刚才提到一个视角那就是每一个
位置我们应该放一个什么的贡品，其实呢我们在问题里面也有 1 到 n*m 就是在这个问题里面
18 个不同的贡品，其实呢 我们可以去添加一个新的视角，这个新的视角呢就是说
每一种贡品我们应该把它放到什么的位置呢？所以首先呢，我们要定义一个范围， 1
到 n*m 这是呢这个贡品的数目，然后定义
一个变量的数组，这个数组就是对于每一个贡品呢， 我们应该把它放到什么的位置，position，
好了，我们有我们原来的视角，贡品，tribute，也有新的 视角，
position 就是位置，当然呢我们要求两个视角它们呢都是一致的，
所以呢我们需要把 tribute 这个视角跟这个position这个视角呢把它们连通起来，
当然我们就可以利用 inverse 这个全局约束。
好了，有了这个之后呢，我们就发现在我们新的视角里面，
假如我们有两个不同的贡品 i 跟 j ，如果呢它们是
相同等级的话，我们发现呢，如果我们可以有一个解，我们可以把这个 position[i]
和 position[j] 这两个变量呢互相交换，我们还是有一个解的。
我们来看看 下面这个例子，譬如说我们有一个解，其中呢， 我们有三个的赋值，这三个赋值呢就是说，
绿色这个宝石是放在第 5 这个位置，红色这个宝石是放在
这个 11 这个位置，蓝色就放在第 8 个
位置，我们也明白了宝石就是我们最高的等级来的， 而且呢它们也是相同的等级，所以呢我们知道
我们把绿色的要放的位置跟红色要放的位置 互相交换呢，我们还是可以保持
这个赋值呢是一个解来的，因为这样子的调换是不会影响
我们这个整个安排里面我们铜钱的数目的，其实，
我们把上面三个赋值三个变量里面的下标 绿色的宝石，红色的宝石，跟蓝色的宝石
我们其实可以互相的调换，我们 得到新的一个赋值呢，还是一个解来的。
好了，当然了，我们 发现了在原来的视角当中是个 值的对称，
到了我们新的一个视角当中呢，变成个变量的对称， 变量的对称当然我们知道是怎么去移除这一类的对称的，
我们就是可以利用这个 LexLeader 这个方案的，但是呢我们现在这个
对称呢，里面呢是比较特别，不是一个矩形，是一个
也可以说是一个一维的矩形，所以呢我们就可以利用这个LexLeader 这个方案，我们要求呢，
每一个贡品的等级，我们叫 i
那这个范围是怎么来的，原来这个范围呢，就是代表了 是
i 这个等级的贡品它们的值，
那你可以说，我们不是用这个枚举类型来代表我们的贡品的吗？
那么为什么又会变成那个数字呢？其实我们大家也应该明白到呢
这个我们利用这个枚举类型呢，就是希望利用它的名字来帮助我们去理解 我们的模型，但是在
MiniZinc 里面内部的话，其实我们这个 枚举类型每一个值呢都是一个数字来的，所以呢
我们也可以利用数字呢，来表示我们这个枚举类型里面的
的每一个元素，然后我们就要求呢相同一个
等级的变量，它们都需要呢有一个
排序，从小到大，这样子呢我们就可以把这个 变量对称呢，去把它移除了。
加入了这个对称的移除之后，我们呢就可以在2分
26秒之内呢，求得一个解，而且呢这个解呢， 也是一个最优的解，我们呢可以在这祭坛上面呢
放这个42个铜钱，比我们之前看过的好很多很多。
刚才我们也提到，我们在原来的视角当中呢， 其实也可以利用我们之前见过的
"value_precede_chain"这个全局约束呢把这个值的对称
去移除，详细的情况呢我就不解释了，你们可以慢慢去看，我们就要求呢，
把一个每一个 等级里面的贡品，我们要求呢把这个贡品呢都排了
一个序，然后利用这个 "value_precede_chain" 呢，我们就可以把我们这个变量的数组呢，
里面的所有的值对称呢，都移除了。
当然呢，我们利用全局约束，就可以进一步把我们求解的效率
提高了，利用呢我们新的模型呢，在 15 秒之内呢就我们就可以把我们最优的解求了出来。
我们来一个小结：值对称在离散优化
问题里面经常的出现，当我们看见问题里面
如果一个解当中的值可以互相的调换，然后我们可以得到 另外一个解的话，我们就说我们问题里面呢有这个值的对称了。
之前当然我们看过利用这个 "value_precede_chain"
这个全局约束呢可以帮助我们把这个 值的对称去移除，但是呢在一个排列的问题
当中呢，我们发现一个视角当中的值对称呢 到了它的逆向视角当中呢，就变成了一个
变量对称，当然我们也可以利用这个变量对称的移除 的方法，譬如说
LexLeader 来帮助把这个变量对称移除，
也就是说把我们原来视角当中的值对称呢也移除了。
如果我们一个问题里面有多于一个的对称我们都需要把它移除的话，
我们要非常小心，我们需要保证呢我们不同的约束呢
是兼容的，就是说要求它们都放到我们的模型里面之后，我们在
模型里面，每一个对称类至少还有一个解呢是给保留下来的，这个
是非常重要。
[空白_录音]
