From 1192e00b23670c71a436f065c58f5524e80142b9 Mon Sep 17 00:00:00 2001 From: Thomas Kahle Date: Fri, 25 Apr 2014 22:07:30 +0200 Subject: [PATCH] Update the glpk calls to the new glp_ API Newer versions of GLPK no longer support the original lpx_ API. Since the use of GLPK is optional, there is little point in supporting two APIs. Switch to the new API and check that it is available. Signed-off-by: Thomas Kahle Signed-off-by: Sven Verdoolaege --- basis_reduction_glpk.c | 82 ++++++++++++++++++++++++++------------------------ configure.ac | 2 +- polysign_glpk.c | 72 +++++++++++++++++++++++--------------------- 3 files changed, 80 insertions(+), 76 deletions(-) diff --git a/basis_reduction_glpk.c b/basis_reduction_glpk.c index 136bfde..5806dbe 100644 --- a/basis_reduction_glpk.c +++ b/basis_reduction_glpk.c @@ -3,15 +3,15 @@ #include #include -static LPX *init_lp(Polyhedron *P); -static void set_lp_obj(LPX *lp, Value *row, int dim); -static int solve_lp(LPX *lp); -static void get_obj_val(LPX* lp, double *F); -static int add_lp_row(LPX *lp, Value *row, int dim); -static void get_alpha(LPX* lp, int row, double *alpha); -static void del_lp_row(LPX *lp); +static glp_prob *init_lp(Polyhedron *P); +static void set_lp_obj(glp_prob *lp, Value *row, int dim); +static int solve_lp(glp_prob *lp); +static void get_obj_val(glp_prob* lp, double *F); +static int add_lp_row(glp_prob *lp, Value *row, int dim); +static void get_alpha(glp_prob* lp, int row, double *alpha); +static void del_lp_row(glp_prob *lp); -#define GBR_LP LPX +#define GBR_LP glp_prob #define GBR_type double #define GBR_init(v) do { } while(0) #define GBR_clear(v) do { } while(0) @@ -25,30 +25,30 @@ static void del_lp_row(LPX *lp); #define GBR_lp_set_obj(lp, obj, dim) set_lp_obj(lp, obj, dim) #define GBR_lp_solve(lp) solve_lp(lp) #define GBR_lp_get_obj_val(lp, F) get_obj_val(lp, F) -#define GBR_lp_delete(lp) lpx_delete_prob(lp) -#define GBR_lp_next_row(lp) lpx_get_num_rows(lp)+1 +#define GBR_lp_delete(lp) glp_delete_prob(lp) +#define GBR_lp_next_row(lp) glp_get_num_rows(lp)+1 #define GBR_lp_add_row(lp, row, dim) add_lp_row(lp, row, dim) #define GBR_lp_get_alpha(lp, row, alpha) get_alpha(lp, row, alpha) #define GBR_lp_del_row(lp) del_lp_row(lp); #define Polyhedron_Reduced_Basis glpk_Polyhedron_Reduced_Basis #include "basis_reduction_templ.c" -static LPX *init_lp(Polyhedron *P) +static glp_prob *init_lp(Polyhedron *P) { - LPX *lp; + glp_prob *lp; int *ind; double *val; int i, j, k, l; ind = ALLOCN(int, 1+P->Dimension); val = ALLOCN(double, 1+P->Dimension); - lp = lpx_create_prob(); - lpx_set_obj_dir(lp, LPX_MAX); - lpx_add_rows(lp, 2*P->NbConstraints); - lpx_add_cols(lp, 2*P->Dimension); + lp = glp_create_prob(); + glp_set_obj_dir(lp, GLP_MAX); + glp_add_rows(lp, 2*P->NbConstraints); + glp_add_cols(lp, 2*P->Dimension); for (i = 0; i < 2; ++i) { for (j = 0; j < P->NbConstraints; ++j) { - int type = j < P->NbEq ? LPX_FX : LPX_LO; + int type = j < P->NbEq ? GLP_FX : GLP_LO; for (k = 0, l = 0; k < P->Dimension; ++k) { if (value_zero_p(P->Constraint[j][1+k])) continue; @@ -56,49 +56,51 @@ static LPX *init_lp(Polyhedron *P) val[1+l] = VALUE_TO_DOUBLE(P->Constraint[j][1+k]); ++l; } - lpx_set_mat_row(lp, 1+i*P->NbConstraints+j, l, ind, val); - lpx_set_row_bnds(lp, 1+i*P->NbConstraints+j, type, + glp_set_mat_row(lp, 1+i*P->NbConstraints+j, l, ind, val); + glp_set_row_bnds(lp, 1+i*P->NbConstraints+j, type, -VALUE_TO_DOUBLE(P->Constraint[j][1+P->Dimension]), 0); } for (k = 0, l = 0; k < P->Dimension; ++k) { - lpx_set_col_bnds(lp, 1+i*P->Dimension+k, LPX_FR, 0, 0); + glp_set_col_bnds(lp, 1+i*P->Dimension+k, GLP_FR, 0, 0); } } free(ind); free(val); - lpx_set_int_parm(lp, LPX_K_MSGLEV, 0); return lp; } -static void set_lp_obj(LPX *lp, Value *row, int dim) +static void set_lp_obj(glp_prob *lp, Value *row, int dim) { int j; for (j = 0; j < dim; ++j) { - lpx_set_obj_coef(lp, 1+j, VALUE_TO_DOUBLE(row[j])); - lpx_set_obj_coef(lp, 1+dim+j, -VALUE_TO_DOUBLE(row[j])); + glp_set_obj_coef(lp, 1+j, VALUE_TO_DOUBLE(row[j])); + glp_set_obj_coef(lp, 1+dim+j, -VALUE_TO_DOUBLE(row[j])); } } -static int solve_lp(LPX *lp) +static int solve_lp(glp_prob *lp) { - lpx_adv_basis(lp); - lpx_simplex(lp); - return lpx_get_status(lp) == LPX_UNBND; + glp_smcp parm; + glp_adv_basis(lp, 0); + glp_init_smcp(&parm); + parm.msg_lev = GLP_MSG_OFF; + glp_simplex(lp, &parm); + return glp_get_status(lp) == GLP_UNBND; } -static void get_obj_val(LPX* lp, double *F) +static void get_obj_val(glp_prob* lp, double *F) { - assert(lpx_get_status(lp) == LPX_OPT); - *F = lpx_get_obj_val(lp); + assert(glp_get_status(lp) == GLP_OPT); + *F = glp_get_obj_val(lp); assert(*F > -1e-10); if (*F < 0) *F = 0; } -static int add_lp_row(LPX *lp, Value *row, int dim) +static int add_lp_row(glp_prob *lp, Value *row, int dim) { int j, l; - int nr = lpx_add_rows(lp, 1); + int nr = glp_add_rows(lp, 1); int *ind; double *val; @@ -113,23 +115,23 @@ static int add_lp_row(LPX *lp, Value *row, int dim) val[1+l+1] = -VALUE_TO_DOUBLE(row[j]); l += 2; } - lpx_set_mat_row(lp, nr, l, ind, val); - lpx_set_row_bnds(lp, nr, LPX_FX, 0, 0); + glp_set_mat_row(lp, nr, l, ind, val); + glp_set_row_bnds(lp, nr, GLP_FX, 0, 0); free(ind); free(val); return nr; } -static void get_alpha(LPX* lp, int row, double *alpha) +static void get_alpha(glp_prob* lp, int row, double *alpha) { - *alpha = -lpx_get_row_dual(lp, row); + *alpha = -glp_get_row_dual(lp, row); } -static void del_lp_row(LPX *lp) +static void del_lp_row(glp_prob *lp) { int rows[2]; - rows[1] = lpx_get_num_rows(lp); - lpx_del_rows(lp, 1, rows); + rows[1] = glp_get_num_rows(lp); + glp_del_rows(lp, 1, rows); } diff --git a/configure.ac b/configure.ac index 76a299f..b917f32 100644 --- a/configure.ac +++ b/configure.ac @@ -403,7 +403,7 @@ if test "$glpk_package" != "no"; then fi AC_CHECK_HEADERS([glpk.h],[ have_glpk=true - AC_CHECK_LIB(glpk, main,[],[have_glpk=false]) + AC_CHECK_LIB(glpk, [glp_simplex],[],[have_glpk=false]) ]) fi AM_CONDITIONAL(HAVE_GLPK, test x$have_glpk = xtrue) diff --git a/polysign_glpk.c b/polysign_glpk.c index e6b6126..734cca2 100644 --- a/polysign_glpk.c +++ b/polysign_glpk.c @@ -9,9 +9,10 @@ #define EMPTY_DOMAIN -2 -static LPX *solve_lp(int dir, Matrix *C, Value *f, Value denom) +static glp_prob *solve_lp(int dir, Matrix *C, Value *f, Value denom) { - LPX *lp; + glp_prob *lp; + glp_smcp parm; int *ind; double *val; int j, k, l; @@ -19,13 +20,13 @@ static LPX *solve_lp(int dir, Matrix *C, Value *f, Value denom) ind = ALLOCN(int, 1+dim); val = ALLOCN(double, 1+dim); - lp = lpx_create_prob(); - lpx_set_obj_dir(lp, dir); - lpx_add_rows(lp, C->NbRows); - lpx_add_cols(lp, dim); + lp = glp_create_prob(); + glp_set_obj_dir(lp, dir); + glp_add_rows(lp, C->NbRows); + glp_add_cols(lp, dim); for (j = 0; j < C->NbRows; ++j) { - int type = value_zero_p(C->p[j][0]) ? LPX_FX : LPX_LO; + int type = value_zero_p(C->p[j][0]) ? GLP_FX : GLP_LO; for (k = 0, l = 0; k < dim; ++k) { if (value_zero_p(C->p[j][1+k])) continue; @@ -33,26 +34,27 @@ static LPX *solve_lp(int dir, Matrix *C, Value *f, Value denom) val[1+l] = VALUE_TO_DOUBLE(C->p[j][1+k]); ++l; } - lpx_set_mat_row(lp, 1+j, l, ind, val); - lpx_set_row_bnds(lp, 1+j, type, + glp_set_mat_row(lp, 1+j, l, ind, val); + glp_set_row_bnds(lp, 1+j, type, -VALUE_TO_DOUBLE(C->p[j][1+dim]), 0); } for (k = 0, l = 0; k < dim; ++k) { - lpx_set_col_bnds(lp, 1+k, LPX_FR, 0, 0); + glp_set_col_bnds(lp, 1+k, GLP_FR, 0, 0); } free(ind); free(val); - lpx_set_int_parm(lp, LPX_K_MSGLEV, 0); /* objective function */ for (j = 0; j < dim; ++j) - lpx_set_obj_coef(lp, 1+j, VALUE_TO_DOUBLE(f[j]) / + glp_set_obj_coef(lp, 1+j, VALUE_TO_DOUBLE(f[j]) / VALUE_TO_DOUBLE(denom)); - lpx_set_obj_coef(lp, 0, VALUE_TO_DOUBLE(f[dim]) / + glp_set_obj_coef(lp, 0, VALUE_TO_DOUBLE(f[dim]) / VALUE_TO_DOUBLE(denom)); - lpx_adv_basis(lp); - lpx_simplex(lp); + glp_adv_basis(lp, 0); + glp_init_smcp(&parm); + parm.msg_lev = GLP_MSG_OFF; + glp_simplex(lp, &parm); return lp; } @@ -61,32 +63,32 @@ static enum lp_result constraints_affine_minmax(int dir, Matrix *C, Value *f, Value denom, Value *opt) { enum lp_result res = lp_ok; - LPX *lp = solve_lp(dir, C, f, denom); + glp_prob *lp = solve_lp(dir, C, f, denom); - switch (lpx_get_status(lp)) { - case LPX_OPT: - if (dir == LPX_MIN) - value_set_si(*opt, (int)ceil(lpx_get_obj_val(lp)-1e-10)); + switch (glp_get_status(lp)) { + case GLP_OPT: + if (dir == GLP_MIN) + value_set_si(*opt, (int)ceil(glp_get_obj_val(lp)-1e-10)); else - value_set_si(*opt, (int)floor(lpx_get_obj_val(lp)+1e-10)); + value_set_si(*opt, (int)floor(glp_get_obj_val(lp)+1e-10)); break; - case LPX_UNBND: + case GLP_UNBND: res = lp_unbounded; break; - case LPX_NOFEAS: + case GLP_NOFEAS: res = lp_empty; break; default: assert(0); } - lpx_delete_prob(lp); + glp_delete_prob(lp); return res; } static int constraints_affine_minmax_sign(int dir, Matrix *C, Matrix *T, int rational) { - LPX *lp; + glp_prob *lp; int sign; double opt; unsigned dim = C->NbColumns-2; @@ -94,9 +96,9 @@ static int constraints_affine_minmax_sign(int dir, Matrix *C, Matrix *T, assert(T->NbRows == 2); lp = solve_lp(dir, C, T->p[0], T->p[1][dim]); - switch (lpx_get_status(lp)) { - case LPX_OPT: - opt = lpx_get_obj_val(lp); + switch (glp_get_status(lp)) { + case GLP_OPT: + opt = glp_get_obj_val(lp); if (rational) { sign = opt < 0 ? -1 : opt > 0 ? 1 : 0; } else { @@ -108,19 +110,19 @@ static int constraints_affine_minmax_sign(int dir, Matrix *C, Matrix *T, sign = 0; } break; - case LPX_UNBND: - if (dir == LPX_MIN) + case GLP_UNBND: + if (dir == GLP_MIN) sign = -1; else sign = 1; break; - case LPX_NOFEAS: + case GLP_NOFEAS: sign = EMPTY_DOMAIN; break; default: assert(0); } - lpx_delete_prob(lp); + glp_delete_prob(lp); return sign; } @@ -152,12 +154,12 @@ enum order_sign glpk_polyhedron_affine_sign(Polyhedron *D, Matrix *T, return glpk_polyhedron_affine_sign_0D(D, T); Polyhedron_Matrix_View(D, &M, D->NbConstraints); - int min = constraints_affine_minmax_sign(LPX_MIN, &M, T, rational); + int min = constraints_affine_minmax_sign(GLP_MIN, &M, T, rational); if (min == EMPTY_DOMAIN) return order_undefined; if (min > 0) return order_gt; - int max = constraints_affine_minmax_sign(LPX_MAX, &M, T, rational); + int max = constraints_affine_minmax_sign(GLP_MAX, &M, T, rational); assert(max != EMPTY_DOMAIN); if (max < 0) return order_lt; @@ -173,6 +175,6 @@ enum order_sign glpk_polyhedron_affine_sign(Polyhedron *D, Matrix *T, enum lp_result glpk_constraints_opt(Matrix *C, Value *obj, Value denom, enum lp_dir dir, Value *opt) { - int glpk_dir = dir == lp_min ? LPX_MIN : LPX_MAX; + int glpk_dir = dir == lp_min ? GLP_MIN : GLP_MAX; return constraints_affine_minmax(glpk_dir, C, obj, denom, opt); } -- 2.11.4.GIT