isl_lp.c

   1 #include "isl_ctx.h"
   2 #include "isl_lp.h"
   3 #include "isl_lp_piplib.h"
   4 #include "isl_seq.h"
   5 #include "isl_tab.h"
   6 #include "isl_map_private.h"
   7
   8 enum isl_lp_result isl_tab_solve_lp(struct isl_basic_map *bmap, int maximize,
   9                                       isl_int *f, isl_int denom, isl_int *opt,
  10                                       isl_int *opt_denom,
  11                                       struct isl_vec **sol)
  12 {
  13         struct isl_tab *tab;
  14         enum isl_lp_result res;
  15         unsigned dim = isl_basic_map_total_dim(bmap);
  16
  17         if (maximize)
  18                 isl_seq_neg(f, f, 1 + dim);
  19
  20         bmap = isl_basic_map_gauss(bmap, NULL);
  21         tab = isl_tab_from_basic_map(bmap);
  22         res = isl_tab_min(tab, f, bmap->ctx->one, opt, opt_denom, 0);
  23         if (res == isl_lp_ok && sol) {
  24                 *sol = isl_tab_get_sample_value(tab);
  25                 if (!*sol)
  26                         res = isl_lp_error;
  27         }
  28         isl_tab_free(tab);
  29
  30         if (maximize)
  31                 isl_seq_neg(f, f, 1 + dim);
  32
  33         return res;
  34 }
  35
  36 /* Given a basic map "bmap" and an affine combination of the variables "f"
  37  * with denominator "denom", set *opt/*opt_denom to the minimal
  38  * (or maximal if "maximize" is true) value attained by f/d over "bmap",
  39  * assuming the basic map is not empty and the expression cannot attain
  40  * arbitrarily small (or large) values.
  41  * If opt_denom is NULL, then *opt is rounded up (or down)
  42  * to the nearest integer.
  43  * The return value reflects the nature of the result (empty, unbounded,
  44  * minmimal or maximal value returned in *opt).
  45  */
  46 enum isl_lp_result isl_basic_map_solve_lp(struct isl_basic_map *bmap, int max,
  47                                       isl_int *f, isl_int d, isl_int *opt,
  48                                       isl_int *opt_denom,
  49                                       struct isl_vec **sol)
  50 {
  51         if (sol)
  52                 *sol = NULL;
  53
  54         if (!bmap)
  55                 return isl_lp_error;
  56
  57         switch (bmap->ctx->lp_solver) {
  58         case ISL_LP_PIP:
  59                 return isl_pip_solve_lp(bmap, max, f, d, opt, opt_denom, sol);
  60         case ISL_LP_TAB:
  61                 return isl_tab_solve_lp(bmap, max, f, d, opt, opt_denom, sol);
  62         default:
  63                 return isl_lp_error;
  64         }
  65 }
  66
  67 enum isl_lp_result isl_basic_set_solve_lp(struct isl_basic_set *bset, int max,
  68                                       isl_int *f, isl_int d, isl_int *opt,
  69                                       isl_int *opt_denom,
  70                                       struct isl_vec **sol)
  71 {
  72         return isl_basic_map_solve_lp((struct isl_basic_map *)bset, max,
  73                                         f, d, opt, opt_denom, sol);
  74 }