GLPK/常见问题解答

GNU 线性规划工具包常见问题解答

Summary: Frequently Asked Questions about the GNU Linear Programming Kit
Original author: Dr. Harley Mackenzie <[email protected]>                     

简介

问. 什么是 GLPK？

答. GLPK 代表 GNU 线性规划工具包。GLPK 包是一个用 ANSI C 编写的例程集，并以可调用库的形式组织起来。此包旨在解决大型线性规划 (LP)、混合整数线性规划 (MIP) 和其他相关问题。

GLPK 包包括以下主要组件

• 单纯形法的实现，
• 原始对偶内点法的实现，
• 分支定界法的实现，
• 应用程序编程接口 (API)，
• GNU MathProg 建模语言（AMPL 的子集），
• GLPSOL，一个独立的 LP/MIP 求解器。

问. 谁开发和维护 GLPK？

答. GLPK 目前由莫斯科航空学院应用信息学系安德鲁·马霍林开发和维护。安德鲁的电子邮件地址是 <[email protected]>，邮寄地址是俄罗斯莫斯科沃洛科拉姆斯克耶·什., 4 号，莫斯科航空学院，安德鲁·奥·马霍林。

问. GLPK 是如何授权的？

答. GLPK 目前根据 GNU 通用公共许可证 (GPL) 授权。GLPK 是自由软件；您可以在 GNU 通用公共许可证的条款下重新分发和/或修改它，该许可证由自由软件基金会发布；无论是版本 2，还是（在您的选择下）任何更高版本。

GLPK 不根据较小通用公共许可证 (LGPL) 授权，与其他自由 LP 代码（如 lp_solve）不同。最显着的含义是链接到 GLPK 库的代码必须根据 GPL 发布，而使用 LGPL，链接到库的代码不必根据相同许可证发布。

问. GLPK 主页在哪里？

答. GLPK 主页是 GNU 网站的一部分，可以在 <http://www.gnu.org/software/glpk/glpk.html> 找到。

问. 我如何下载和安装 GLPK？

答. GLPK 源代码分发可以在您最喜欢的 GNU 镜像上的子目录 /gnu/glpk/ 中找到 <http://www.gnu.org/prep/ftp.html>，可以直接从源代码编译。

GLPK 包（与所有其他 GNU 软件一样）以打包档案的形式分发。这是一个名为 'glpk-x.y.tar.gz' 的文件，其中 x 是主版本号，y 是次版本号。

为了准备分发以进行安装，您应该

1. 将 GLPK 分发文件复制到某个子目录。
2. 输入命令 'gzip -d glpk-x.y.tar.gz' 以解压缩分发文件。解压缩后，分发文件的名称将自动更改为 'glpk-x.y.tar'。
3. 输入命令 'tar -x < glpk-x.y.tar' 以解压缩分发文件。执行此操作后，将自动创建子目录 'glpk-x.y'，它是 GLPK 分发文件。

解压缩和解压缩 GLPK 分发文件后，您应该配置包并编译应用程序。编译的结果是

• 文件 'libglpk.a'，它是一个库档案，包含所有 GLPK 例程的目标代码；以及
• 程序 'glpsol'，它是一个独立的 LP/MIP 求解器。

完整的编译和安装说明包含在分发文件中包含的 INSTALL 文件中。

该分发包含适用于 Microsoft Visual C/C++ 版本 6 和 Borland C/C++ 版本 5 的 make 文件，默认情况下编译和链接 glpk*.lib 库文件、glpk*.dll DLL 文件和 glpsol.exe 应用程序文件。从 <http://gnuwin32.sourceforge.net/packages/glpk.htm> 也提供了使用 mingw32 C/C++ 编译器编译的 GNU Windows 4.1 二进制文件、源代码和文档。

问. 有 GLPK 邮件列表或新闻组吗？

答. GLPK 有两个邮件列表：<[email protected]> 和 <[email protected]>。

主要讨论列表是 <[email protected]>，用于讨论 GLPK 的所有方面，包括它的开发和移植。还有一个专门用于报告错误的列表 <[email protected]>。

要订阅任何 GLPK 邮件列表，请发送一封主题行仅为“subscribe”的空邮件到相关的 -request 列表。例如，要订阅主要列表，您需要将邮件发送到 <[email protected]>，邮件正文为空，主题行仅为“subscribe”。

订阅 GLP 邮件列表的另一种方法是访问网页 <http://mail.gnu.org/mailman/listinfo/help-glpk> 和 <http://mail.gnu.org/mailman/listinfo/bug-glpk>。

目前没有专门针对 GLPK 的新闻组。

问. 谁维护此常见问题解答，我如何为该常见问题解答做出贡献？

答. 本常见问题解答的现任维护人是 HARD 软件的哈利·麦肯齐博士，尽管常见问题解答的内容来自许多来源，例如 GLPK 文档、GLPK 邮件存档和原始内容。

哈利的电子邮件地址是 <[email protected]>，邮寄地址是澳大利亚维多利亚州纽镇邮政信箱 8004，HARD 软件公司。

所有对本常见问题解答的贡献，例如问题和（最好）答案，应发送到 <[email protected]> 电子邮件地址。此常见问题解答版权归哈利·麦肯齐 2003 所有，并根据与 GLPK 相同的许可证、条款和条件发布，即 GPL 版本 2 或更高版本。

贡献不会直接在常见问题解答正文中引用，因为这将变得难以管理且杂乱无章，而是在对本常见问题解答的贡献者列表中列出。如果您是本常见问题解答中包含的任何信息的作者，并且您不希望您的内容被包含在内，请联系常见问题解答维护者，您的资料将被删除。此外，如果您没有被正确地列为本常见问题解答的贡献者，您的详细信息已更改，或者您不希望您的姓名列在贡献者列表中，请联系常见问题解答维护者进行更正。

问. 我在哪里可以下载此常见问题解答？

答. 最新版本的 GLPK 常见问题解答可以从 <http://www.hardsoftware.com/downloads.php#GLPK+FAQ> 下载，以下格式

• DocBook
• 格式化文本
• Adobe PDF

问. 常见问题解答的贡献者是谁？

答. 常见问题解答的内容来自以下来源

• 迈克尔·亨内布里
• http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html
• 哈利·麦肯齐，HARD 软件私人有限公司。
• 安德鲁·马霍林，莫斯科航空学院应用信息学系

GLPK 函数和功能

问. GLPK 开发的现状如何？

答. GLPK 正在开发中，目前正在不断开发中。截至目前版本 4.3，GLPK 是一个基于单纯形的求解器，能够处理最多 100,000 个约束的问题。特别是，它成功地解决了 netlib 中的所有实例（请参阅 GLPK 分发中包含的 bench.txt 文件）。内点求解器不太健壮，因为它无法处理密集列，有时会因数值不稳定或收敛速度慢而终止。

混合整数规划 (MIP) 求解器目前基于分支定界，因此它无法解决困难或非常大的问题，可能的实际限制为 100-200 个整数变量。但是，有时它能够解决最多 1000 个整数变量的更大问题，尽管大小取决于特定问题的属性。

问. GLPK 与其他 LP 代码相比如何？

答. 我认为在非常大规模的实例中，CPLEX 8.0 对偶单纯形比 GLPK 单纯形求解器快 10-100 倍，当然也更健壮。在许多情况下，对于纯 LP 以及 MIP，GLPK 比 lp_solve 4.0 更快、更健壮。请参阅 GLPK 分发 doc 目录中的 bench.txt 文件，以了解 GLPK netlib 基准测试结果。

您可以在汉斯·米特尔曼的网页上找到一些 LP 和 MIP 求解器的基准测试，例如 CPLEX、GLPK、lp_solve 和 OSL <http://plato.asu.edu/bench.html>。

问. AMPL 和 GNU MathProg 之间有什么区别？

答. 在 MathProg 中实现的 AMPL 子集大约对应于 1990 年的 AMPL 状态，因为它主要基于罗伯特·福雷、大卫·M·盖伊和布莱恩·W·科尼汉 (1990) 的论文“数学规划的建模语言”，管理科学，第 36 卷，第 519-554 页，可以在 <http://users.iems.nwu.edu/~4er/WRITINGS/amplmod.pdf> 找到。

GNU MathProg 翻译器是作为 GLPK 的一部分开发的。但是，GNU MathProg 可以轻松地用于其他应用程序，因为有一组专为在其他应用程序中使用而设计的 MathProg 接口例程。

问. GLPK 支持哪些输入文件格式？

答. GLPK 目前可以以三种支持的格式读取输入和输出 LP 模型文件

• MPS 格式 - 这是一种面向列的、广泛支持的文件格式，但人类可读性差。
• CPLEX 格式 - 这是一种易于阅读的面向行的格式。
• GNU MathProg - 这是一种类似 AMPL 的数学建模语言。

问. GLPK 提供了哪些接口？

A. GLPK 软件包实际上是一个 C 语言 API，可以静态或动态链接到许多编程系统中。

目前，GLPK 软件包中包含三个贡献的外部接口

• GLPK Java 本地接口 (JNI)
• GLPK Delphi 接口 (DELI)
• GLPKMEX Matlab MEX 接口

在 <http://gottfried.lindner.bei.t-online.de/glpk.htm> 中提供了一个非官方的 Microsoft Visual Basic、Tcl/Tk 和 Java GLPK 接口。

在 CVXOPT 中提供了一个 Python 接口，用于 GLPK 的 LP 求解器，请参阅 <http://abel.ee.ucla.edu/cvxopt/>。

目前正在开发其他语言接口，包括 FAQ 维护者 Harley Mackenzie 博士 <[email protected]> 正在开发的 Perl 接口。

Q. 在哪里可以找到一些示例？

A. GLPK 软件包发行版包含许多示例，这些示例是用 GNU MathProg (*.mod)、C API 调用 (*.c)、CPLEX 输入文件格式 (*.lpt)、MPS 格式 (*.mps) 以及一些特定旅行商示例 (*.tsp) 编写的。

所有示例都可以在 GLPK 发行版示例子目录中找到。

Q. GLPK 的未来计划是什么？

A. GLPK 的计划开发包括改进现有的关键 GLPK 组件，例如开发更健壮、更高效的单纯形和内点求解器的实现。计划中的未来 GLPK 增强功能包括实现分支定界求解器、MIP 预处理器、后最优和敏感性分析，以及可能的网络单纯形和二次规划求解器。

Q. 如何报告 GLPK 错误？

A. 如果你认为在 GLPK 中发现了错误，那么你应该向 <[email protected]> 发送尽可能完整的报告。

Q. 如何为 GLPK 开发做出贡献？

A. 目前，新的 GLPK 开发补丁应通过电子邮件发送给 Andrew Makhorin <[email protected] >，并附有足够的文档和测试代码，以解释补丁的性质、如何安装它及其使用带来的影响。在开始进行任何主要 GLPK 开发以纳入 GLPK 发行版之前，最好在 GLPK 邮件列表上讨论这个想法。

Q. 如何在 UNIX 平台上编译和链接 GLPK 应用程序？

A. 为了在 UNIX 平台上编译 GLPK 应用程序，编译器必须能够包含 GLPK 包含文件并链接到 GLPK 库。例如，在 GLPK 系统安装的系统上

 gcc mylp.c -o mylp -lglpk 

或者如果 GLPK 未安装，则显式指定包含文件和 libglpk.a。

Q. 如何在 Win32 平台上编译和链接 GLPK 应用程序？

A. 在 Win32 平台上，GLPK 作为 Win32 动态链接库 (DLL) 实现，或者可以静态链接到 glpk*.lib 文件。与 UNIX 指示一样，GLPK 应用程序必须设置指向 GLPK 包含文件的路径，如果静态链接，还需要引用 GLPK 库。

Q. 如何限制 GLPK 执行时间？

A. 你可以通过 API 例程 lpx_set_real_parm 设置控制参数 LPX_K_TMLIM 来限制计算时间。目前，没有办法限制 glpsol 的执行时间，除非更改源代码并重新编译特定版本。

GLPK 线性规划

Q. 什么是线性规划，它是如何工作的？

A. 线性规划是一种数学技术，它是一种解决具有线性项的某些方程组的通用方法。LP 的真正威力在于它们有许多实际应用，并已被证明是一种强大而健壮的工具。

关于 LP 的最佳单一信息来源是线性规划 FAQ <http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html>，其中包含有关 LP 和 MIP 的信息，包括可用的 LP 软件的综合列表，以及许多供进一步研究的 LP 参考资料。

Q. 如何确定 LP 解的稳定性？

A. 你可以通过为 glpsol 指定 --bounds 选项来执行敏感性分析，如

 glpsol ... --bounds filename 

在这种情况下，求解器会将分析结果以纯文本格式写入指定的文件名。相应的 API 例程是 lpx_print_sens_bnds() 。

Q. 如何确定哪些约束导致不可行？

A. 找到这样一组约束的一个简单方法是逐个删除约束。如果删除约束会导致可解问题，则将其拾取并继续进行下一个约束。在将阶段 1 应用于不可行问题后，所有基本的满足约束都可以删除。

如果问题具有可行的对偶，那么运行对偶单纯形方法是一种更直接的方法。在最后一次旋转之后，非基本约束和一个违反的约束将构成一个最小集合。GLPK 单纯形表例程将允许你从违反的约束中选择一个正确的约束。

请注意，需要关闭 GLPK 预处理器才能使上述技术起作用，否则 GLPK 不会保留不可行解的基础。

此外，在邮件列表存档中发布了更详细的方法，位于 <http://mail.gnu.org/archive/html/help-glpk/2003-09/msg00017.html>。

Q. 检查和约束有什么区别？

A. 检查语句旨在检查用户在模型中指定的所有数据是否正确，主要是在 MathProg 模型的数据部分。例如，如果某个参数表示网络中的节点数，则它必须是正整数，这只是在检查语句中检查的条件（尽管在这种情况下，可以在参数语句中直接检查此条件）。请注意，检查语句是在翻译器生成模型时执行的，因此它们不能包含变量。

约束是根据变量表达的条件，并在模型完全生成后由求解器解决。如果模型中指定的所有数据都事先正确，则不需要检查语句，可以省略，而约束是模型的重要组成部分，因此不能省略。

GLPK 整数规划

Q. 什么是整数规划，它是如何工作的？

A. 整数 LP 模型是指其变量被约束为取整数或整数（而不是分数）值的模型。整数规划比普通线性规划困难得多，这可能并不明显，但实际上确实如此，无论是在理论上还是在实践中。

Q. 什么是整数优化套件 (IOS)？

A. IOS 是一个框架，用于实现基于 LP 松弛的隐式枚举方法（如分支定界和分支剪枝）。目前 IOS 只包含基本功能（枚举树、API 例程和驱动程序），并没有完整记录。

Q. 我刚把一个 LP 更改为 MIP，现在它不起作用了？

A. 如果你有一个正在运行的 LP，你将其更改为 MIP 并收到“lpx_integer: optimal solution of LP relaxation required” 204 (==LPX_E_FAULT) 错误，你可能在 lpx_integer() 之前没有调用 LP 求解方法 lpx_simplex() 。MIP 例程使用 LP 解作为 MIP 解方法的一部分。

注意：此答案已过时 —lpx_simplex()和lpx_integer()已被弃用，请尝试glp_iotopt()代替。

Q. 什么是切割，它们是如何工作的？

A. 假设你有一个 MIP 实例。删除整型约束会得到 MIP 的 LP 松弛。LP 松弛的可行集是一个多面体 P，其顶点对应于基本解，这些解可能是非整型的（因为整型约束被删除）。现在假设你构建了 MIP 可行集的凸包 T。它也是一个多面体（称为 MIP 多面体）；根据定义，每个顶点都对应于一个基本解，该解是整型的。显然，T 是 P 的子集。请注意，T 的描述，即定义它的线性不等式组，通常是未知的。如果你找到了 LP 松弛的最优解，即 P 的最优顶点，假设为 x，并且 x 不是整型，则必须存在一个称为切割平面的超平面或切割，它将 x 从 T 中切除（分离）。如果你找到了某个切割 ax >= b，你可以将此不等式（称为有效不等式）添加到原始 MIP 中；请注意，如果一个不等式是有效的，则每个整型解都满足它，即它保留 T。理想情况下，切割应该是 T 的一个面，然而，对于许多 MIP 类，很难找到这种面诱导的有效不等式。

历史上，第一类切割平面是由 Ralph Gomory 提出的。分支剪枝方法是分支定界方法，其中子问题用切割平面加强，这使得可以减小搜索树的大小。在互联网上，你可以找到大量关于分支剪枝方法的报告、论文和书籍。

GLPK 数据库访问

Q. 是否可以通过 ODBC 从 Access DB 中读取一个简单的标量参数？

A. 标量参数在表语句中不允许使用。但是，你可以定义一个标量参数数组，例如

  set N; /* parameter names */
  param p{N}; /* parameter values */

从表中读取 S 和 p{S}，然后在模型中使用 p["test"]。