GLPK/评论和基准测试
独立评论和数值基准测试是任何优化求解器项目的重要组成部分。此页面列出了一些对 GLPK 的独立评估,并试图说明 GLPK 通常在哪些方面表现出色。
GLPK 是自由软件——这可能是优点也可能是缺点,具体取决于您的需求和观点。访问源代码使研究人员,尤其是,能够修改 GLPK 以满足他们的需求,并在以后将他们的改进提交给 GLPK 维护者以供可能包含。
GLPK 无法与顶级商业求解器在超大型规模实例上的性能(或价格)相匹配。举一个例子,可以预期CPLEX在双单纯形问题上快 10-100 倍。通过查看一些当前的基准测试调查,可以进行更具体的比较。
GLPK 求解器提供以下方法和功能
- 针对非整数问题,采用改进的单纯形和原始对偶内点方法
- 针对整数和混合整数问题,采用分支定界算法以及Gomory 混合整数切割
- 针对图论问题,提供一些图、流网络和关键路径例程
- 包含用于解决布尔可满足性问题的MiniSat 求解器
- 支持任意精度算术
- 支持ODBC 连接,以与关系数据库和电子表格进行交互。
除图例程外,所有功能都可以通过 GLPSOL 命令行实用程序使用。
GLPK 对变量和约束的数量没有具体限制。当然,大型或困难问题可能会超过可用内存或无法在合理时间内解决。
- Fourer, Robert (2009). "Software survey : linear programming". OR/MS Today. 36 (3): 46–55.
{{cite journal}}
: Unknown parameter|month=
ignored (help) — 可供下载(需要注册)。
基准测试故意具有挑战性,并不一定代表用户想要解决的问题类型。
为了避免不可避免的维护延迟,官方的 GLPK 基准测试结果未在此处发布。相反,它们作为官方 GLPK 文档的一部分包含在内。相比之下,Mittelmann 基准测试可以直接查看——同时要注意 Mittelmann 未涵盖 GLPK 功能的某些方面,包括图论例程。
MIPLIB 是来自ZIB 的混合整数测试问题套件,目前为 MIPLIB 2003 版本[1]。GLPK 项目定期针对此测试套件的 2.0 和 3.0 测试集进行基准测试。最新的结果报告在以下文本文件中doc/miplib2.txt和doc/miplib3.txt在官方 GLPK 文档中。
GLPK 项目定期针对来自netlib 的ftp://ftp.netlib.org/lp/data 的套件进行基准测试。最新的结果报告在以下文本文件中doc/netlib.txt在官方 GLPK 文档中。
亚利桑那州立大学数学与统计学院的 Hans Mittelmann 在plato.asu.edu/bench.html 上维护着一个基准测试网站。虽然 GLPK 未列在起始页面上,但它包含在适当的测试类别中。基准测试使用NEOS 服务器 进行。GLPK 以下列测试套件中的形式出现
- plato.asu.edu/ftp/lpfree.html — 用于串行(单线程)求解器的线性规划测试
- plato.asu.edu/ftp/milpf.html — 用于串行(单线程)求解器的混合整数线性规划测试。
测试结果中包含问题大小指标。
NEOS 优化服务器 提供了一个门户,用于试用 GLPK。由于门户的组织方式,问题实例必须以GAMS 语言提交,而不是以本机 MathProg 语言提交。[2]
GLPK 项目不进行正式的代码审查。但是,用户有时会向 GLPK 邮件列表发布非请求的评论。例如
"非常感谢大家提供如此一流的软件包。代码是我见过的最好的代码之一,如果不是最好的。这些年来,我一直是数百万行其他人代码的唯一支持者。因此,看到如此精心编写的代码真是令人欣慰。"来源:GLPK 帮助列表,2011 年 1 月 13 日。
评论:用户可以在这里发布他们的问题和解决方案指标(本节将根据需求迁移到一个独立页面)。
- ↑ Achterberg,Tobias;Koch,Thorsten;Martin,Alexander(2006)。"MIPLIB 2003"。运筹学通讯。爱思唯尔。34(4):1-12。 doi:10.1016/j.orl.2005.07.00.
- ↑ Bob Fourer 指出,在 2011 年 2 月 1 日,运营 NEOS 的威斯康星大学有可能被说服也支持 MathProg。