最近遇到了一个小问题, 大致是已知一块玻璃上有些瑕疵, 如何切割出一块给定大小的矩形区域, 让它的位置尽量靠近左下角, 但是不与任何瑕疵重合.

虽然原始问题要求的是不与任何瑕疵重合, 但是对于一个给定的格局, 比如已知一些瑕疵会同时被覆盖, 有些瑕疵显然是不需要考虑的, 我们称其为 “被支配” 的瑕疵.
所以其实我们只需要避开没有 “被支配” 的瑕疵, 如下图中红色的点, 而绿色的点显然是不需要考虑的.

矩形装配

这个问题给我的第一反应是它和多目标优化的一种实现方式很像, 即帕累托最优性 (Pareto Optimality).
对于在帕累托前沿 (Pareto Frontier) 上的点, 找不到这样一个点, 在各个维度 (目标) 上都比他们数值更大 (目标函数值更优).
反之, 通俗地说, 就是存在一个点在各个维度上都能碾压某个不在 Pareto Frontier 上的点.

在搜索引擎里搜了下, 想找找有没有高效的求解方案, 找到了下面几个网页:
https://en.wikipedia.org/wiki/Pareto_efficiency#Computation
https://en.wikipedia.org/wiki/Multi-objective_optimization
https://en.wikipedia.org/wiki/Skyline_operator

其中令人惊讶的是, 这个问题居然跟数据库有关, 甚至 SQL 里面还有个专门的算子用来实现这个功能!

突然想起前段时间一位在国内某 500 强企业数据库部门的师叔来实验室交流时, 对通用求解器的讨论.
数据库和组合优化都是在一个有限的解空间内搜索满足条件的数据.
而数据库有个很大的优点, 就是有一个统一的描述语言, SQL, 来定义一切对数据的查询和修改操作.
在多年的不断改进和优化之下, 使用数据管理系统已经能比绝大多数人自行编写代码完成数据管理更加高效了.
但是对于组合优化问题, 无论是学术界还是工业界, 都还在以手工打造为主的阶段.
以 Gurobi 和 CPLEX 为首的基于线性规划的通用求解器存在各种各样的限制, 比如只支持混合整数规划和特殊形式的二次规划, 而且求解速度往往慢于针对性的启发式算法或精确算法.
其他的基于约束编程 (Constraint Programming) 的求解器, 或者基于启发式的 LocalSolver 等求解器提供了更丰富而强大的建模语言, 但表达能力仍然有限, 且求解效果尚不如 Gurobi.
更进一步, 将问题编码成布尔表达式可满足性问题 (SAT 或 MAX-SAT) 也是一个很有意思的方案, 但是如果说前两种得到了广泛应用的方案是用 C++ 编程, 这个方案简直就是在用汇编甚至设计电路.

这样看来, 打造一个更加通用更加高效的求解器似乎是一个很有吸引力的研究方向.

然而, 即使在 “大数据” 时代, PB 甚至 EB 级的数据量仍然是十分有限的, 跟几乎无穷无尽的组合优化问题的解空间相比, 实在是太渺小了.
简单机械地将问题拆分成多个子问题逐层求解的方式听起来前途十分渺茫.
因此, 要实现这个设想的难度也是十分巨大的.

附: 开篇问题的严谨定义

令 A(d) 表示矩形区域的左侧边缘与瑕疵 d 的右侧边缘存在重合的部分;
B(d) 表示矩形区域的下侧边缘与瑕疵 d 的上侧边缘存在重合的部分;
C(x) 和 C(y) 分别表示矩形区域的下侧边缘和左侧边缘与 x 轴和 y 轴重合.
其中边缘均为不包括矩形区域顶点的线段.

则矩形区域的放置位置需要满足以下约束:

存在 d != d’, 使 (A(d) && C(x)) || (B(d) && C(y) || (A(d) && B(d’)) 为真,
同时矩形区域内不存在任何瑕疵.

求矩形区域所有可能的放置位置.