作者：留德华叫兽
在和『运筹OR帷幄』社区群友交流的时候，发现很多小伙伴还没能很好地区分算法设计和数学建模在求解一个具体问题时的区别。例如有人开口就问，“求解VRP问题用什么算法好？”
今天，希望借这个知乎问题，和大家捋一捋两者的区别。
-- 学术不精，且不那么严谨，还望大神们斧正！
01
—
数学规划模型的通用解法
该问题属于数学规划问题，因此上面这个问题对我来说，1这个步骤已经完成了90%，唯一要做的就是将L1范数|| . || 这个绝对值项线性化。
这就比较巧了，朋友们！我的这篇paper[1]用到的trick可以完美搞定，如下图：
问题（2）和知乎问题非常类似，目标方程的绝对值求和--即向量的L1范数，除了x在这里是一个整数变量。
通过引入俩组新的变量以及增加新的约束条件5b和5e，上述问题即可被线性化。
如下图：
该问题被转化成了线性整数规划问题（请忽略约束5d），而文章开头的知乎问题可以被转化成线性规划问题，然后就可以丢进优化求解器（如：Cplex或Gurobi）求得精确解了。
当然咯，还不要开心地太早！
既然是通用解法，计算速度是无法保证的。
但是，至少可以作为一个Baseline！这也是非常宝贵的！
要不然干嘛花那么大力气去做通用的优化求解器呢？你说是吧？
02
—
“优化”模型
“优化”这个词或许用得欠妥当，因为我也想囊括【将原问题转化为对偶问题】等这些技巧，大家心领神会就行。
回到知乎问题，这时候它已经是一个带约束的线性规划问题了，我们试图去“优化”它。至于为什么要优化，以及为何用下面的方法“优化”，我最后再说。
我们用拉格朗日松弛法，把约束条件“挪”到目标方程。
这里偷懒一下，直接引用『运筹OR帷幄』优化版块主编@覃含章 同学的知乎回答：
https://www.zhihu.com/question/424948743/answer/1552969000
好了，变成一个无约束优化问题咯！
03
—
算法设计--具体问题具体分析
到这里我可以揭晓谜底了--为啥要使用拉格朗日松弛法“优化”该模型。
因为被“优化”后，这个知乎问题被转化成了一个Lasso问题！
什么是Lasso？
Umm，我还是直接上图吧：
看不懂不要紧，总之Lasso是一个非常经典的问题！
既然是经典问题，那么就意味着有无数研究者针对这一特定问题设计了无数专门的算法，这些算法充分考虑了Lasso问题的特性。
因此，到这里，你应该知道如何去设计针对这个问题的算法了？
--百度或谷歌 Lasso算法吧，亲！
04
—
解题步骤回顾
遇到一个问题，首先是进行常规的数学规划建模。
因为不管怎样，建好模型后，把它插入优化求解器，它至少可以给你一个baseline！
完成这一步，你其实已经可以去设计针对该问题的特定算法（例如我通常会设计一个贪婪算法）。
但是。。。
正如本文的例子，如果你建立的数学模型，和经典的问题模型有几分神似，那么，就想尽一切办法把该问题“转化”成为一个经典问题，即使他们不完全等价（例如本文的拉格朗日松弛法）。
因为，经典问题被研究了那么多年，存在一整套数学理论和高效算法。
等到这个时候，再去设计算法也不迟呐！
总结一下：
建模->优化模型->设计算法
因此，『运筹OR帷幄』社群的童鞋们，不要抛出一个问题直接问算法了！
当然咯，凡事必有例外--近似算法（理论计算机）。
谈到它--抛出问题，就可以直接谈算法了！
整数规划精确算法/近似算法/(元)启发算法/神经网络反向传播等算法的区别与关联
参考
1.^An ILP Model for Multi-Label MRFs With Connectivity Constraints https://ieeexplore.ieee.org/abstract/document/9102375
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
微信编辑：疑疑
关注我们
FOLLOW US
