isl_lp.c

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