跳转到内容

GLPK/互操作性

Add links
来自 Wikibooks，开放世界中的开放书籍

在本例中，互操作性是指在 GLPK 下转换和/或使用常见的线性及混合整数问题规范格式的能力。这些格式用于表示和归档问题实例。问题格式的概念不应与高级建模语言（如 GLPK MathProg）混淆。本页还介绍了 GLPK 提供的解恢复格式，并提供有关机器处理 GLPK 输出的信息。

概述

[编辑 | 编辑源代码]

GLPK 可以轻松地输入和输出各种问题规范格式中的问题

  • CPLEX LP 格式（包括 MIP 问题）
  • MPS 格式，分为固定（旧）和自由（现代）两种变体
  • 自定义的DIMACS 类格式，名为GLPK 格式。

这意味着 GLPK 可以用来为其他求解器创建问题。并且可以从其他来源获取问题，并将它们重新格式化或解决。此功能可通过 GLPSOL 和 GLPK 可调用库实现。事实上，一些用户仅将 GLPK 用于其模型生成和问题重新格式化功能，而从未实际调用底层求解器。

GLPK 无法在底层格式规范提供此功能的情况下，将结果写回这些格式。用户必须依赖于本机 GLPK 解输出。GLPK 目前也不支持任何基于XML 的优化格式[1]，包括作为COIN-OR OS（优化服务）项目的一部分而开发的格式。

此外，GLPK 提供了几个图 读取和写入例程，它们使用 DIMACS 团/着色格式，以及自定义 GLPK 纯文本格式。这些 API 例程目前不可通过 GLPSOL 使用，并且不再讨论。

早期版本的 GLPK 支持 OPB 伪布尔格式。

以下文件扩展名约定通常适用

格式 文件扩展名 评论
CPLEX LP .lp
MPS .mps 固定和自由
GLPK .glp  .glpk

官方 GLPK 文档提供了对每个受支持格式的完整详细信息。

最后，本页包含一个敏感性分析示例，尽管它并不是真正的互操作性问题。敏感性分析解释键在glp_print_ranges 条目中给出。

GLPSOL 用法

[编辑 | 编辑源代码]

GLPSOL 提供了方便的命令行用法来实现互操作性。从 GLPSOL 的帮助消息开始是一个很好的起点。

下表总结了相关的互操作性选项（MathProg 列是为了完整性而包含的）：[2]

CPLEX LP MPS 固定 MPS 自由 GLPK MathProg
读取 --lp --mps --freemps --glp --math
写入 --wlp 文件名 --wmps 文件名 --wfreemps 文件名 --wglp 文件名 不可行

如上所示，通常无法从低级问题格式创建高级模型。也就是说，CPLEX LP 格式是最人性化的。

以下示例读取现有convert.lpCPLEX LP 格式文件，并输出一个 GLPK 格式文件，不求解模型。在本例中，--check选项阻止运行模型。

$ glpsol --check --wglp convert.glp --lp convert.lp

GLPSOL 用于解捕获的选项包括

可打印格式 纯文本格式
恢复 --output 文件名 --write 文件名

可打印格式旨在供人类理解。纯文本格式用于机器处理。两种格式均不代表已建立的标准。还可以使用--log选项将终端输出的副本写入文件。因此

$ glpsol --output example.out --log example.log --math example.mod

GLPSOL 提供的相同功能也可通过 GLPK 可调用库的 API 例程获得。

同样，官方 GLPK 文档提供了对每个格式的完整详细信息。

机器处理 GLPK 输出

[编辑 | 编辑源代码]

用户可能希望自动处理来自 GLPK 的输出。但是 GLPK 无法生成常见的机器可解析格式，如CSV（逗号分隔值）或XML 或基于这两种协议的专用方言。相反，GLPK 维护者建议

"要从计算机程序访问 GLPSOL 找到的解，可以将模型写入--wglp选项，将解写入--write选项。行和列的排序在两个文件中都是相同的。这足以获得所有必要的信息。（我想在这里做的唯一改进是使用 DIMACS 类格式来保存解文件。）" 来源：[help-glpk], 19 Jan 2011，语法已更正，强调部分已添加。

请参阅本页的其他位置，了解来自这两个 GLPSOL 选项的代表性输出。

相同的输出也可以使用适当的 API 调用生成，即glp_write_sol, glp_write_ipt, glp_write_mip和glp_write_prob.

简短示例

[编辑 | 编辑源代码]

本节使用short.mod模型，它首先在MathProg 页面上介绍。将以下模型保存到名为short.mod. 

# short example
var x1;
var x2;
maximize obj: 0.6 * x1 + 0.5 * x2;
s.t. c1: x1 + 2 * x2 <= 1;
s.t. c2: 3 * x1 + x2 <= 2;
solve;
display x1, x2;
end;

敏锐的读者可能注意到，此模型不包含高级 MathProg 语言功能，因此看起来很像问题格式（solve和display语句除外）。

接下来给出了一些调用和结果。此练习还提供了一个对这些各种格式的有用视觉比较。

CPLEX LP 格式

[编辑 | 编辑源代码]
$ glpsol --check --wlp short.lp --math short.mod 

\* Problem: short *\

Maximize
 obj: + 0.6 x1 + 0.5 x2

Subject To
 c1: + x1 + 2 x2 <= 1
 c2: + 3 x1 + x2 <= 2

Bounds
 x1 free
 x2 free

End

MPS 固定格式

[编辑 | 编辑源代码]
$ glpsol --check --wmps short.mps --math short.mod 

* Problem:    short
* Class:      LP
* Rows:       3
* Columns:    2
* Non-zeros:  6
* Format:     Fixed MPS
*
NAME          short
ROWS
 N  obj
 L  c1
 L  c2
COLUMNS
    x1        obj                0.6   c1                   1
    x1        c2                   3
    x2        obj                0.5   c1                   2
    x2        c2                   1
RHS
    RHS1      c1                   1   c2                   2
BOUNDS
 FR BND1      x1      
 FR BND1      x2      
ENDATA

MPS 自由格式

[编辑 | 编辑源代码]
$ glpsol --check --wfreemps short.mps --math short.mod 

* Problem:    short
* Class:      LP
* Rows:       3
* Columns:    2
* Non-zeros:  6
* Format:     Free MPS
*
NAME short
ROWS
 N obj
 L c1
 L c2
COLUMNS
 x1 obj 0.6 c1 1
 x1 c2 3
 x2 obj 0.5 c1 2
 x2 c2 1
RHS
 RHS1 c1 1 c2 2
BOUNDS
 FR BND1 x1
 FR BND1 x2
ENDATA

GLPK 格式

[编辑 | 编辑源代码]
$ glpsol --check --wglp short.glp --math short.mod 

p lp max 3 2 6
n p short
n z obj
i 1 f
n i 1 obj
i 2 u 1
n i 2 c1
i 3 u 2
n i 3 c2
j 1 f
n j 1 x1
j 2 f
n j 2 x2
a 0 1 0.6
a 0 2 0.5
a 1 1 0.6
a 1 2 0.5
a 2 1 1
a 2 2 2
a 3 1 3
a 3 2 1
e o f

GLPSOL 输出格式

[编辑 | 编辑源代码]

请在此处查看有关KKT 最优性条件的信息。

$ glpsol --output short.out --math short.mod

Problem:    short
Rows:       3
Columns:    2
Non-zeros:  6
Status:     OPTIMAL
Objective:  obj = 0.46 (MAXimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 obj          B           0.46                             
     2 c1           NU             1                           1          0.18 
     3 c2           NU             2                           2          0.14 

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x1           B            0.6                             
     2 x2           B            0.2                             

Karush-Kuhn-Tucker optimality conditions:

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

End of output

GLPSOL 写入格式

[编辑 | 编辑源代码]
$ glpsol --write short.sol --math short.mod

3 2
2 2 0.46
1 0.46 0
3 1 0.18
3 2 0.14
1 0.6 0
1 0.2 0

GLPSOL 敏感性分析

[编辑 | 编辑源代码]

有关表头的信息，请参见此处。

$ glpsol --ranges short.rng --math short.mod

GLPK 4.45 - SENSITIVITY ANALYSIS REPORT                                                                         Page   1

Problem:    short
Objective:  obj = 0.46 (MAXimum)

   No. Row name     St      Activity         Slack   Lower bound       Activity      Obj coef  Obj value at Limiting
                                          Marginal   Upper bound          range         range   break point variable
------ ------------ -- ------------- ------------- -------------  ------------- ------------- ------------- ------------
     1 obj          BS        .46000       -.46000          -Inf           -Inf      -1.00000        .      c1
                                            .               +Inf         .46000          +Inf          +Inf

     2 c1           NU       1.00000        .               -Inf           -Inf       -.18000          -Inf
                                            .18000       1.00000           +Inf          +Inf          +Inf

     3 c2           NU       2.00000        .               -Inf           -Inf       -.14000          -Inf
                                            .14000       2.00000           +Inf          +Inf          +Inf

GLPK 4.45 - SENSITIVITY ANALYSIS REPORT                                                                         Page   2

Problem:    short
Objective:  obj = 0.46 (MAXimum)

   No. Column name  St      Activity      Obj coef   Lower bound       Activity      Obj coef  Obj value at Limiting
                                          Marginal   Upper bound          range         range   break point variable
------ ------------ -- ------------- ------------- -------------  ------------- ------------- ------------- ------------
     1 x1           BS        .60000        .60000          -Inf           -Inf        .25000        .25000 c2
                                            .               +Inf           +Inf       1.50000       1.00000 c1

     2 x2           BS        .20000        .50000          -Inf           -Inf        .20000        .40000 c1
                                            .               +Inf           +Inf       1.20000        .60000 c2

End of report

参考资料

[编辑 | 编辑源代码]
  1. ↑ Fourer, Robert; Lopes, Leo; Martin, Kipp (2005), "LPFML：线性与整数规划的 W3C XML 模式", INFORMS 计算杂志, vol. 17, no. 2, pp. 139–158, doi:10.1287/ijoc.1040.0120
  2. ↑ 已过时的选项 --wcpxlp 等效于 --wlp。
取自 “https://wikibooks.cn/w/index.php?title=GLPK/Interoperability&oldid=3421278”
华夏公益教科书