From 62855b103223ce7e2d74e01760e84bf69556d959 Mon Sep 17 00:00:00 2001 From: Sven Verdoolaege Date: Sat, 27 Oct 2007 13:33:45 +0200 Subject: [PATCH] polysign: add pip-backed version --- Makefile.am | 1 + barvinok/options.h | 1 + options.c | 14 +++++----- polysign.c | 4 +++ polysign.h | 5 ++++ polysign_pip.c | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 96 insertions(+), 6 deletions(-) create mode 100644 polysign_pip.c diff --git a/Makefile.am b/Makefile.am index 854c2b8..6f2a446 100644 --- a/Makefile.am +++ b/Makefile.am @@ -106,6 +106,7 @@ libbarvinok_la_SOURCES = \ $(POLYSIGN_CDD) \ $(POLYSIGN_GLPK) \ polysign.c \ + polysign_pip.c \ polysign_polylib.c \ polysign.h \ reduce_domain.c \ diff --git a/barvinok/options.h b/barvinok/options.h index 42b51e2..2fd6aa1 100644 --- a/barvinok/options.h +++ b/barvinok/options.h @@ -85,6 +85,7 @@ struct barvinok_options { #define BV_LP_GLPK 1 #define BV_LP_CDD 2 #define BV_LP_CDDF 3 + #define BV_LP_PIP 4 int lp_solver; #define BV_SUM_BARVINOK 0 diff --git a/options.c b/options.c index f661cea..34da260 100644 --- a/options.c +++ b/options.c @@ -84,7 +84,7 @@ struct barvinok_options *barvinok_options_new_with_defaults() #elif defined HAVE_LIBCDDGMP options->lp_solver = BV_LP_CDD; #else - options->lp_solver = BV_LP_POLYLIB; + options->lp_solver = BV_LP_PIP; #endif options->summation = BV_SUM_BARVINOK; @@ -163,13 +163,13 @@ static struct argp_option barvinok_argp_options[] = { }, { "lp", BV_OPT_LP, #if defined(HAVE_LIBGLPK) && defined(HAVE_LIBCDDGMP) - "cdd|cddf|glpk|polylib", + "cdd|cddf|glpk|pip|polylib", #elif defined(HAVE_LIBGLPK) - "glpk|polylib", + "glpk|pip|polylib", #elif defined(HAVE_LIBCDDGMP) - "cdd|cddf|polylib", + "cdd|cddf|pip|polylib", #else - "polylib", + "pip|polylib", #endif 0, "lp solver to use " #if defined(HAVE_LIBGLPK) @@ -177,7 +177,7 @@ static struct argp_option barvinok_argp_options[] = { #elif defined(HAVE_LIBCDDGMP) "[default: cdd]", #else - "[default: polylib]", + "[default: pip]", #endif }, { "summation", BV_OPT_SUM, "barvinok|bernoulli|euler", 0, @@ -326,6 +326,8 @@ static error_t barvinok_parse_opt(int key, char *arg, struct argp_state *state) options->lp_solver = BV_LP_CDDF; if (!strcmp(arg, "glpk")) options->lp_solver = BV_LP_GLPK; + if (!strcmp(arg, "pip")) + options->lp_solver = BV_LP_PIP; if (!strcmp(arg, "polylib")) options->lp_solver = BV_LP_POLYLIB; break; diff --git a/polysign.c b/polysign.c index bdd4089..c4e97b5 100644 --- a/polysign.c +++ b/polysign.c @@ -98,6 +98,8 @@ enum lp_result constraints_opt(Matrix *C, Value *obj, Value denom, return cdd_constraints_opt(C, obj, denom, dir, opt); else if (options->lp_solver == BV_LP_CDDF) return cddf_constraints_opt(C, obj, denom, dir, opt); + else if (options->lp_solver == BV_LP_PIP) + return pip_constraints_opt(C, obj, denom, dir, opt); else assert(0); } @@ -133,6 +135,8 @@ enum lp_result polyhedron_range(Polyhedron *D, Value *obj, Value denom, return cdd_polyhedron_range(D, obj, denom, min, max, options); else if (options->lp_solver == BV_LP_CDDF) return cddf_polyhedron_range(D, obj, denom, min, max, options); + else if (options->lp_solver == BV_LP_PIP) + return pip_polyhedron_range(D, obj, denom, min, max, options); else assert(0); } diff --git a/polysign.h b/polysign.h index 250f1d0..75be9a8 100644 --- a/polysign.h +++ b/polysign.h @@ -34,6 +34,8 @@ enum lp_result cdd_constraints_opt(Matrix *C, Value *obj, Value denom, enum lp_dir dir, Value *opt); enum lp_result cddf_constraints_opt(Matrix *C, Value *obj, Value denom, enum lp_dir dir, Value *opt); +enum lp_result pip_constraints_opt(Matrix *C, Value *obj, Value denom, + enum lp_dir dir, Value *opt); enum lp_result polyhedron_opt(Polyhedron *P, Value *obj, Value denom, enum lp_dir dir, Value *opt, @@ -60,6 +62,9 @@ enum lp_result cdd_polyhedron_range(Polyhedron *D, Value *obj, Value denom, enum lp_result cddf_polyhedron_range(Polyhedron *D, Value *obj, Value denom, Value *min, Value *max, struct barvinok_options *options); +enum lp_result pip_polyhedron_range(Polyhedron *D, Value *obj, Value denom, + Value *min, Value *max, + struct barvinok_options *options); #if defined(__cplusplus) } #endif diff --git a/polysign_pip.c b/polysign_pip.c new file mode 100644 index 0000000..27b5e90 --- /dev/null +++ b/polysign_pip.c @@ -0,0 +1,77 @@ +#include +#include +#include "polysign.h" + +static PipQuast *solve_lp(int maximize, Matrix *C, Value *f, Value denom) +{ + int i; + PipMatrix *domain; + PipOptions *options; + PipQuast *sol; + + domain = pip_matrix_alloc(C->NbRows+1, C->NbColumns+1); + value_set_si(domain->p[0][0], 0); + value_set_si(domain->p[0][1], -1); + Vector_Copy(f, domain->p[0]+2, C->NbColumns-1); + for (i = 0; i < C->NbRows; ++i) { + value_assign(domain->p[i+1][0], C->p[i][0]); + Vector_Copy(C->p[i]+1, domain->p[i+1]+2, C->NbColumns-1); + } + + options = pip_options_init(); + options->Urs_unknowns = -1; + options->Maximize = maximize; + options->Nq = 0; + sol = pip_solve(domain, NULL, -1, options); + pip_matrix_free(domain); + pip_options_free(options); + + return sol; +} + +static enum lp_result constraints_affine_minmax(int maximize, Matrix *C, + Value *f, Value denom, Value *opt) +{ + enum lp_result res = lp_ok; + PipQuast *sol = solve_lp(maximize, C, f, denom); + + if (!sol->list) + res = lp_empty; + else if (value_zero_p(sol->list->vector->the_deno[0])) + res = lp_unbounded; + else { + if (maximize) + mpz_fdiv_q(*opt, sol->list->vector->the_vector[0], + sol->list->vector->the_deno[0]); + else + mpz_cdiv_q(*opt, sol->list->vector->the_vector[0], + sol->list->vector->the_deno[0]); + } + pip_quast_free(sol); + return res; +} + +enum lp_result pip_constraints_opt(Matrix *C, Value *obj, Value denom, + enum lp_dir dir, Value *opt) +{ + int maximize = dir == lp_min ? 0 : 1; + return constraints_affine_minmax(maximize, C, obj, denom, opt); +} + +enum lp_result pip_polyhedron_range(Polyhedron *D, Value *obj, Value denom, + Value *min, Value *max, + struct barvinok_options *options) +{ + enum lp_result res; + Matrix M; + + if (emptyQ(D)) + return lp_empty; + + Polyhedron_Matrix_View(D, &M, D->NbConstraints); + res = constraints_affine_minmax(0, &M, obj, denom, min); + if (res != lp_ok) + return res; + res = constraints_affine_minmax(1, &M, obj, denom, max); + return res; +} -- 2.11.4.GIT