Overview

优化问题是一种常见的决策问题，它在我们的社会中很常见。它的应用可以从数独问题的解决涵盖到婚礼的座次安排。同样的技术可以用于航班与机组成员的安排，钢铁生产的调节，和钢铁从矿区到港口的调度问题。在生产中，人力资源与生产材料的合理决策可以使企业获得成千上万的利润提升。类似的问题也存在于我们的日常生活中，它们包括决定包裹的运输路径，调整学校课程时间，和传输能源到千家万户。尽管这些问题很基础，不过以一般本科教育的知识来解决这些问题都会十分困难。这个课程是设计给已完成离散优化建模基础篇的同学。你将学习到更多关于如何使用先进的高级建模语言表述清楚具有挑战性的离散优化问题，并让约束求解器完成其余工作。本课程将重点介绍模型调试与改良，如何把一个复杂的约束定义封装到一个谓词里面，及如何着手各种复杂的项目调度和打包问题。当你掌握这种先进的技术，你将能够解决以前难以想象的问题。

Syllabus

调试与改良模型

跟计算机程序一样，模型也会有错误。在这一单元中，你将会看到许多不同错误的症状（如不能满足，太多解，太少解），而且学到不同的方法来发现你的模型的问题在哪里，你可以如何去修复它们。有了这些技能，你就可以开发和调试复杂的模型。这个单元的学习目标是：1.改正不正确的Minizinc模型; 2. 运用调试技巧来查明模型里面的错误; 3. 解释在关系语义下的一些为定义的表达式; 4. 修改一个正确的MiniZinc模型从而让它变得更有效率。

谓词

在这个模块中你将会学习到如何把一个复杂的约束定义封装到一个谓词里面，从而可以重复使用它。这可以让你建立越来越复杂的模型的同时，通过模块化的方式提升它的可读性。你将会第一次碰到多目标函数的问题，和学习如何压缩他们到一个目标函数里。除此以外，你还会学到如何对于安排宴会座次问题进行建模，这会在日常生活的许多场景中帮到你。你的学习目标有：1. 建立一个模型利用谓词和局部变量来让重要的约束抽象化; 2. 对于在MiniZinc模型中的不同的表达式进行分类。

调度问题

学习如何着手各种复杂的项目调度问题，从只有简单的次序要求的问题到有单一资源甚至累积资源的问题。你将会在这些应用中看到如何对于一些复杂的约束进行建模。这个单元的学习目标有: 1. 建立复杂的调度问题的模型; 2. 发现调度问题的子结构，如问题中分离调度和累积调度。

Packing 打包问题

在这个单元中，你可以学习到打包问题的一些重要应用，从正方形打包到直边形打包（考虑或不考虑旋转）。同样地，你将会看到在这些应用中如何对一些复杂的约束进行建模。你的学习目标有：1. 建立一个复杂的打包模型; 2. 通过全局约束（如diffn和geost）来描述打包问题。

对称与支配

在最后的单元中，我们将会探讨在离散优化问题中不同类型的对称。你将会学到如何用不同的方法和特殊的约束来打破这种对称性从而提升解决的效率。你也将会学到支配的概念，一种更广义上的对称，还有打破支配的技巧。你的学习目标有：1. 在问题的陈述中发现对称性; 2. 通过增加适当的打破对称性的约束来更改具有对称性的MiniZinc的模型; 3. 总结模型中存在的不同类型的对称; 4. 通过发现支配来提升模型。