こうして線形計画法を解けるようになりましたが、自分で書いたプログラムに組み込むことで、もっと柔軟な問題を解けるようになります。そのためにGLPKには色々な関数とヘッダファイルが用意されていて、これをリンクすることで簡単に線形計画法を用いるプログラムを書くことができます。
例として、GLPK上に上げた問題を解くCのプログラムを示します。
このプログラムではデータをstruct transfer_problemという構造体に格納するものとして、プログラム中央付近のmake_sample_data()で問題を作成しています。そしてこの(勝手に定義した)データをGLPKに渡して解いているのがsolve()です。 lpx_simplex(lp)までがデータのロード、その後は解いたデータの取り出しです。
このプログラムをコンパイルするには、以下のようなオプションをつけてください。
$ gcc -I (glpkのインストール先)/include (glpkのインストール先)/lib/libglpk.a -lm -lglpk glpk_sample.c
例えば以下のようなMakefileを用いるとよいです。
CFLAGS=-I /home/kay/local/glpk/include
LINK= /home/kay/local/glpk/lib/libglpk.a -lm -lglpk
trans: trans.o
gcc $^ $(LINK) -o $@
.c.o:
gcc $(CFLAGS) -c $^
/* glpk_sample.c */
#include <stdio.h>
#include <stdlib.h>
#include "glpk.h"
struct transfer_problem {
int n_transfers; //
int n_links; // Number of links
double *link_bws; // Bandwidth for each link
int *weights; // Number of destination nodes in each transfer
double *transfer_bws; // Bandwidth assigned to each transfer (output)
// Connction matrix (Sparse expression, the index starts from 1)
int *idx_links;
int *idx_transfers;
double *cm;
int n_cm_elems;
};
struct transfer_problem *new_transfer_problem(int n_transfers, int n_links, int n_cm_elems){
struct transfer_problem *tp =\
(struct transfer_problem *)malloc(sizeof(struct transfer_problem));
tp->n_transfers = n_transfers;
tp->n_links = n_links;
tp->weights = (int *)malloc(sizeof(int) * n_transfers);
tp->transfer_bws = (double *)malloc(sizeof(double) * n_transfers);
tp->link_bws = (double *)malloc(sizeof(double) * n_links);
// Connction matrix
tp->n_cm_elems = n_cm_elems;
tp->idx_links = (int *)malloc(sizeof(int) * (n_cm_elems+1));
tp->idx_transfers = (int *)malloc(sizeof(int) * (n_cm_elems+1));
tp->cm = (double *)malloc(sizeof(double) * (n_cm_elems+1));
return tp;
}
struct transfer_problem *make_sample_data(void){
// (link, transfer, value)
//1 (1, 1, 1)
//2 (2, 1, 1)
//3 (3, 2, 1)
//4 (4, 1, 1)
//5 (4, 2, 1)
//6 (5, 1, 1)
//7 (5, 2, 1)
//8 (6, 1, 1)
//9 (7, 2, 1)
static int WEIGHTS[2] = {2,1};
static double LINK_BWS[7] = {20, 30, 25, 32, 27, 19, 23};
static int IDX_LINKS[9] = {1, 2, 3, 4, 4, 5, 5, 6, 7};
static int IDX_TRANSFERS[9] = {1, 1, 2, 1, 2, 1, 2, 1, 2};
static int CM[9] = {1, 1, 1, 1, 1, 1, 1, 1, 1};
struct transfer_problem *tp;
int i;
tp = new_transfer_problem(2, 7, 9);
for(i = 0; i < tp->n_transfers; i++)
tp->weights[i] = WEIGHTS[i];
for(i = 0; i < tp->n_links; i++)
tp->link_bws[i] = LINK_BWS[i];
for(i = 0; i < tp->n_cm_elems; i++){
tp->idx_links[i+1] = IDX_LINKS[i];
tp->idx_transfers[i+1] = IDX_TRANSFERS[i];
tp->cm[i+1] = CM[i];
}
return tp;
}
double solve(struct transfer_problem *tp){
int i;
char label[128];
LPX *lp;
double Z;
int cnt;
lp = lpx_create_prob();
lpx_set_prob_name(lp, "trans");
lpx_set_obj_dir(lp, LPX_MAX);
lpx_add_rows(lp, tp->n_links);
for(i = 0; i < tp->n_links; i++){
sprintf(label, "link_%d", i);
lpx_set_row_name(lp, i+1, label);
lpx_set_row_bnds(lp, i+1, LPX_UP, 0.0, tp->link_bws[i]);
}
lpx_add_cols(lp, tp->n_transfers);
for(i = 0; i < tp->n_transfers; i++){
sprintf(label, "transfer_%d", i);
lpx_set_col_name(lp, i+1, label);
lpx_set_col_bnds(lp, i+1, LPX_LO, 0.0, 0.0);
lpx_set_obj_coef(lp, i+1, tp->weights[i]);
}
lpx_load_matrix(lp, tp->n_cm_elems, tp->idx_links, tp->idx_transfers, tp->cm);
lpx_simplex(lp);
Z = lpx_get_obj_val(lp);
for(i = 0; i < tp->n_transfers; i++){
tp->transfer_bws[i] = lpx_get_col_prim(lp, i+1);
}
lpx_delete_prob(lp);
return Z;
}
int main(void){
int i;
double Z;
struct transfer_problem *tp;
tp = make_sample_data();
Z = solve(tp);
printf("Z = %5.3d\n", Z);
for(i = 0; i < tp->n_links; i++){
printf("link %d:%5.3f ", i, tp->link_bws[i]);
}
printf("\n");
}
