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