GLPK/解决方案信息

本页面解释了如何从 GLPK 中恢复和解释解决方案信息。此处提供的信息应与使用 GLPSOL 的建模者和使用可调用库 API 的程序员相关。

在使用本页面的内容之前，您必须尝试求解您的问题，但 GLPK 的求解过程不一定产生了可用的答案。无论是否有答案，都有很多原因需要寻求有关求解过程和/或解决方案的额外信息。

运行时报告

GLPK 通常会在求解过程中打印信息，可以在终端输出页面上找到详细信息。

无法求解到最优

GLPK 可能无法找到最优解的原因有很多（除了软件错误），

问题为空，求解器返回
求解器证明该问题是无界的，并返回
求解器证明该问题是不可行的，并返回
求解器无法在分配的时间或可用内存内找到初始可行解
求解器无法在分配的时间或可用内存内找到最优解
求解器遇到数值不稳定问题

并非所有这些情况都与{ 单纯形，内点 } × { LP，MIP } 组合中的每一个相关，但这确实给出了可能出现的各种问题的概况。故障排除页面提供了一些建议和解决方案。特别是数值不稳定警告可能是由于缩放不当导致的。如果您遇到一个非常令人费解的问题，并且认为是 GLPK 中的错误，请报告该问题，以便对其进行处理。

如果使用 GLPK 进行编程，请记住，求解器可能（也许是矛盾的）不一定找到了解决方案来返回成功 - 它只需要以令人满意的方式完成其分配的任务。

解决方案恢复

假设 GLPK 提供了最优解，可以使用标准调用和定制方法来恢复解决方案信息，这有几种方法。某些技术也可以接受和处理非最优可行解。

MathProg 语言允许严格控制解决方案信息的输出。该语言现在支持针对约束和变量（但不是参数）的后缀 - 这在搜索例如对偶值时非常有用。关于接近零值的部分展示了如何使用 MathProg 条件来输出真正的零值而不是非常小的数字。

GLPSOL 提供了选项--output和--write分别用于获得人类可读和机器可解析格式的解决方案信息。两者都可以在一个命令中使用

glpsol ... --output file.out --write file.wri

这两个输出格式在互操作性页面上展示。终端输出也可以使用 GLPSOL 命令行选项复制到文本文件--log file.log. 反过来，特殊文件名/dev/stdout可用于将“文件”写入终端而不是写入常规文件。这两种策略可以一起使用。

由glp_print_sol产生的输出类似于 IBM MPS/360 线性规划软件包中使用的输出，但略有修改，因为 GLPK 使用辅助变量而不是松弛/盈余变量。 ^[1]

可以用来恢复信息的各种 GLPK API 调用列在下方。在其他地方，给出了相关的函数名称，以帮助交叉引用回 GLPK API 手册，在该手册中通常可以找到全面的技术描述。

敏感性分析报告

用单纯形求解器求解到最优的问题可以进一步进行敏感性分析。此功能不适用于内点求解器生成的解决方案或混合整数问题。该glp_print_rangesAPI 调用以人类可读的格式生成敏感性报告。

GLPSOL 的--ranges选项也生成此报告（或如果其使用不当，则发出适当的警告）

glpsol ... --ranges file.sen

由glp_print_ranges与 IBM MPS/360 线性规划软件包中使用的报告相同（参见 Murtagh 1981）。

此处的描述故意简短 - 详细信息可以在官方 GLPK API 手册中找到，包括对断点和目标系数敏感性的解释。以下两个表格可以用于阅读敏感性分析报告。

行
标题	值	注释
`编号`		行的序号， 1 … n
`行名`		符号名称（如果没有则为空白）
`St`		行状态

	`BS`	约束不活动
	`NL`	RHS 较低的非等式约束活动
	`NU`	RHS 较高的非等式约束活动
	`NS`	等式约束活动
	`NF`	自由行活动
`活动`		（主）辅助变量的值
`松弛`		（主）松弛变量的值
`边际`		辅助变量的简化成本（对偶活动）
`下限`		RHS 的下限（`-Inf`如果打开）
`上限`		RHS 的上限（`+Inf`如果打开）
`目标系数范围`		与行相关的目标系数范围
`目标值`		目标值
`限制变量`		限制变量的名称

列
标题	值	注释
`编号`		列的序号， 1 … m
`列名`		符号名称（如果没有则为空白）
`St`		列状态

	`BS`	基本列
	`NL`	下限活动的非基本列
	`NU`	上限活动的非基本列
	`NS`	非基本固定列
	`NF`	非基本自由（无界）列
`活动`		（主）结构变量的值
`目标系数`		结构变量的目标系数
`边际`		结构变量的简化成本（对偶活动）
`下限`		结构变量的下限（`-Inf`如果打开）
`上限`		结构变量的上限（`+Inf`如果打开）
`目标值`		目标值
`限制变量`		限制变量的名称

缩写：RHS 表示右手边。Inf 表示无穷大。

官方文档（GLPK 4.45）解释说，对行的分析是对其辅助变量的分析，该变量等于行线性形式 $\sum a_{j}x_{j}$ 。对列的分析是对其对应结构变量的分析。从形式上讲，在执行敏感性分析时，行和列之间没有内在的区别。

Karush-Kuhn-Tucker 最优条件

对于纯线性规划（不包括混合整数规划），Karush-Kuhn-Tucker 最优性条件对于给定解成为全局最优解是必要且充分的（假设一些正则性条件也满足）。这些 KKT 条件在此列出，因为它们适用于 GLPK。数值求解器也使用这些 KKT 条件来估计其浮点计算完成后的精度。GLPK 可以根据要求提供一个人类可读的报告，其中包含 KKT 条件，以及使用单纯形或内点求解器获得的任何解。

KKT 计算

GLPK 提供了lpx_check_kkt例程来计算和解释当前基本解的 KKT 最优性条件。此调用填充一个 C 结构LPXKKT实例，从中可以恢复特定信息。它的使用在官方 GLPK API 手册中进行了说明，并且调用本身也在本维基百科中进行了描述。

KKT 报告

GLPKglp_print_sol和glp_print_ipt调用打印一个包含解和该解的 KKT 最优性条件的报告。GLPSOL--output选项也显示了纯 LP（非 MIP）问题的相同信息（用法不受限制）。

glpsol ... --output file.out

KKT 条件最常用于估计不精确浮点运算对报告解的质量的影响（假设没有使用精确运算）。此处给出的描述有意简短——有关详细信息，请参阅官方 GLPK API 手册。共有四个报告测试，标记为KKT.PE到KKT.DB。显示了一个典型的报告——在本例中是干净的！

KKT.PE: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

KKT.PB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

KKT.DE: max.abs.err = 0.00e+00 on column 0
        max.rel.err = 0.00e+00 on column 0
        High quality

KKT.DB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

以下三个表格可用于阅读 KKT 报告。第一个表格中给出的数学表达式在此处进行了详细描述。

要求	数学上	解释
`KKT.PE`	$A\mathbf {x} =b$	原始变量满足原始问题
`KKT.PB`	$\mathbf {x} \geq 0$	非基本变量满足边界约束
`KKT.DE`	$A^{\top }\pi +\lambda =c$	目标函数梯度是约束平面法向量的特定线性组合
`KKT.DB`	$\lambda \geq 0$	原始约束阻止解沿着目标函数梯度“移动”

属性	解释
`max.abs.err`	最大绝对误差
`max.rel.err`	最大相对误差

质量	字符	解释
`高质量`	`H`	高质量
`中等质量`	`M`	中等质量
`低质量`	`L`	低质量
各种报告	`?`	原始或对偶解错误或不可行

上面的char列指的是 GLPK 中包含的字符值LPXKKTC 结构体。

解释

对于给定问题，如果缩放有效，GLPK 4.45 API 手册指出，“如果所有指标都显示高质量或中等质量……用户可以确信获得的基本解相当准确。”

整数可行性报告

前两个 KKT 条件KKT.PE和KKT.PB也可以为混合整数规划的解计算，并用于调查所得解的数值精度。仅这两项测试不能保证最优性，但求解器将知道分支定界树是否已遍历完。有关详细信息，请参见前面的部分。

GLPKglp_print_mip调用打印一个包含解和该解的整数可行性条件的报告。GLPSOL--output选项可用于显示 MIP 问题的此信息（用法不受限制）。

glpsol ... --output file.out

还要注意 GLPSOL 选项--nomip，它允许通过删除整数限制来将 MIP 问题作为纯 LP 求解。

信息性 API

以下函数可用于直接收集信息（应优先于正则表达式文本文件）

API	注释
`glp_get_row_prim`	检索行原始值
`glp_get_row_dual`	检索行对偶值
`glp_get_row_stat`	检索行状态
`glp_get_row_lb`	检索行下界
`glp_get_row_ub`	检索行上界
`glp_get_col_prim`	检索列原始值
`glp_get_col_dual`	检索列对偶值
`glp_get_col_stat`	检索列状态
`glp_get_col_lb`	检索列下界
`glp_get_col_ub`	检索列上界
`glp_get_obj_coef`	检索目标系数或常数项
`lpx_check_kkt`	计算 KKT 最优性条件并填充`LPXKKT`C 结构体

以下函数应生成人类可读的报告

API	注释
`glp_print_ranges`	打印人类可读的灵敏度分析报告
`glp_print_sol`	打印人类可读的KKT 条件，以及单纯形 LP 解
`glp_print_ipt`	打印人类可读的KKT 条件，以及内点 LP 解
`glp_print_mip`	打印人类可读的整数可行性报告，以及 MIP 解

自适应使用

几个创新项目在自适应环境中使用 GLPK 解信息。一次运行的结果用于生成下一个模型，依此类推，直到达到某个预定的条件。

注意：需要更多详细信息。

参考资料

↑ Murtagh, Bruce A (1981). 高级线性规划：理论与实践. 纽约，美国：McGraw-Hill. ISBN 0-07-044095-6.

请求：如果有人开发了一些脚本用于解析人类可读的报告，他们可以将其添加到此页面或发布到[help-glpk]列表，以便在此处包含。

[1] Murtagh, Bruce A (1981). 高级线性规划：理论与实践. 纽约，美国：McGraw-Hill. ISBN 0-07-044095-6.

[1]