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 基