多年以前曾经有过一段与统一建模语言与通用求解器相关的意识流 (数据库中的搜索, 组合优化问题的搜索, 统一建模语言与通用求解器).
最近机缘巧合, 又遇到了这个话题, 于是又做了进一步的思考.
总的来说, 如果能设计一个能与针对特定问题的专用算法相媲美的通用求解器, 无论是精确还是近似, 其实际应用价值不亚于证明 P = NP.
可惜, 天上不会掉馅饼, 一个高价值的问题, 难度往往也不会低.

我们需要什么样的通用求解器?

如果说好奇心驱使人类进行科学探索, 那么, 懒, 则是人类发展技术的动力源泉.
“复用” 是软件工程的核心思想之一, 说白了就是懒, 不想做别人甚至自己早就做过的工作.
在求解组合优化问题时, 我们当然也希望充分利用现有的研究成果.
算法设计中有很多平衡, 在这里, 我们关注的是算法的开发难度和结果优度之间的平衡, 以及开发效率和运行效率之间的平衡.

通用求解器的美好愿景是, 我们只用向计算机描述我们的问题, 它便能自动求出最优解.

然而, 其最大的问题就是如何向计算机描述我们的需求.
计算机往往只能接受形式化的语言, 即程序设计语言.
相比于命令式的编程语言, 声明式的编程语言更适合用于数学建模.
它们仅用于陈述事实, 所有声明是平行的, 需要被同时满足, 而不像命令式编程语言描述事件和操作的先后顺序.
不幸的是, 用数学语言形式化地描述问题对很多人来说都是一件十分困难的事情.
毕竟, 很多人用自然语言都无法清晰地描述需求, 定义问题.
简洁的建模语言入门容易, 但表达能力往往较弱, 十分考验使用者的经验与技巧.
复杂的建模语言表达能力强, 但学习成本也十分高昂.
如果既简洁又强大的建模语言真的存在, 大概率又会难以绕开自然语言的问题, 即二义性.

另一方面, 通用算法想要识别问题结构, 然后进行针对性处理是非常困难的.
然而, 且不说不同问题, 即使是同一个问题, 面对不同特性的测试用例, 不同算法的性能也有天壤之别.
比如, 拿最短简单路径这种教科书级别的 P 问题来举例:
若所有边权重相同, 则可以直接用广度优先搜索进行求解;
若在平面图上, 可以用欧氏距离作为启发函数使用 A* 算法高效求解;
若在网格上, 可以有更多基于地标和可达范围的加速策略…
如果能给计算机一些提示, 使其能够利用问题结构的信息, 将对求解效率产生十分积极的影响.

几个通用求解器的技术路线

数学规划

以 Gurobi 和 CPLEX 为代表的数学规划求解器, 主要基于线性规划求得线性松弛, 再基于线性松弛进行树搜索.
以个人经验来看, 虽然很多求解器还支持特殊形式的二次规划 (QP), 但其表达能力和求解效果往往不如混合整数规划 (MIP), 故此处仅讨论后者.

数学规划可以适应离散优化与连续优化相结合的场景, 表达能力足以支撑生产生活中绝大多数组合优化问题的建模.
但是, 正如 Harold Hotelling 的 “名言”, “But we all know the world is nonlinear”, 大量组合优化问题无法直接用 MIP 等建模语言进行描述.
最简单的情形便是 “逻辑或” 的关系, MIP 要求所有约束同时满足, 即 “逻辑与” 的关系, 所有约束对应的超平面将解空间切成一个单纯形 (凸多胞形) 构成可行解空间, “逻辑或” 会使可行解空间产生凹陷.
我们需要添加布尔类型的辅助变量进行升维, 使用 Big-M 的技巧, 将线性不可分的解空间转换为线性可分的, 将逻辑约束转述为代数约束.
进行上述处理后, 问题结构往往变得高度非线性, 不同的转换方式会不同程度地丢失问题的结构信息, 导致求解效果不够理想, 以至于最短路径或最小生成树之类的 P 问题求解速度往往也难以接受.

SAT/MaxSAT/SMT

以 MiniSAT 及其衍生出的众多开源求解器为代表的通用求解器, 主要基于问题之间普遍存在可以相互归约/转换的关系, 通过一定的编码技巧将各类约束统一表达为布尔表达式.

与数学规划方法基于代数理论以连续优化为切入点不同, SAT/MaxSAT/SMT 方法的重心在逻辑推理, 直接面向离散优化.
由于 NP 完全问题之间普遍存在的可归约性, SAT 问题作为第一个 NP 完全问题, 其求解器理论上可以求解所有 NP 完全问题.
然而, NP 完全问题只是所有组合优化问题中一个很小的子集, 即使扩展到了 MaxSAT, 表达能力也十分有限而充满技巧性.
例如, 在数学规划中十分基础的 $a + b \le c$ 的约束, 要编码成 SAT 算例甚至类似于设计一个包含加法器和比较器的电路.
当然, 更进一步发展到 Satisfiability Modulo Theories (SMT) 之后, 表达能力产生了质的飞跃, 但从其目前的受欢迎程度来看 (我并没有使用过 SMT), 求解效率似乎也随之发生了质的跌落…

约束编程

以 MiniZinc 为代表的约束编程求解器, 其实现主要基于树搜索算法.

约束编程中各式各样的约束类型十分丰富, 表达能力很强, 乍一看好像和 SMT 很接近, 但是由于研究不多, 在此不做过多评价.
个人感觉约束编程中对很多常见的约束类型进行了封装或者模板化, 在简化调用代码的同时可以完整地呈现问题结构, 而不是以被使用者打散的状态出现.
做个不恰当的类比, 我们在描述一块砖的受到的重力时, 正常人都是用整块砖的质量乘以地表重力加速度, 而不是考虑砖里面每个原子的受到的万有引力以及原子间的相互作用.
比如在排序问题中, 我们需要给每个元素安排一个序号, 所有序号互不相同, 学过排序算法的都知道, 我们每次只交换两个元素就不会违反这个互不相同 (all-different) 约束.
但是如果使用者给出了 $n^{2}$ 条约束, 告诉求解器任意两个元素的序号不相等, 那么求解器就需要经过一系列约束推理 (传播) 才能发现, 修改了 A 的序号之后, 必须把另一个元素的序号改成 A 原来的序号才行.
如果建模语言直接支持一类 all-different 约束, 则可以保留这种结构信息.
当然, 与其丰富的特性相对应地, 其学习成本也不见得比学习一门编程语言以及启发式算法的基本思想低多少.
有意思的是, 物理学家们努力在寻找大统一理论来解释所有相互作用, 虽然似乎目前进展不太顺利.

局部搜索

以 LocalSolver 为代表的基于局部搜索的通用求解器.

局部搜索算法与人的求解过程十分相似, 都是从初始解出发, 不断对当前解进行修改, 只对搜索路径或上下文信息进行有限的记录.
对于约束较少的优化问题, 局部搜索具有极高的适应性.
例如, 以最小化问题为例, 局部搜索关注上界, 是真实可行的解的目标函数值, 因此更符合实际需求.
而树搜索为了确保最优性, 关注的往往是下界, 是理论上最优解的目标函数值, 其实努力方向稍微有点走偏了.
然而, 局部搜索算法的设计是高度依赖问题结构的, 算法性能的关键一方面是邻域动作, 即每次如何修改当前解, 另一方面是邻域范围, 即每次评估哪些邻域动作.
如果只是对解向量进行任意的修改, 可能会浪费大量时间在无效的动作上.
以前面的 all-different 约束为例, 改变一个元素的序号后, 下一步可以把 n 个元素的序号更改为 1 到 n 中的任意一个, 共有 $n^{2}$ 个动作, 但其实只有一个能得到可行解.
因此, 个人对于基于局部搜索的 “傻瓜式” “即开即用” 的通用求解器持相对悲观的态度, 不进行定制化将难以发挥局部搜索算法的强大威力.

算法库

以 COIN-OR 和 dlib 为代表的算法库.
主要基于问题之间普遍存在可以分解/组合的关系, 由算法设计者对各种子算法进行组合形成完整问题的求解算法.

使用算法库与基于 SAT/MaxSAT/SMT 构建通用求解器在思路上十分相似, 但从另一个角度看又是两个极端.
算法库几乎将算法设计的压力全部扔给了使用者, 甚至可以说这条技术路线完全没有超出软件工程的范畴.
而已知算法庞大的数量将极大地限制其可用性, 屠龙勇士最终往往会成为新的恶龙.
我已经有过类似的经历, 需要使用一个经典算法时, 发现很多第三方库中都有, 但是为了用一个简单的算法, 需要把整个庞大的工程集成到我的代码中, 感觉十分繁琐.
同时, 这些算法为了支持多种多样的应用场景往往会有很复杂的参数控制算法的行为, 即使我只需要最基础的功能, 我也得花大量时间仔细研究使用说明.
于是我决定自己重新实现一下, 并在以后的使用中日积月累, 功能越来越强大.
直到有一天, 我向学弟学妹们推销我那瑞士军刀般的算法库时, 大家都望而却步, 我才发现, 我的 “杰作” 已经成为了自己曾经不屑一顾的东西…

当然我们也不必过于悲观, 在特定领域中算法库应该还是有其用武之地的.
事实上, 基于数学规划的方法为我们提供了一些思路, 比如行生成 (惰性约束) 和列生成 (分支定价) 框架就是典型案例, 其子问题往往是个很简单的 P 问题, 可以由算法库提供支撑.
更通用地, 我们可以用函数式的编程范式对算法进行组合, 例如, 上层问题每找到一个可行解 (大格局), 就调用回调函数进行下层问题的求解 (完整解), 然后将完整解的可行性和优度反馈给上层, 上层根据反馈结果开展进一步搜索.

算法框架

以 SCIP 和 EasyLocal 为代表的算法框架.
说白了还是软件工程, 提取算法中公共的重复的部分, 将需要定制化的部分开放出来 (当然也可以提供默认的实现以提高易用性), 可以用于任何方法学.

对现有的框架了解不多, 自己设想的框架还在规划中, 在此不展开讨论.

能够指导求解的统一建模语言

前面反复提到 “问题结构” 这个词, 它到底是个什么东西? 到底能为求解带来多大的好处?
其实我自己也没想清楚, 只有两个模糊的思路.
一方面, 如果我们按某种策略对解空间进行探索, 那么有些约束将自然满足, 根本不用考虑, 不用专门添加约束加以限制.
比如对于 SAT 问题, 我们默认同一个变元在所有子句中的取值是完全一致的, 就是一种很自然的约束, 在满足这个约束的基础上去寻找满足所有子句的变元取值.
事实上, 我们还可以进行完全不同的建模, 比如要求所有子句必须都满足, 然后最大化同一变元在不同子句中的一致性, 其求解效果可能有天壤之别, 但求解器很难知道还有另一个等价的可以高效求解的模型.
另一方面, 如果我们按某种策略对解空间进行探索, 一旦探索过某些特定的子结构, 则可以排除一部分解空间包含更优解的可能性.
这个思路在 P 问题的求解中应用尤为广泛, 在 NP 问题中也较为常见, 比如动态规划的最优子结构, 树搜索的剪枝策略等等.

我是研究元启发式算法的, 下面我还是以我的老本行为切入点, 探讨一下在建模层面为求解算法提供指导的可能性.
前面提到, 影响局部搜索算法求解效果最关键的两个因素是邻域动作和邻域范围, 除此之外, 如何高效地增量评估邻居解的目标函数值, 以及如何近似评估目标函数值, 都是局部搜索中的重要问题.
指导求解的统一建模语言, 至少可以从这几个方面入手.

邻域动作

“启发式” 的含义即借鉴人与自然的经验.
局部搜索其实十分自然, 就像人在解决问题一样, 先做个差不多的方案, 然后左调调右调调, 看看能不能改出一个更好的方案.
因此, 定义邻域动作其实并不比数学规划或约束编程复杂.
而合理的邻域动作定义, 可以充分利用问题结构, 省略部分十分自然的约束.
比如集合覆盖, 如果邻域动作是交换两个集合的选中状态, 则无需添加选中集合数量约束.
用形式化的语言描述, 令所有子集的集合为 $S$, 选中的子集集合为 $X$, 交换邻域动作可以定义为 $M = { X \leftarrow X \cup { p } \setminus { q } | p \in S \setminus X, q \in X }$.

邻域范围

定义邻域范围其实也只涉及简单的集合定义, 甚至没有超出高中数学的范畴.
合理的邻域范围定义, 可以充分利用问题结构, 避免评估毫无希望的邻域动作, 或者适当缩小邻域对单位评估改进量 (评估的邻域解数量 / 最优邻域动作目标函数值改进量) 进行平衡.
比如作业车间调度, 相比于任意调整同机器上两个工序的先后顺序, 高效的邻域范围往往会针对关键路径上的工序, 因为其他工序的顺序调整无法直接缩短完工时间.

再次以集合覆盖为例, 每个交换动作中新增子集时, 相比于从所有未选中集合中挑选一个, 高效的邻域范围可以是随机选中一个未覆盖元素, 尝试添加一个能够覆盖该元素的集合.
用形式化的语言描述, 令所有子集的集合为 $S$, 选中的子集集合为 $X$, 子集 $s$ 可覆盖的元素集合为 $C_{s}$, 可覆盖元素 $e$ 的子集集合为 $B_{e}$, 未覆盖元素集合 $U(X) = \bigcup_{s \in S} C_{s} \setminus \bigcup_{s \in X} C_{s}$.
精简的交换邻域可以定义为 $N = { X \leftarrow X \cup { p } \setminus { q } | \exists e \in U(X), \forall p \in B_{e}, \forall q \in X }$.
注意, 这里的符号使用可能不太严谨, 我们用存在量词 $\exists$ 表示从集合中随机选取一个元素, 还应进一步规范化.

增量评估

通用的增量评估虽然可行, 但其效率往往难以达到极致.
很多时候我们需要在更新代价和查询代价之间进行平衡, 往往需要一个中间数据结构实现辅助计算.
我们可以定义辅助查找表, 定义每轮迭代时目标函数如何通过这个查找表进行计算, 然后执行完邻域动作后查找表中的相关数据如何更新, 来提高评估效率.

近似评估

对于相对复杂的问题, 往往增量评估的代价都十分巨大, 此时我们需要使用近似评估策略, 筛选出若干较有潜力的解, 然后对其进行精确评估选出真正的最优动作.
近似评估其实于邻域范围有些许重叠, 邻域范围相当于可以在 O(1) 时间内完成的近似评估, 直接筛掉没有改进潜力的动作.
当然, 近似评估除了由人根据经验定义, 也完全有可能实现通用化和智能化, 即使用机器学习的技术, 进行函数逼近, 自动学习出一个开销很小的函数来模拟真实的目标函数.

总结

通用求解器是一个美好的愿景, 基于局部搜索的通用求解器更是十分有吸引力的方向.
而局部搜索的优势在于其对问题结构的把握, 丧失了问题结构的指引, 局部搜索的效果必然大打折扣.
因此, 个人认为, 我们在统一建模语言的基础上, 适当加入算法设计的提示信息, 对算法进行合理引导, 应该是比较有前景的技术路线.