在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]. 维基百科：运筹学
©版权归品览所有
未经授权请勿转载
AlphaDraw筑绘通正逐步上线施工图领域各专业的新模块：包含建筑、构造、暖通、电气、给排水、室内六大专业，47个一级系统，共计180个二级模块。同时，小览也会陆续更新新模块内容及操作教程，敬请期待吧！
品览是AI建筑设计智造者，专注于建筑设计AI做事，致力于为地产企业和设计院客户供应AI设计出图做事。自主研发的建筑AI智能设计云平台AlphaDraw「筑绘通」，基于打算机视觉技能，建筑设计知识库和天生式强化学习算法帮助客户自动完成施工图设计。仅需上传建筑方案图纸就可以自动完善成套施工图，并符合各地设计规范，助力企业标准化出图、效率质量双提升。
