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         if (maximize && opt)
  33                 isl_int_neg(*opt, *opt);
  34
  35         return res;
  36 }
  37
  38 /* Given a basic map "bmap" and an affine combination of the variables "f"
  39  * with denominator "denom", set *opt/*opt_denom to the minimal
  40  * (or maximal if "maximize" is true) value attained by f/d over "bmap",
  41  * assuming the basic map is not empty and the expression cannot attain
  42  * arbitrarily small (or large) values.
  43  * If opt_denom is NULL, then *opt is rounded up (or down)
  44  * to the nearest integer.
  45  * The return value reflects the nature of the result (empty, unbounded,
  46  * minmimal or maximal value returned in *opt).
  47  */
  48 enum isl_lp_result isl_basic_map_solve_lp(struct isl_basic_map *bmap, int max,
  49                                       isl_int *f, isl_int d, isl_int *opt,
  50                                       isl_int *opt_denom,
  51                                       struct isl_vec **sol)
  52 {
  53         if (sol)
  54                 *sol = NULL;
  55
  56         if (!bmap)
  57                 return isl_lp_error;
  58
  59         switch (bmap->ctx->opt->lp_solver) {
  60         case ISL_LP_PIP:
  61                 return isl_pip_solve_lp(bmap, max, f, d, opt, opt_denom, sol);
  62         case ISL_LP_TAB:
  63                 return isl_tab_solve_lp(bmap, max, f, d, opt, opt_denom, sol);
  64         default:
  65                 return isl_lp_error;
  66         }
  67 }
  68
  69 enum isl_lp_result isl_basic_set_solve_lp(struct isl_basic_set *bset, int max,
  70                                       isl_int *f, isl_int d, isl_int *opt,
  71                                       isl_int *opt_denom,
  72                                       struct isl_vec **sol)
  73 {
  74         return isl_basic_map_solve_lp((struct isl_basic_map *)bset, max,
  75                                         f, d, opt, opt_denom, sol);
  76 }