GLPK/Add-Ons

此页面描述 GLPK 的“附加组件”——包括 GLPK 代码库的非官方扩展，以提供一些特殊功能。因此，这些扩展需要合适的编译环境。

BAK：分支定界分析工具包

使用 BAK 生成的分支定界树，并使用 gnuplot 渲染

BAK 是用于分析 GLPK 和其他求解器的分支定界行为的工具。 BAK 随 GPL 2.0 许可证和 CPL 1.0 许可证一起分发——用户可以选择使用哪种许可证。

将 BAK 添加到 GLPK

可以使用以下方法下载最新的 BAK 版本

svn checkout https://projects.coin-or.org/svn/CoinBazaar/projects/BAK

可以在 https://projects.coin-or.org/CoinBazaar/browser/projects/BAK/ 查看源代码。

BAK 在以下目录中提供了一些针对 GLPK 的修补源文件bak/interfaces/GLPK. 首先将这些文件复制到正常的 GLPK 源代码目录，然后重新构建 GLPK（参见章节 编译 GLPK）。

使用

修改后的独立求解器 GLPSOL 会写入一个包含分支信息的文件。此文件的名称使用命令行选项指定--bakfile, 例如

glpsol --bakfile tsp.bak -m tsp.mod

该文件包含有关创建的节点、分支过程、遇到的整数不可行性和运行时进度的信息。该文件格式在 [1] 中有说明。例如，该文件可能以以下几行开头。

#SOLVER: GLPK
#PROBLEM: (null)
0.002000 branched 1 0 M 6030.000000 6.466667 32
0.002000 candidate 2 1 L
0.002000 candidate 3 1 R
0.004000 branched 2 1 L 6030.000000 6.466667 30
0.004000 candidate 4 2 L
0.004000 candidate 5 2 R
0.006000 branched 4 2 L 6069.000000 7.533333 32
0.006000 candidate 6 4 L
0.006000 candidate 7 4 R
0.008000 branched 7 4 R 6069.000000 7.266667 30
0.008000 candidate 8 7 L
0.008000 candidate 9 7 R
0.009000 infeasible 9 7 R
...

可以使用 python 脚本创建中间文件，以便使用 gnuplot 可视化这些信息

python bak/BAK_visual.py --all tsp.bak

可以使用 PNG 文件查看器（例如 evince）查看生成的文件

evince tree_alt.004.png

丹齐格-沃尔夫分解

丹齐格-沃尔夫分解 是一种将结构适当的 LP 问题分解为子问题的方法——然后分别解决这些子问题，通常是并行解决。基础约束矩阵需要某种形式的块结构。该技术最初是在 1960 年提出的，鉴于廉价的多核个人计算机的出现，它引起了人们的重新兴趣。

该 丹齐格-沃尔夫求解器项目 现在托管在 SourceForge 上，提供了使用 GLPK 的丹齐格-沃尔夫的通用并行实现。该代码由 Joey Rios 编写。第一个公开发布版本 1.0 于 2010 年 10 月 15 日上传。

该实现使用 Pthreads 线程管理库。GLPK 需要进行少量修改才能允许其并发运行。因此，GLPK 的全部内容都包含在丹齐格-沃尔夫求解器项目的代码库中。除了 Pthreads 之外，不需要其他专业库。

该代码已成功构建在 Mac OS X 10.5 和 10.6、Red Hat Enterprise Linux 以及通过 cygwin 的 Windows XP 上。

作者希望这个工具能为丹齐格-沃尔夫分解的进一步研究提供一个起点。事实上，虽然跨多个领域的许多论文都利用了 DW，但这可能是唯一提供 DW 源代码供开放测试和开发的项目。

该软件有一些限制。截至 2010 年 10 月，只能使用 LP 公式，子问题必须是有界的。也可能存在错误。

建模者为主问题和每个子问题提供 CPLEX LP 输入文件。还需要一个简单的引导文件，该文件告诉命令行工具所有内容在哪里。该代码库包含从教科书和网站上获取的或由作者开发的几个 DW 示例。

有关一般情况下和并行计算下丹齐格-沃尔夫分解的评估，请参见 Tebboth (2001)。 有关空中交通管制应用程序，请参见 Rios 和 Ross (2010)。