【运筹OR帷幄】当我们求解数学规划问题时，如何区分数学建模和算法设计
编者按：在和『运筹OR帷幄』社区群友交流的时候，发现很多小伙伴还没能很好地区分算法设计和数学建模在求解一个具体问题时的区别。例如有人开口就问：“求解VRP问题用什么算法好？”
今天，希望借这个知乎问题，和大家捋一捋俩者的区别。
学术不精，且不那么严谨，还望大神们斧正！
作者 留德华叫兽 美国Clemson应用数学|运筹学硕士、博士候选人，德国海德堡大学数学|组合优化博士，博士研究方向为离散优化在计算机视觉的交叉应用。读博期间于意大利博洛尼亚大学和法国巴黎综合理工访问10个月，意大利IBM Cplex实习半年。学术不精，转而致力于科普，读博期间创办运筹OR帷幄（运筹学|数据科学|人工智能社区）以及DIY飞跃计划（全球1000+海外硕博留学咨询师）俩个知乎机构号|微信公众号|头条号|社区，并邀请学界|业界大佬联合举办了10+知乎 Live。现于德国某汽车集团无人驾驶部门机器学习组，担任计算机视觉研发工程师。
欢迎原链接转发，付费转载请前往 @运筹OR帷幄 的主页获取信息，盗版必究。
敬请关注和扩散 @运筹OR帷幄 B站及同名公众号，会邀请全球知名学者陆续发布运筹学、人工智能中优化理论等相关干货、知乎Live及行业动态。
作为一个运筹学数学规划（Math Programming）领域的博士，我研究问题通常的步骤是：
建立数学规划模型（最好是线性规划或线性整数规划）
将模型直接放入求解器（试图）求得精确解
如果问题规模比较大，考虑求解其对偶问题或一些大规模问题的分解技巧优化数学模型，例如：割平面、列生成、Benders等
设计针对该问题的启发式算法，（作为初始解）加速2
（其中2-4顺序不限）
01
—
数学规划模型的通用解法
该问题属于数学规划问题，因此上面这个问题对我来说，1这个步骤已经完成了90%，唯一要做的就是将L1范数|| . || 这个绝对值项线性化。
这就比较巧了，朋友们！我的这篇paper[1]用到的trick可以完美搞定，如下图：
问题（2）和知乎问题非常类似，目标方程的绝对值求和——即向量的L1范数，除了x在这里是一个整数变量。
通过引入俩组新的变量以及增加新的约束条件5b和5e，上述问题即可被线性化。
如下图：
该问题被转化成了线性整数规划问题（请忽略约束5d），而文章开头的知乎问题可以被转化成线性规划问题，然后就可以丢进优化求解器（如：Cplex或Gurobi）求得精确解了。
当然咯，还不要开心地太早！
既然是通用解法，计算速度是无法保证的。
但是，至少可以作为一个Baseline！这也是非常宝贵的！
要不然干嘛花那么大力气去做通用的优化求解器呢？你说是吧？
02
—
“优化”模型
“优化”这个词或许用得欠妥当，因为我也想囊括【将原问题转化为对偶问题】等这些技巧，大家心领神会就行。
回到知乎问题，这时候它已经是一个带约束的线性规划问题了，我们试图去“优化”它。至于为什么要优化，以及为何用下面的方法“优化”，我最后再说。
我们用拉格朗日松弛法，把约束条件“挪”到目标方程。
这里偷懒一下，直接引用『运筹OR帷幄』优化版快主编@覃含章 同学的知乎回答：
好了，变成一个无约束优化问题咯！
03
—
算法设计--具体问题具体分析
到这里我可以揭晓谜底了--为啥要使用拉格朗日松弛法“优化”该模型。
因为被“优化”后，这个知乎问题被转化成了一个Lasso问题！
什么是Lasso？
Umm，我还是直接上图吧：
看不懂不要紧，总之Lasso是一个非常经典的问题！
既然是经典问题，那么就意味着有无数研究者针对这一特定问题设计了无数专门的算法，这些算法充分考虑了Lasso问题的特性。
因此，到这里，你应该知道如何去设计针对这个问题的算法了？
--百度或谷歌Lasso算法吧，亲！
04
—
解题步骤回顾
遇到一个问题，首先是进行常规的数学规划建模。
因为不管怎样，建好模型后，把它插入优化求解器，它至少可以给你一个baseline！
完成这一步，你其实已经可以去设计针对该问题的特定算法（例如我通常会设计一个贪婪算法）。
但是……
正如本文的例子，如果你建立的数学模型，和经典的问题模型有几分神似，那么，就想尽一切办法把该问题“转化”成为一个经典问题，即使他们不完全等价（例如本文的拉格朗日松弛法）。
因为，经典问题被研究了那么多年，存在一整套数学理论和高效算法。
等到这个时候，再去设计算法也不迟哪！
总结一下：
建模->优化模型->设计算法
因此，『运筹OR帷幄』社群的童鞋们，不要抛出一个问题直接问算法了！
当然咯，凡事必有例外--近似算法（理论计算机）。
谈到它——抛出问题，就可以直接谈算法了！
