polyhedron_minimize.c

   1 /*
   2  * Copyright 2008-2009 Katholieke Universiteit Leuven
   3  *
   4  * Use of this software is governed by the MIT license
   5  *
   6  * Written by Sven Verdoolaege, K.U.Leuven, Departement
   7  * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
   8  */
   9
  10 #include <assert.h>
  11 #include <isl/set.h>
  12 #include <isl/vec.h>
  13 #include <isl_ilp_private.h>
  14 #include <isl_seq.h>
  15 #include <isl_vec_private.h>
  16
  17 /* The input of this program is the same as that of the "polytope_minimize"
  18  * program from the barvinok distribution.
  19  *
  20  * Constraints of set is PolyLib format.
  21  * Linear or affine objective function in PolyLib format.
  22  */
  23
  24 static struct isl_vec *isl_vec_lin_to_aff(struct isl_vec *vec)
  25 {
  26         struct isl_vec *aff;
  27
  28         if (!vec)
  29                 return NULL;
  30         aff = isl_vec_alloc(vec->ctx, 1 + vec->size);
  31         if (!aff)
  32                 goto error;
  33         isl_int_set_si(aff->el[0], 0);
  34         isl_seq_cpy(aff->el + 1, vec->el, vec->size);
  35         isl_vec_free(vec);
  36         return aff;
  37 error:
  38         isl_vec_free(vec);
  39         return NULL;
  40 }
  41
  42 /* Rotate elements of vector right.
  43  * In particular, move the constant term from the end of the
  44  * vector to the start of the vector.
  45  */
  46 static struct isl_vec *vec_ror(struct isl_vec *vec)
  47 {
  48         int i;
  49
  50         if (!vec)
  51                 return NULL;
  52         for (i = vec->size - 2; i >= 0; --i)
  53                 isl_int_swap(vec->el[i], vec->el[i + 1]);
  54         return vec;
  55 }
  56
  57 int main(int argc, char **argv)
  58 {
  59         struct isl_ctx *ctx = isl_ctx_alloc();
  60         struct isl_basic_set *bset;
  61         struct isl_vec *obj;
  62         struct isl_vec *sol;
  63         isl_int opt;
  64         unsigned dim;
  65         enum isl_lp_result res;
  66         isl_printer *p;
  67
  68         isl_int_init(opt);
  69         bset = isl_basic_set_read_from_file(ctx, stdin);
  70         assert(bset);
  71         obj = isl_vec_read_from_file(ctx, stdin);
  72         assert(obj);
  73         dim = isl_basic_set_total_dim(bset);
  74         assert(obj->size >= dim && obj->size <= dim + 1);
  75         if (obj->size != dim + 1)
  76                 obj = isl_vec_lin_to_aff(obj);
  77         else
  78                 obj = vec_ror(obj);
  79         res = isl_basic_set_solve_ilp(bset, 0, obj->el, &opt, &sol);
  80         switch (res) {
  81         case isl_lp_error:
  82                 fprintf(stderr, "error\n");
  83                 return -1;
  84         case isl_lp_empty:
  85                 fprintf(stdout, "empty\n");
  86                 break;
  87         case isl_lp_unbounded:
  88                 fprintf(stdout, "unbounded\n");
  89                 break;
  90         case isl_lp_ok:
  91                 p = isl_printer_to_file(ctx, stdout);
  92                 p = isl_printer_print_vec(p, sol);
  93                 p = isl_printer_end_line(p);
  94                 p = isl_printer_print_isl_int(p, opt);
  95                 p = isl_printer_end_line(p);
  96                 isl_printer_free(p);
  97         }
  98         isl_basic_set_free(bset);
  99         isl_vec_free(obj);
 100         isl_vec_free(sol);
 101         isl_ctx_free(ctx);
 102         isl_int_clear(opt);
 103
 104         return 0;
 105 }