isl_lp_piplib.c

   1 #include "isl_map.h"
   2 #include "isl_vec.h"
   3 #include "isl_lp.h"
   4 #include "isl_piplib.h"
   5 #include "isl_map_piplib.h"
   6
   7 static void copy_solution(struct isl_vec *vec, int maximize, isl_int *opt,
   8         isl_int *opt_denom, PipQuast *sol)
   9 {
  10         int i;
  11         PipList *list;
  12         isl_int tmp;
  13
  14         if (opt) {
  15                 if (opt_denom) {
  16                         isl_seq_cpy_from_pip(opt,
  17                                  &sol->list->vector->the_vector[0], 1);
  18                         isl_seq_cpy_from_pip(opt_denom,
  19                                  &sol->list->vector->the_deno[0], 1);
  20                 } else if (maximize)
  21                         mpz_fdiv_q(*opt, sol->list->vector->the_vector[0],
  22                                          sol->list->vector->the_deno[0]);
  23                 else
  24                         mpz_cdiv_q(*opt, sol->list->vector->the_vector[0],
  25                                          sol->list->vector->the_deno[0]);
  26         }
  27
  28         if (!vec)
  29                 return;
  30
  31         isl_int_init(tmp);
  32         isl_int_set_si(vec->el[0], 1);
  33         for (i = 0, list = sol->list->next; list; ++i, list = list->next) {
  34                 isl_seq_cpy_from_pip(&vec->el[1 + i],
  35                         &list->vector->the_deno[0], 1);
  36                 isl_int_lcm(vec->el[0], vec->el[0], vec->el[1 + i]);
  37         }
  38         for (i = 0, list = sol->list->next; list; ++i, list = list->next) {
  39                 isl_seq_cpy_from_pip(&tmp, &list->vector->the_deno[0], 1);
  40                 isl_int_divexact(tmp, vec->el[0], tmp);
  41                 isl_seq_cpy_from_pip(&vec->el[1 + i],
  42                         &list->vector->the_vector[0], 1);
  43                 isl_int_mul(vec->el[1 + i], vec->el[1 + i], tmp);
  44         }
  45         isl_int_clear(tmp);
  46 }
  47
  48 enum isl_lp_result isl_pip_solve_lp(struct isl_basic_map *bmap, int maximize,
  49                                       isl_int *f, isl_int denom, isl_int *opt,
  50                                       isl_int *opt_denom,
  51                                       struct isl_vec **vec)
  52 {
  53         enum isl_lp_result res = isl_lp_ok;
  54         PipMatrix       *domain = NULL;
  55         PipOptions      *options;
  56         PipQuast        *sol;
  57         unsigned         total;
  58
  59         total = isl_basic_map_total_dim(bmap);
  60         domain = isl_basic_map_to_pip(bmap, 0, 1, 0);
  61         if (!domain)
  62                 goto error;
  63         entier_set_si(domain->p[0][1], -1);
  64         isl_int_set(domain->p[0][domain->NbColumns - 1], f[0]);
  65         isl_seq_cpy_to_pip(domain->p[0]+2, f+1, total);
  66
  67         options = pip_options_init();
  68         if (!options)
  69                 goto error;
  70         options->Urs_unknowns = -1;
  71         options->Maximize = maximize;
  72         options->Nq = 0;
  73         sol = pip_solve(domain, NULL, -1, options);
  74         pip_options_free(options);
  75         if (!sol)
  76                 goto error;
  77
  78         if (vec)
  79                 *vec = isl_vec_alloc(bmap->ctx, 1 + total);
  80         if (vec && !*vec)
  81                 res = isl_lp_error;
  82         else if (!sol->list)
  83                 res = isl_lp_empty;
  84         else if (entier_zero_p(sol->list->vector->the_deno[0]))
  85                 res = isl_lp_unbounded;
  86         else
  87                 copy_solution(*vec, maximize, opt, opt_denom, sol);
  88         pip_matrix_free(domain);
  89         pip_quast_free(sol);
  90         return res;
  91 error:
  92         if (domain)
  93                 pip_matrix_free(domain);
  94         return isl_lp_error;
  95 }