polysign_pip.c

   1 #include <assert.h>
   2 #include <piplib/piplibMP.h>
   3 #include "polysign.h"
   4
   5 static PipQuast *solve_lp(int maximize, Matrix *C, Value *f, Value denom)
   6 {
   7     int i;
   8     PipMatrix   *domain;
   9     PipOptions  *options;
  10     PipQuast    *sol;
  11
  12     domain = pip_matrix_alloc(C->NbRows+1, C->NbColumns+1);
  13     value_set_si(domain->p[0][0], 0);
  14     value_set_si(domain->p[0][1], -1);
  15     Vector_Copy(f, domain->p[0]+2, C->NbColumns-1);
  16     for (i = 0; i < C->NbRows; ++i) {
  17         value_assign(domain->p[i+1][0], C->p[i][0]);
  18         Vector_Copy(C->p[i]+1, domain->p[i+1]+2, C->NbColumns-1);
  19     }
  20
  21     options = pip_options_init();
  22     options->Urs_unknowns = -1;
  23     options->Maximize = maximize;
  24     options->Nq = 0;
  25     sol = pip_solve(domain, NULL, -1, options);
  26     pip_matrix_free(domain);
  27     pip_options_free(options);
  28
  29     return sol;
  30 }
  31
  32 static enum lp_result constraints_affine_minmax(int maximize, Matrix *C,
  33                                               Value *f, Value denom, Value *opt)
  34 {
  35     enum lp_result res = lp_ok;
  36     PipQuast *sol = solve_lp(maximize, C, f, denom);
  37
  38     if (!sol->list)
  39         res = lp_empty;
  40     else if (value_zero_p(sol->list->vector->the_deno[0]))
  41         res = lp_unbounded;
  42     else {
  43         if (maximize)
  44             mpz_fdiv_q(*opt, sol->list->vector->the_vector[0],
  45                              sol->list->vector->the_deno[0]);
  46         else
  47             mpz_cdiv_q(*opt, sol->list->vector->the_vector[0],
  48                              sol->list->vector->the_deno[0]);
  49     }
  50     pip_quast_free(sol);
  51     return res;
  52 }
  53
  54 enum lp_result pip_constraints_opt(Matrix *C, Value *obj, Value denom,
  55                                     enum lp_dir dir, Value *opt)
  56 {
  57     int maximize = dir == lp_min ? 0 : 1;
  58     return constraints_affine_minmax(maximize, C, obj, denom, opt);
  59 }
  60
  61 enum lp_result pip_polyhedron_range(Polyhedron *D, Value *obj, Value denom,
  62                                 Value *min, Value *max,
  63                                 struct barvinok_options *options)
  64 {
  65     enum lp_result res;
  66     Matrix M;
  67
  68     if (emptyQ(D))
  69         return lp_empty;
  70
  71     Polyhedron_Matrix_View(D, &M, D->NbConstraints);
  72     res = constraints_affine_minmax(0, &M, obj, denom, min);
  73     if (res != lp_ok)
  74         return res;
  75     res = constraints_affine_minmax(1, &M, obj, denom, max);
  76     return res;
  77 }