polyhedron_minimize.c

   1 #include <assert.h>
   2 #include "isl_set.h"
   3 #include "isl_vec.h"
   4 #include "isl_ilp.h"
   5 #include "isl_seq.h"
   6
   7 /* The input of this program is the same as that of the "polytope_minimize"
   8  * program from the barvinok distribution.
   9  *
  10  * Constraints of set is PolyLib format.
  11  * Linear or affine objective function in PolyLib format.
  12  */
  13
  14 static struct isl_vec *isl_vec_lin_to_aff(struct isl_vec *vec)
  15 {
  16         struct isl_vec *aff;
  17
  18         if (!vec)
  19                 return NULL;
  20         aff = isl_vec_alloc(vec->ctx, 1 + vec->size);
  21         if (!aff)
  22                 goto error;
  23         isl_int_set_si(aff->el[0], 0);
  24         isl_seq_cpy(aff->el + 1, vec->el, vec->size);
  25         isl_vec_free(vec);
  26         return aff;
  27 error:
  28         isl_vec_free(vec);
  29         return NULL;
  30 }
  31
  32 /* Rotate elements of vector right.
  33  * In particular, move the constant term from the end of the
  34  * vector to the start of the vector.
  35  */
  36 static struct isl_vec *vec_ror(struct isl_vec *vec)
  37 {
  38         int i;
  39
  40         if (!vec)
  41                 return NULL;
  42         for (i = vec->size - 2; i >= 0; --i)
  43                 isl_int_swap(vec->el[i], vec->el[i + 1]);
  44         return vec;
  45 }
  46
  47 int main(int argc, char **argv)
  48 {
  49         struct isl_ctx *ctx = isl_ctx_alloc();
  50         struct isl_basic_set *bset;
  51         struct isl_vec *obj;
  52         struct isl_vec *sol;
  53         isl_int opt;
  54         unsigned dim;
  55         enum isl_lp_result res;
  56
  57         isl_int_init(opt);
  58         bset = isl_basic_set_read_from_file(ctx, stdin, 0, ISL_FORMAT_POLYLIB);
  59         assert(bset);
  60         obj = isl_vec_read_from_file(ctx, stdin, ISL_FORMAT_POLYLIB);
  61         assert(obj);
  62         dim = isl_basic_set_total_dim(bset);
  63         assert(obj->size >= dim && obj->size <= dim + 1);
  64         if (obj->size != dim + 1)
  65                 obj = isl_vec_lin_to_aff(obj);
  66         else
  67                 obj = vec_ror(obj);
  68         res = isl_basic_set_solve_ilp(bset, 0, obj->el, &opt, &sol);
  69         assert(res != isl_lp_error);
  70         switch (res) {
  71         case isl_lp_empty:
  72                 fprintf(stdout, "empty\n");
  73                 break;
  74         case isl_lp_unbounded:
  75                 fprintf(stdout, "unbounded\n");
  76                 break;
  77         case isl_lp_ok:
  78                 isl_vec_dump(sol, stdout, 0);
  79                 isl_int_print(stdout, opt, 0);
  80                 fprintf(stdout, "\n");
  81         }
  82         isl_basic_set_free(bset);
  83         isl_vec_free(obj);
  84         isl_vec_free(sol);
  85         isl_ctx_free(ctx);
  86         isl_int_clear(opt);
  87
  88         return 0;
  89 }