求解器选择与收敛性问题(OR |
您所在的位置:网站首页 › tsp问题求解器 › 求解器选择与收敛性问题(OR |
文章目录
1.求解器的选择2.求解器的收敛2.1 相同时间下求解结果2.2 不同时间段求解结果2.3 目标函数变化曲线
3.结论
1.求解器的选择
OR-Tools提供了用于求解 线性规划和 混合整数规划问题的 MPSolver 接口容器,易于调用各种不同求解器。gurobi 当然无论在各个问题上性能都要优胜许多,考虑到毕竟是商用求解器,这里主要枚举开源免费的求解器。 问题类型求解器纯整数规划(IP)CP-SAT线性规划(LP)Glop混合整数规划(MIP)SCIP, CP-SAT由于MIP问题是最为麻烦难解的,建模时候尽量考虑建成LP或IP,求解速度会快很多。尤其google ortools 整合了SAT/CP solver,CP_SAT 对于一部分MIP问题也可以求解,部分问题效果比SCIP好很多。 2.求解器的收敛做一个简单的数值实验对比不同求解器的求解速度。构建一个小规模整数规划问题,算例都一样,模型也一样,唯一的区别即求解器不同,这里测试GUROBI,CP_SAT,SCIP三个比较常用的求解器。 ortools调用solver. solver = pywraplp.Solver.CreateSolver('SCIP') # GUROBI SCIP CP_SAT 2.1 相同时间下求解结果先用gurobi求解算例,14s后得到最优解,设定求解时间为14s,再依次求解CP_SAT,SCIP,结果如下表所示。 求解器求解时间(s)是否最优解objgurobi14是9190.0CP_SAT14是9190.0SCIP14否9305.49(CP_SAT 在规定时间内同样求得最优解,但如果不加限制求解依然不会停止,这里可能是求解器数值问题) 2.2 不同时间段求解结果我们设定不同的停止时间,观察求解器的求解情况,可以看到gurobi无论是在初始解以及最后的收敛上都要技高一筹,其实在第7s时就已经找到了最优解,但程序最终停止时间是14s,剩余的这段时间大概就是验优的过程。我设置的算例为IP,CP_SAT表现略逊gurobi但也不错,但SCIP在短时间内陷入了局部最优,跳出局部最优需要更多的时间,显然这就是不同求解器内部性能的一个差异了。 limit Time(s)gurobiCP_SATSCIP19215.09241.09305.4929215.09215.59305.4939215.09215.09305.4959209.59211.59305.4979190.09199.59305.4910opt9196.09305.4912opt9205.59305.4914opt9190.09305.49 2.3 目标函数变化曲线上面用一个小规模算例简单比较了一下三个求解器的求解性能,为了更好的看到求解器gap变化情况,这里将算例规模适当扩大(算例太大了过于费时),给予不同的停止时间,绘制目标函数随时间变化曲线。结果很显著,对于整数规划问题CP_SAT效果明显优于SCIP。
|
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |