开源求解器的优化算法有哪些 开源求解器

01 简介

前几天老板让测一下一些开源 lp 求解器的稳定性。先看看本次上场的主角：lp_solve 是一个免费的（请参阅 LGPL 的 GNU 较小通用公共许可证）线性（整数）编程求解器，基于修订的单纯形法和整数的分支定界法。 http：//web.mit.edu/lpsolve/doc/Clp（硬币或线性规划）是一个开源的线性规划求解器。它主要用作可调用库，但也提供基本的独立可执行版本。它旨在寻找以下形式的数学优化问题的解决方案。 https：//github.com/coin-or/clpCPLEX Optimizer 为线性规划、混合整数规划、二次规划和二次约束规划问题提供灵活、高性能的数学规划求解器。这些求解器包括用于混合整数规划的分布式并行算法，以利用多台计算机来解决难题。

CPLEX可不是开源的哦，这里主要是作为基线，这样就可以看看lp_solve和Clp跟目前最先进的商业求解器的差距了。02设置

开始，还是先做一些准备工作。首先是测试数据集，本次测试了两个数据集：NETLIB（91例）： http：//www.netlib.org/lp/data/index.htmlL1（34例）：http：//www-eio.upc.edu/~jcastro/mindist_sdc.html

数据集中的文件有些是.mps，部分solver可以直接读取。而NETLIB中是压缩的MPS，需要用他提供的工具进行解压。

当然也可以从这里下载现成的：

https：//github.com/zrjer/LP-TEST-PROBLEM-FROM-NETLIB/tree/master/netlib_mps

测试平台是ubuntu 18.04，lp_solve和clp用的是python调用，而CPLEX还是用Java调用的（别问，问就是使起来顺手），虽然这些平台只是作为一个调用的作用，应该不会影响初始化的时间（我想是这样~错了麻烦多指正）。

然后讲讲python下怎么配置lp_solve和clp吧：lp_solvewindows平台：直接到https：//www.lfd.uci.edu/~gohlke/pythonlibs/#lp_solve这里下载对应版本的轮子然后pip进行安装，注意版本对应。linux平台：用conda安装，参考这里 https：//anaconda.org/conda-forge/lpsolve55ClpClp是一个解算器，Coin-or团队又为python开发了一个叫CyLP的包（https://github.com/coin-or/CyLP），可以直接用来调用他们家的办公器（CLP、CBC和CGL），所以下面讲怎么讲装CyLP。windows平台：直接pip install cylp，会自动安装clp等活动器。linux平台：比较麻烦，需要用conda先安装cbc等活动器，具体方法参照CyLP的说明，比较麻烦。

把测试的代码准备好然后再写个shell脚本进行批量测试：代码语言：javascript代码运行次数：0运行复制dir=MPS_Filesfor file in $dir/*；do python lpsolve_run.py $filedone登录后复制

意思是读取中的所有文件，然后在里面打个代码让他跑，当然跑完了记得在程序中把一些结果记录一下哦。最后把代码和脚本上传到服务器上，执行一下./run_lpsolve.sh，然后就可以安心去刷剧摸鱼等结果啦。03 计算结果

由于lpsolve只能使用单线程模式，因此在实验中也限制了CPLEX也只能使用单线程。关于表格列的说明：variable：模型中变量的个数。constraint：模型中约束的个数。non_zero：约束Ax=b中，矩阵A中非0个元素的个数。objective：问题的目标值。time：假设所花的时间。3.1 Netlib

共有96个算例，其中有5个CPLEX读取错误（我也不知道是啥。。），剩下91个算例中（平均variable=2524，平均constraint=978，平均non_zero=14763）：cplex能全部解到最优，平均工作时间为0.48s（yyds？）。lpsolve只求得了88个算例的最优化解，这87个算例的平均工作时间为0.89s。有三个算例在长时间内（大于2000s）无法连接作业解（表中标NA的单元格），手动终止了（用我导的这篇，就是这样）为什么lpsolve是免费的...）。

clp比lpsolve更稳定一点，所得的所有结果和cplex一致，时间上也低于lpsolve。表格中不同的地方已经加粗了。一些有趣的现象

对于E226.SIF这个案例，对比了几个solver，结果结果分别如下：官方报告的optimal：-18.7519cplex，gurobi，clp：-11.64matlab：-18.7519lpsolve： -25.86

会不会是模型解析的问题呢？我把他们的模型打出来看过了，模型都是一样的，只是仿真的结果不一样。

至于为什么会这样，在网上看到一个比较有趣的回答：

MIP 求解器处理浮点数据。对于像您这样的问题，数据幅度变化很大，这会导致舍入误差。任何 LP 求解器都必须对这些数据执行操作，这可能会放大问题。在某些情况下，例如您的问题，这会使求解器得出结论，认为问题不可行，但事实并非如此。当您修复变量时，求解器执行的浮点运算会更少。

像 Gurobi 或 cplex 这样的商业求解器通常在处理像您这样的数值困难数据方面做得更好。Gurobi 有一个参数 QuadPrecision，可以处理更高精度的浮点数。大多数求解器都有一个参数，可以使求解器更好地处理数值困难的数据。例如，LPSolve 有一个参数 epsint，可以放宽对整数的定义。该参数的默认值为 10e-7，因此 0.9999999 会被视为整数，而 0.9999998 则不是。您可以将此值调大，但可能会产生不可接受的结果。

您遇到了抽象泄漏。从技术上讲，您的问题属于混合整数规划的范畴，但 MIP 求解器并非旨在解决该问题。混合整数规划是一个 NP-Hard 问题。不可能有一个求解器能够对所有输入快速可靠地运行。MIP

奥尔弗试图很好地解决来自不同领域的问题，如投资组合优化、供应链规划和网络流。它们并不是为了解决密码学问题而设计的。

出处：https：//stackoverflow.com/questions/16001462/solving-an-integer-线性-program-why-are-solvers-claiming-a-solvable-instance3.2 L1数据集

共34个案例，初步观察有以下的结论：lpsolve和clp差不多很多，cplex相当领先。有好几个案例，几个solver最终的解不一样，表中标粗的部分。

最后经过测试发现，CPLEX中的pre_solve有可能会影响到最后的结果，按理说不应该影响才是，摘一点官网的介绍：

Presolve在于修改模型改进它，以便更有效地求解。

CP Optimizer 在搜索之前预先求解输入模型。预求解在于修改模型以改进模型，以便更有效地求解。 Presolve 的工作原理是通过删除冗余和固定表达式来减少线性约束来简化模型，并通过聚合约束或因式分解公共子表达式来强化模型以实现更多域缩减。

因此，总体引擎内存消耗可能会增加，因为创建了内部模型来执行改进操作

有可能是求解器的一些bug。在lpsolve中也遇到过，用pre_solve日后竟然直接说问题不可行了？？？有趣。04结论

这里有份开源的表格，里面考察了更多的求解器，数据也权威更多，看到很多国产的求解器在表格中都取得了很不错的成绩，希望国产的MILP也快快提上日程。

http：//plato.asu.edu/ftp/lpsimp.html

总结一下，作为开源免费的LP求解器，clp是一个不错的选择，目前cylp也在逐步开发。Google的或者工具因为没有测他们的python接口还没有很完善。lp_solve比较出名了，但是感觉还是不稳定吧，帮助文档倒是写得不错。

以上就是开源线性规划学习器（线性规划）求解器）LP_Solve和CLP的PK的详细内容，更多请关注乐哥常识网其他相关文章！