GLPK/使用 GLPK 可调用库

此页面描述了将 GLPK 作为可调用库使用时相关的问题。因此，此页面主要面向使用 C 或 C++ 编写应用程序并使用 GLPK 应用程序编程接口 (API) 的开发人员。

官方文档

该GLPK 官方文档文件doc/glpk.pdf包含 GLPK API 的完整参考。因此，此处不再重复这些内容。请参阅获取 GLPK。

简短示例

以下 API 示例实现了线性约束优化模型

最大化	$0.6x_{1}+0.5x_{2}$
受制于	$x_{1}+2x_{2}\leq 1$
	$3x_{1}+x_{2}\leq 2$

/* short.c */

#include <stdio.h>            /* C input/output                       */
#include <stdlib.h>           /* C standard library                   */
#include <glpk.h>             /* GNU GLPK linear/mixed integer solver */

int main(void)
{
  /* declare variables */
  glp_prob *lp;
  int ia[1+1000], ja[1+1000];
  double ar[1+1000], z, x1, x2;
  /* create problem */
  lp = glp_create_prob();
  glp_set_prob_name(lp, "short");
  glp_set_obj_dir(lp, GLP_MAX);
  /* fill problem */
  glp_add_rows(lp, 2);
  glp_set_row_name(lp, 1, "p");
  glp_set_row_bnds(lp, 1, GLP_UP, 0.0, 1.0);
  glp_set_row_name(lp, 2, "q");
  glp_set_row_bnds(lp, 2, GLP_UP, 0.0, 2.0);
  glp_add_cols(lp, 2);
  glp_set_col_name(lp, 1, "x1");
  glp_set_col_bnds(lp, 1, GLP_LO, 0.0, 0.0);
  glp_set_obj_coef(lp, 1, 0.6);
  glp_set_col_name(lp, 2, "x2");
  glp_set_col_bnds(lp, 2, GLP_LO, 0.0, 0.0);
  glp_set_obj_coef(lp, 2, 0.5);
  ia[1] = 1, ja[1] = 1, ar[1] = 1.0; /* a[1,1] = 1 */
  ia[2] = 1, ja[2] = 2, ar[2] = 2.0; /* a[1,2] = 2 */
  ia[3] = 2, ja[3] = 1, ar[3] = 3.0; /* a[2,1] = 3 */
  ia[4] = 2, ja[4] = 2, ar[4] = 1.0; /* a[2,2] = 1 */
  glp_load_matrix(lp, 4, ia, ja, ar);
  /* solve problem */
  glp_simplex(lp, NULL);
  /* recover and display results */
  z = glp_get_obj_val(lp);
  x1 = glp_get_col_prim(lp, 1);
  x2 = glp_get_col_prim(lp, 2);
  printf("z = %g; x1 = %g; x2 = %g\n", z, x1, x2);
  /* housekeeping */
  glp_delete_prob(lp);
  glp_free_env();
  return 0;
}

当然，生产代码会检查函数的返回值glp_simplex并做出相应的反应。

Linux

这些说明与 Linux 相关（其他操作系统的详细信息应该类似）。

构建简短使用您的系统编译器，在本例中为 GNU GCC

$ gcc -Wall short.c -lglpk -o short

运行生成的二进制文件

$ ./short 
*     0: obj =   0.000000000e+00  infeas =  0.000e+00 (0)
*     2: obj =   4.600000000e-01  infeas =  0.000e+00 (0)
OPTIMAL SOLUTION FOUND
z = 0.46; x1 = 0.6; x2 = 0.2

您应该获得$x_{1}=0.6$和$x_{2}=0.2$作为程序终端输出的一部分。

GLPK 运行时报告格式（以 * 开头的行）在GLPK 官方文档的可调用库部分以及此处进行了介绍。

同一个问题在MathProg中进行了编码。

提交补丁

GLPK 补丁最好通过将它们发布到两个GLPK 邮件列表中最合适的一个来提交。请注意，GLPK 项目不维护基于 Web 的源代码存储库。

如果创建源文件补丁，请避免使用制表符并将行长限制为 72 个字符。

线程安全

GLPK本身不是线程安全的。有关在并发执行下使用 GLPK API 的更多信息，请咨询 GLPK 新闻组档案。特别是，请参阅此讨论，以及稍后的此讨论。

如果您的问题涉及多个 LP（或可以这样构建），则可以考虑将每个 LP 作为单独的进程运行。这仅对多核硬件有意义。

可重入性

Andrew表示，可重入性是代码的一个属性，它允许使用内存中程序的唯一副本并行运行同一程序的多个实例。此属性要求程序不更改其自身代码和静态分配的数据。另请参阅 Wikipedia 对可重入性的定义。

glpk 代码是可重入的，除了两个内部例程 tls_set_ptr 和 tls_get_ptr（请参阅 src/env/tls.c）。在 glpk 的可重入版本中，这两个例程应替换为特定于平台的例程。

当前版本的 tls.c 不是可重入的

static void *tls = NULL;

void tls_set_ptr(void *ptr)
{     tls = ptr;
      return;
}

void *tls_get_ptr(void)
{     void *ptr;
      ptr = tls;
      return ptr;
}

Andrew建议使用可重入版本

#include <pthread.h>
pthread_key_t _glp_pth_key;
/* must be initialized in the main program */

void tls_set_ptr(void *ptr)
{     pthread_setspecific(_glp_pth_key, ptr);
      return;
}

void *tls_get_ptr(void)
{     void *ptr;
      ptr = pthread_getspecific(_glp_pth_key);
      return ptr;
}

最新的 GCC 编译器具有存储类关键字__thread

static __thread void *tls = NULL;

void tls_set_ptr(void *ptr)
{     tls = ptr;
}

void *tls_get_ptr(void)
{     return tls;
}

Visual Studio 2005 编译器具有类似的存储类修饰符__declspec( thread )

static __declspec( thread ) void *tls = NULL;

void tls_set_ptr(void *ptr)
{     tls = ptr;
}

void *tls_get_ptr(void)
{     return tls;
}

此提交使库在 Windows 和 Linux 上可重入。

已弃用的 GLPK API

一些 GLPK API 最近已被弃用并替换。除非另有说明，否则lpx_前缀已被替换为glp_前缀。在所有情况下，开发人员都应仔细检查官方文档。

从 4.49 版开始，开发人员必须迁移到这些新的 API。旧的 API 例程（其名称以lpx_开头）现已从 GLPK API 中删除，不再可用。

GLPK	已弃用	注释
4.16	lpx_add_cols
	lpx_add_rows
	lpx_create_index
	lpx_create_prob
	lpx_del_cols
	lpx_del_rows
	lpx_delete_index
	lpx_delete_prob
	lpx_find_col
	lpx_find_row
	lpx_get_col_dual
	lpx_get_col_kind
	lpx_get_col_lb
	lpx_get_col_name
	lpx_get_col_prim
	lpx_get_col_stat
	lpx_get_col_type
	lpx_get_col_ub
	lpx_get_mat_col
	lpx_get_mat_row
	lpx_get_num_bin
	lpx_get_num_cols
	lpx_get_num_int
	lpx_get_num_nz
	lpx_get_num_rows
	lpx_get_obj_coef
	lpx_get_obj_dir
	lpx_get_obj_name
	lpx_get_obj_val
	lpx_get_prob_name
	lpx_get_row_dual
	lpx_get_row_lb
	lpx_get_row_name
	lpx_get_row_prim
	lpx_get_row_stat
	lpx_get_row_type
	lpx_get_row_ub
	lpx_ipt_col_dual
	lpx_ipt_col_prim
	lpx_ipt_obj_val
	lpx_ipt_row_dual
	lpx_ipt_row_prim
	lpx_load_matrix
	lpx_mip_col_val
	lpx_mip_obj_val
	lpx_mip_row_val
	lpx_set_col_bnds
	lpx_set_col_kind
	lpx_set_col_name
	lpx_set_col_stat
	lpx_set_mat_col
	lpx_set_mat_row
	lpx_set_obj_coef
	lpx_set_obj_dir
	lpx_set_obj_name
	lpx_set_prob_name
	lpx_set_row_bnds
	lpx_set_row_name
	lpx_set_row_stat
4.18	lpx_simplex
4.20	lpx_integer	参见：glp_iotopt
4.29	lpx_read_mps
	lpx_read_freemps
	lpx_write_mps
	lpx_write_freemps
	lpx_read_cpxlp
	lpx_write_cpxlp
4.31	lpx_scale_prob
	lpx_std_basis
	lpx_adv_basis
	lpx_cpx_basis
4.32	lpx_integer
	lpx_intopt
4.33	lpx_exact
	lpx_get_ray_info	参见glp_unbnd_ray
	lpx_interior
	lpx_read_model
4.37	lpx_print_sol
	lpx_print_ips	参见lpx_print_ipt
	lpx_print_mip
	lpx_print_prob	参见glp_print_lp
4.41	lpx_transform_row
	lpx_transform_col
	lpx_prim_ratio_test
	lpx_dual_ratio_test
4.42	lpx_print_sens_bnds	参见glp_print_ranges
4.49	lpx_check_kkt	参见glp_check_kkt

近期新增的 GLPK API

GLPK 不断添加新的 API。以下列出了这些 API。如果合适，新的 API 也可能在相同或后续版本中通过相关的 GLPSOL 命令行选项公开。

注意：此信息仅追溯到 2007 年 2 月发布的 4.31 版。

GLPK	添加	注释
4.49	glp_check_kkt	替换lpx_check_kkt
	glp_mincost_relax4	使用 RELAX-IV 代码求解最小成本流问题
4.47	glp_intfeas1	使用 GLPK 代码求解 CNF-SAT 问题实例（暂定）
4.46	glp_read_cnfsat	以 DIMACS 格式读取 CNF-SAT 问题数据
	glp_write_cnfsat	以 DIMACS 格式写入 CNF-SAT 问题数据
	glp_check_cnfsat	检查 CNF-SAT 问题实例
	glp_minisat1	使用 MiniSat 求解 CNF-SAT 问题实例
4.44	glp_cpp	求解关键路径问题
4.42	glp_check_dup	检查稀疏矩阵中是否存在重复元素
	glp_sort_matrix	对约束矩阵的元素进行排序
	glp_read_prob	读取 GLPK 格式的问题数据
	glp_write_prob	写入 GLPK 格式的问题数据
	glp_analyze_bound	分析非基变量的活动界
	glp_analyze_coef	分析基变量的目标系数
	glp_print_ranges	打印灵敏度分析报告
4.41	glp_transform_row	转换显式指定的行
	glp_transform_col	转换显式指定的列
	glp_prim_rtest	执行原始比率检验
	glp_dual_rtest	执行对偶比率检验
4.40	glp_del_vertices	从图中移除顶点
	glp_del_arc	从图中移除弧
	glp_wclique_exact	使用 P Ostergard 教授开发的精确算法查找最大权重团
	glp_read_ccdata	以 DIMACS 团/着色格式读取图
	glp_write_ccdata	以 DIMACS 团/着色格式写入图
4.39	glp_warm_up	“预热” LP 基
	glp_set_vertex_name	分配（更改）顶点名称
	glp_create_v_index	创建顶点名称索引
	glp_find_vertex	按名称查找顶点
	glp_delete_v_index	删除顶点名称索引
	glp_read_asnprob	以 DIMACS 格式读取分配问题数据
	glp_write_asnprob	以 DIMACS 格式写入分配问题数据
	glp_check_asnprob	检查分配问题数据的正确性
	glp_asnprob_lp	将分配问题转换为 LP
	glp_asnprob_okalg	使用失衡算法求解分配问题
	glp_asnprob_hall	使用霍尔算法查找最大基数的二分匹配
4.37	glp_print_sol	以可打印格式写入基本解
	glp_print_ipt	以可打印格式写入内点解
	glp_print_mip	以可打印格式写入 MIP 解
	glp_read_graph	从纯文本文件读取（有向）图
	glp_write_graph	将（有向）图写入纯文本文件
	glp_weak_comp	查找所有弱连通分量
	glp_strong_comp	查找所有强连通分量
4.36	glp_mincost_okalg	使用失衡算法查找最小成本流
	glp_maxflow_ffalg	使用福特-福克森算法查找最大流
4.35	glp_create_graph	创建图
	glp_set_graph_name	分配（更改）图名称
	glp_add_vertices	向图中添加新顶点
	glp_add_arc	向图中添加新弧
	glp_erase_graph	擦除图内容
	glp_delete_graph	删除图
	glp_read_mincost	以 DIMACS 格式读取最小成本流问题数据
	glp_write_mincost	以 DIMACS 格式写入最小成本流问题数据
	glp_mincost_lp	将最小成本流问题转换为 LP
	glp_netgen	Klingman 的网络问题生成器
	glp_gridgen	网格状网络问题生成器
	glp_read_maxflow	以 DIMACS 格式读取最大流问题数据
	glp_write_maxflow	以 DIMACS 格式写入最大流问题数据
	glp_maxflow_lp	将最大流问题转换为 LP
	glp_rmfgen	Goldfarb 的最大流问题生成器
4.33	glp_copy_prob	复制问题对象内容
	glp_exact	以精确算术求解 LP（使 lpx_exact 已弃用）
	glp_get_unbnd_ray	确定导致无界性的变量（使 lpx_get_ray_info 已弃用）
	glp_interior	使用内点法求解 LP（使 lpx_interior 已弃用）
4.32	glp_ios_row_attr	确定其他行属性
	glp_ios_pool_size	确定割池的当前大小
	glp_ios_add_row	向割池添加约束
	glp_ios_del_row	从割池中删除约束
	glp_ios_clear_pool	从割池中删除所有约束
4.31	glp_scale_prob	问题数据的自动缩放
	glp_std_basis	构建标准的初始 LP 基
	glp_adv_basis	构建高级的初始 LP 基
	glp_cpx_basis	构建 Bixby 的初始 LP 基