在AlphaDraw筑绘通平台中， AI 理论模型及相关工具对整个 AI 自动出图流程具有核心支撑作用，其贯通了从识图到画图的各个环节。
在 AI 技术体系之下，有一个并未如此闪耀的理论工具，也为 AI 画图的质速提升发挥了重要的作用，这个工具就是运筹学领域下的各种“瑞士军刀”。运筹学是一个博大精深的经典学科。从定义上来说，是一门应用数学学科，其利用统计学、数学模型和资料科学方法，去寻找复杂问题中的最优或者近似最优的解。事实上，人工智能技术也可以被划入运筹学的一个分支。
运筹学
运筹学是寻找最优策略的方法体系。在建筑施工图过程中，在各种规则限定的画法之外，有大量有赖于设计师发挥自身的经验和人类理性进行优化设计的地方。例如如何处理的连线，如何排布构件，如何平衡各种参数等等。从技术角度，这些设计过程都是一种决策过程，而决策过程总是可以被刻画成一个优化问题，进而可以使用运筹学的方法来解决。
之前的AI论技中，我们在地上照明平面图的构件连线和标注自动排布算法中，介绍了基于启发式算法思想设计的优化算法用来求解布局布线问题的最优解或者次优解。这些启发式算法是运筹学的一个重要的分支。本文旨在介绍运筹学领域的另一个重要分支：混合整数规划方法 (Mixed Integer Programming， MIP)。
△混合整数规划问题在数学规划问题中位置，图片来自 https://www.birs.ca/cmo-workshops/2018/18w5208/files/GleixnerAmbros.pdf
MIP 方法属于数学规划方法族，它的兄弟姐妹还包括了线性规划方法，动态规划方法，以及组合最优化方法等。MIP 方法由于其应用场景的广泛性得到了学术界和工业界的普遍关注，目前已经出现了大量的成熟工具可以让我们高效地求解 MILP 问题。因此，只要我们能够将我们的目标问题建模成合适的 MILP 模型，我们就离最终最优答案很近了。
什么是 MILP
在解释混合整型线性规划模型之前，我们需要介绍一下线性规划模型。任何一个优化问题都可以划分成目标与约束两个部分。当这两个部分都是线性的时候，我们就可以称这个问题是一个线性规划问题。下面的公式就是刻画了一个简单的线性规划问题：
其中， x，y 为优化问题的决策变量。线性规划问题通常易于求解。目前商用求解器可以在数秒内计算具有上千万个约束的线性规划问题。注意到，上面的简单问题中，变量 x，y 都是连续变量，倘若我们将这些变量的取值范围从连续的实数空间变更到不连续的整数空间，那么，这个问题就从线性规划问题，变成整数规划问题。整数规划问题在组合优化问题中非常常见。若干整数规划变量中所有变量都是离散的整数，那么这类问题被称为纯整数规划问题，这些变量中同时包含了连续变量和离散变量，那么这类问题被称为混合整数规划问题。在现实问题中，尤其是在我们所关注的建筑识图图自动绘制的具体场景中，混合整数线性规划问题要更加普遍。
混合整数规划的求解方法
「求解原理」
一般来说，混合整数规划问题的求解是一个 NP-hard 的问题，这意味着我们无法在多项式时间内得到混合整数规划问题的精确解。但是通过放松对解的精确性的要求，我们可以得到一些更加高效的求解方法。这种“松弛”思想是各种整数规划算法的基础思想。
分支定界法 (Branch and Bound Algorithm) 是求解混合整数规划的主要技巧之一，其核心思想是将 NP-hard 的原问题分成多个线性规划问题，这些线性规划问题的解可以确定原混合整数规划问题的解的上下界。随着算法迭代，我们可以让上下界之间的区间逐渐缩小，从而得到一个距离最终精确解的距离小于一定阈值的次优解。
△分支定界法的原理示意，图片来自 Groubo。可以看到分支定界法会将原问题分解成多个 MIP 问题，我们会求解这些 MIP 的线性松弛问题，并在这个过程中最终解的上下界。
分支定界法的原理比较清晰，但是在实现层面上非常复杂。好在经过长时间的研究和发展，学术界和产业界涌现了一批专门针对混合整数规划问题的求解器。
「求解器」
求解方法的思想虽然简单，但是实现起来却比想象的复杂，如何管理各个分支的存储，分支的先后顺序，以及一些提高分支定界法效率的算法等等。
国外知名的混合整数规划求解器有：IBM Cplex，Gurobi，FICO Xpress，SCIP。前三个都是商业软件，开源的SCIP是由柏林ZIB研究机构开发并维护，但商业用途需要购买版权。如果用作教学、科研用途，这四个都可以免费下载。
由于求解器在工业应用中的关键作用，近几年，国内也有几家公司投身于开发优化求解器，其中比较令人瞩目的有杉数科技的COPT和阿里的MDOPT，两款优化器在线性优化方面已经处于领先地位。混合整数规划方面的话还有一定差距。
由于求解效率是不同求解器的衡量标准，Hans Mittelmann每年会针对各求解器做测评，我们可以以此作为一个参考。需要单独说明一下的是，IBM和FICO要求从2019年开始将CPLEX和XPRESS不再纳入评测榜单。
「求解器MILP评测榜单」
从评测榜单中可以看出，在MILP方面，Gurobi有比较大的优势。杉数的COPT在单核的情况下跟SCIP效率相近。8核下比SCIP提升明显。榜单中的求解器效率差距可能达到20倍，所以不同的求解器差距比较大。
「求解器LP评测榜单」
能看到 COPT，MDOPT，Gurobi处于领先地位，差距不算大。但与其它的求解器差距可能达到百倍。所以求解器也很关键。
在AI自动出图中的应用
在建筑施工图的自动出图中，存在很多可以被建模成混合整数规划问题的例子。例如在AlphaDraw筑绘通平台已经公测的楼梯间详图模块中，AI 画图需要解决楼梯段的碰头问题。在安排梯段和休息平台的长度和位置时，我们需要确上下梯段的距离大于一定的阈值，并且，梯段与休息平台的还需要满足其他规则性约束，例如台阶数量，疏散半径等等。这个问题可以建模成为一个典型的混合整数规划问题。
若使用的直接遍历的方法， 这个问题的求解时间将会有很大的波动。如果运气较好，我们能够在数分钟内找到一个可行解，但是更多的时候求解过程将会非常漫长，甚至出现超时（求解用时超过 1 个小时）。我们将这个问题建模成一个混合整数规划模型，并使用求解器进行求解，则在大多数场景下，我们可以在数十毫秒的时间内得到可行解，并且我们可以对美观度（如平台对齐）进行优化。下面的动图展现了一个求解的结果。
参考文献：
[1]. http://plato.asu.edu/bench.html
[2]. http://plato.asu.edu/ftp/milp.html
[3].【学界】混合整数规划/离散优化的精确算法--分支定界法及优化求解器
[4]. Computational Mixed-Integer Programming
[5]. 维基百科：运筹学
©版权归品览所有
未经授权请勿转载
RECOMMENDED
一键试用 筑绘通
点击阅读原文或扫码
即刻预约
AlphaDraw筑绘通正逐步上线施工图领域各专业的新模块：包含建筑、结构、暖通、电气、给排水、室内六大专业，47个一级系统，共计180个二级模块。同时，小览也会陆续更新新模块内容及操作教程，敬请期待吧！
品览是AI建筑设计智造者，专注于建筑设计AI服务，致力于为地产企业和设计院客户提供AI设计出图服务。自主研发的建筑AI智能设计云平台AlphaDraw「筑绘通」，基于计算机视觉技术，建筑设计知识库和生成式强化学习算法帮助客户自动完成施工图设计。仅需上传建筑方案图纸就可以自动完善成套施工图，并符合各地设计规范，助力企业标准化出图、效率质量双提升。
本文来自微信公众号“品览Pinlan”（ID：pinlandata）。大作社经授权转载，该文观点仅代表作者本人，大作社平台仅提供信息存储空间服务。
