GLPK/第三方 API 包装器

此页面描述了与原生 GLPK API 集 接口的“包装器”类，以提供额外的功能。此页面主要针对开发大型应用程序的程序员。

GLPK API 在很多方面都是比较底层的，而且不太智能（但它们正在改进）。尤其是 C++ 开发人员，有时会编写包装器类来在 GLPK 和他们的客户端代码之间进行接口。他们的动机通常源于对以下一项或两项功能的需求：

• 提供更高层、更定制、更智能的 客户端调用集
• 能够在不影响客户端代码的情况下 切换求解器 - 就像需要重新链接但 不需要 重新编译一样。

在这个背景下，智能包括能够在内部维护行和列计数、识别不完整模型、选择特定求解器调用、优雅地失败以及其他相关的自适应行为。

以上两方面的实现都需要设计权衡，这意味着 API 包装器在某种程度上往往是针对特定情况的。例如，为了保持共性，切换求解器的能力可能需要排除专门的求解器功能。

COIN-OR 开放求解器接口 (Osi)

求解器切换的关键举措是 COIN-OR Osi 项目。

GLPK 通过派生的包装器类获得支持OsiGlpk. 测试环境包括（没有提到 Mac OS X）

• Windows 使用 Microsoft Visual C++ V6 和 V7
• Windows 使用 Cygwin 工具链
• Linux 使用 g++ 2.95.2 及更高版本。

鉴于 GLPK 正在进行的 更新 其 API 集的计划，OsiGlpk代码目前依赖于已弃用的 API（截至 2010 年 12 月，一个寻求对齐的 2008 年票据仍然开放 ）。对于 LP 问题这可能不是问题，但对于分支定界切割方法来说可能是个问题。建议开发人员在继续之前确认（可能需要修改）此接口类。COIN-OR Osi 仍在持续开发中。

Osi 代码库更改在 projects.coin-or.org/Osi/changeset 中进行跟踪。

通用线性优化包 (Glop)

Glop，通用线性优化包，是一个库包，它提供函数来在 C 或 C++ 程序中创建、操作和求解线性规划 (LP)。Glop 主要是一个包装器库，允许用户通过同一个 API 访问不同的现有 LP 求解器。Glop 支持 GLPK，由 Francois Galea 编写。

LEMON 图形库

LEMON 是用于网络中高效建模和优化的库。 这是一个 C++ 模板库，提供了各种数据结构和算法，用于“主要与图形相关的组合优化任务”。GLPK 是 LEMON 支持的众多求解器之一。

LEMON 项目由匈牙利布达佩斯罗兰大学运筹学系埃格瓦里组合优化研究小组 (EGRES) 于 2003 年启动。LEMON 是 COIN-OR 倡议的成员，该倡议是一组与运筹学相关的开源项目。LEMON 在 Boost 软件许可证版本 1.0 下分发，这是一个允许商业和非商业用途的宽松许可证。Boost 许可证与 GPL 兼容。该项目维护着一个包含用户文档、源代码浏览和错误跟踪的网站。它还运营着几个邮件列表。

IAJAAR.H 项目

IAJAAR.H 是一个小型项目，它为程序员提供了一个名为IAJAAR的专用三元组 (3 元组) 容器类。该项目在 本地 进行了更详细的描述。

使用 C++ 向量

一些用户可能更喜欢使用来自 C++ 标准库 的向量，而不是 C 样式数组。

例如，标准 GLPK 教程问题 可以重新编码如下

// system headers
...
#include <vector>             // STL sequence container

// declare variables
glp_prob *lp;
std::vector<int>    iav;
std::vector<int>    jav;
std::vector<double> arv;
iav.reserve(1001);            // was: int ia[1+1000]
jav.reserve(1001);            // was: int ja[1+1000]
arv.reserve(1001);            // was: double ar[1+1000]
double Z, x1, x2, x3;
int solver_ret;               // exit status of solver
// create problem
lp = glp_create_prob();
glp_set_prob_name(lp, "example using std::vector");
glp_set_obj_dir(lp, GLP_MAX);
// fill problem
glp_add_rows(lp, 3);
...
glp_load_matrix(lp, 9, &iav[0], &jav[0], &arv[0]);  // was: glp_load_matrix(lp, 9, ia, ja, ar)
solver_ret = glp_simplex(lp, NULL);
...

这样做的原因是 C++ 标准要求 std::vector 保存在连续的内存中。为此，Josuttis (1999 p155) 这样写道：

"这个例子表明，无论出于何种原因（例如用于现有的 C 库）需要类型为 T 的数组，都可以使用 std::vector<T> 并将第一个元素的地址传递给它"

如果您尝试读取或写入超出范围的数据，这种习惯用法会像 C 样式数组一样肯定会失败 - 但它会抛出一个带有更易于理解的错误消息的 C++ 异常。如果您愿意，甚至可以捕获异常，然后更优雅地退出。例如

glp_prob *lp;
try
  {
    // most of the above code in here
  }
catch(const std::out_of_range& e)
  {
    std::cout << "e.what()" << std::endl;
    // any mopping up
  }
glp_delete_prob(lp);
glp_free_env();

不要在以后尝试在向量中预留更多容量 - 重新分配会自动使所有引用、指针和迭代器失效！

如果在 C++11 标准下编程，可以使用初始化列表（以保存所有 std::vector::push_back 调用）

// load the structural matrix data using initialization lists
std::vector<int>    iat = {  1,   1,   2,   2};
std::vector<int>    jat = {  1,   2,   1,   2};
std::vector<double> art = {1.0, 2.0, 3.0, 1.0};

// now prepend the required position zero placeholder (any value will do but zero is safe)
// first create length one vectors using default member construction
std::vector<int>    iav(1);
std::vector<int>    jav(1);
std::vector<double> arv(1);

// then concatenate these with the original data vectors
iav.insert(iav.end(), iat.begin(), iat.end());
jav.insert(jav.end(), jat.begin(), jat.end());
arv.insert(arv.end(), art.begin(), art.end());

// then load the structural matrix data
glp_load_matrix(lp, 9, &iav[0], &jav[0], &arv[0]);  // was: glp_load_matrix(lp, 9, ia, ja, ar)

需要使用 std::vector::insert 调用，因为 GLPK 从一开始就进行索引，而 C++ 从零开始索引。还要注意，std::deque 容器 不 保证连续使用内存。