半年间对提高自带解算器效率的认识（8小时到8分钟）

vincentac

       最近肺炎疫情，只能在家研究模型，最近半年主要在写和改自己模型。今晚来说下过程，供有同样非线性问题的朋友讨论一起进步（偏求解的模型）自己的模型数据量在10-15万之间，计算公式大概在3万多，变量56个，计算精度为excel最大精度，属于非线性规划求解，由于啥都是现学，数学垃圾，所以水平有限，说下自己的改进之路。

非线性问题对于规划求解solver首选肯定是GRG解算器，不过对于求最优解不要存在太大幻想求到全局最优，除非凸的。简约梯度法求局部最优还是比较合理的期望，第一次运行，大概9个子问题深度，运行了8个小时= =，惨不忍睹的效率，而且得到的局部最优解相当不完美。
       通过上论坛和去外网查资料，首先发现自己模型第一个严重的问题，函数的乱用，论坛里大神也有说过的，像逻辑函数非连续函数，甚至max，min，abs啊这些也是会严重拖慢你模型求解速度的（数据少的不复杂的忽略），查找函数你就更不要想了（也是有办法，不过自己模型用的不太多，用个傻办法代替了），总之第一步一句话，把你的函数往连续线性函数去靠，靠不到就用逼近函数代替（像maxminabs这种常用的想不用太难，我全是用逼近函数替换的，虽说不相等，但是从结果来看还是可以接受的，要是能变成线性问题那解算速度是杠杠滴）数学不好的只能不耻下问去找个数学好的问下了。
       通过第一步你的模型应该最不理想也会变成一个连续的非线性问题了，我模型经过这步大概走一次平均在3-3.5个小时了已经，所以很有必要。第二步就是认识你的模型，先减小数据规模，检视整个流程，会数学软件的可以做图看看，这步其实主要就是要你对你的模型的数学特征等有明确的认识，方便精简流程。
下面列几个点，供大家交流：
初始解：不要随便选一个放上去算，你最终会后悔的（深有体会），对于局部最优，初始解太重要了，你甚至可以专门写个小的挑选良好初始解的vba来专门计算适合你模型的初始解。
变量；在solver里变量算半硬性指标，变量约束可以是弹性的，可以用vba或者直接在表格里进行限制和调整，来改善计算流程（基本都会比不改前最优解更完美）
二次规划：如果缩减后还是非线性就可能涉及到二次规划，不细说，需要自己改公式，或者去写专门的vba判断和提速解算
grg改进：GRG只是一个最基本的方法，网上有各种混合的梯度法来提高速度或者避开鞍点一类的，由于涉及到纯数学，网上很多，要自己学。计算方向：算是GRG改进里的吧，主要是梯度法里面关于各系数的确定和分段的计算方向，像步长一类的还是需要vba一类的去进一步控制，否则solver自身遇到这类问题有时表现就是每次计算改进的程度很低，缓慢犹如蜗牛。
       这就算我对自带解算器提高速度的全部理解了，说的比较笼统，因为涉及太多，而且有大量数学问题，有时间再展开了。
       经过这一步我用excel自带的求解器走一次大概需要2个小时左右了，从8个小时缩减到2个小时，基本已经到了我的能力极限。毕竟我的数学大学的时候也就比及格高点有限，自学也是有限度的，外网太深的文章我看不懂了，国内有的论文有，但是还要钱才能看，我是个穷人pass。
不过话说回来2个小时对于我来说还是不爽的，所以下面的方法只能从偷巧的来了，因为excel自身的规划求解是frontline做的，我首先也是去外网看了下，的确人家有商业版，不过年费不是我这种草民能负担的起的，还要全程联网= =，只能一台计算机用，shit！不过提供15天试用，有想玩的可以去申请下用用，我先说下我的试用结果，经过我一个星期的参数调试，运行一次现在需要3-8分钟一次（OMG!我吐出一大滩血，我付出的时间啊，现在心中无数草泥马在奔腾！）
                p。s：网上开源的excel求解器我也下来试过，都不太行，还是有差距，建议非线性就不要尝试了，全局求解可以尝试下，不过效率并不高。国内那家说自己做商业解算器的那家公司你能把你非线性求解器放出来不，放个线性的出来有啥意思，前段吹得震天响，好歹拿出来测试测试。
      总结：对于坚持用excel自带解算器的，你的模型第一步是很有必要的，第二步尽你最大能力就好，毕竟excel自带的求解器基本就没怎么升级过（wps更次，内部也不改进），而且excel对于多核还是感觉不行啊，也用过hpc专版那个，对多核还是不理想，分配有问题，总之我的模型在excel上能够运行一次最快也就2小时以内，要达到8分钟我感觉我没那实力了，如果让我更进一步恐怕要调用外部接口了。
      想要免费达到更快速度，你需要换软件了，最近一直再试各种能调取excel数据有破解版的专业计算软件了，恐怕又是个把月时间要花去。要是你的模型打算干事，还是尽快从专业软件写起，从这几天下来感觉专业软件对速度和对多核的支持还是有很大差别的，再缩减计算时间还是很大希望的。
       最后在网上写下我得目标：15-20分钟。
        P.s：本人非专业，写代码不爱加备注，所以写文章也从不回头看，上面肯定有说错打错写错的，只是想让能力有限的一些人少走些我得弯路！
             p.s中的p.s:居然写了20分钟

13602822168

学习，学习，学习，学习，

yjh_27

快100倍！！比起EXCEL自带规划求解，这款求解器实在太牛了
http://club.excelhome.net/thread-1514014-1-1.html
(出处: ExcelHome技术论坛)

vincentac

yjh_27 发表于 2020-2-4 19:57
快100倍！！比起EXCEL自带规划求解，这款求解器实在太牛了
http://club.excelhome.net/thread-1514014-1-1 ...

用过这款开源的，外网大概可以找到3，4款开源项目求解器，大部分是针对线性的或者带全局算法的，非线性的有但是效率很低（要不商业求解器也早没市场了是吧），可能上面原贴对开源项目说的太绝对，yjh_27说的这款求解器外挂的算法有点单一，主要也是针对lp问题或者大型lp有优化，对于非线性并没有太高的提速。其实对于非线性模型，能用到lp的方法主要是分段后取值对于计算方向上的选择可能加速非线模型计算（决定区段可以向前向后解析或者不同位置差分），大型LP求解器没有整合专门的算法的话对非线性问题整体速度并没有十分明显的提升，当然仅仅针对我做过的几个模型而已。
   

vincentac

最近几天一直在尝试gurobi，这玩意的确很强大，不过弄那个许可好麻烦，而且到期还要再申请，总之不花钱想用好麻烦，不过找人帮忙最终用上了，正在熟悉中，不过感觉好复杂，有点难适应，做个简单模型运算了下速度很叼，估计有门。
另一面再试着让别人帮我申请frontline的教育许可，不知道结果行不行，目前没信= =。
p.s：最近还发现了个有趣的软件lumina的analytica，主要看简介对他那个蒙特卡洛快速演算感兴趣，大家可以搜下，有兴趣做个运筹学模型的可以玩玩，当然最主要的是这个有不花钱的。至于能不能提速小型的决策模型不清楚，最近时间太少

astupig

其实, 如果非线性规划, 听说Lingo速度还比较快, 但是不能支持Excel很多公式...
如果线性规划, 我个人觉得Gurobi和Cplex比较快, 至少比Lingo还要快.