basis_reduction_templ.c

   1 /*
   2  * Copyright 2006-2007 Universiteit Leiden
   3  * Copyright 2008-2009 Katholieke Universiteit Leuven
   4  *
   5  * Use of this software is governed by the GNU LGPLv2.1 license
   6  *
   7  * Written by Sven Verdoolaege, Leiden Institute of Advanced Computer Science,
   8  * Universiteit Leiden, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands
   9  * and K.U.Leuven, Departement Computerwetenschappen, Celestijnenlaan 200A,
  10  * B-3001 Leuven, Belgium
  11  */
  12
  13 #include <stdlib.h>
  14 #include "isl_basis_reduction.h"
  15
  16 static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha)
  17 {
  18         int i;
  19
  20         for (i = 0; i < n; ++i)
  21                 GBR_lp_get_alpha(lp, first + i, &alpha[i]);
  22 }
  23
  24 /* Compute a reduced basis for the set represented by the tableau "tab".
  25  * tab->basis, must be initialized by the calling function to an affine
  26  * unimodular basis, is updated to reflect the reduced basis.
  27  * The first tab->n_zero rows of the basis (ignoring the constant row)
  28  * are assumed to correspond to equalities and are left untouched.
  29  * tab->n_zero is updated to reflect any additional equalities that
  30  * have been detected in the first rows of the new basis.
  31  * The final tab->n_unbounded rows of the basis are assumed to correspond
  32  * to unbounded directions and are also left untouched.
  33  * In particular this means that the remaining rows are assumed to
  34  * correspond to bounded directions.
  35  *
  36  * This function implements the algorithm described in
  37  * "An Implementation of the Generalized Basis Reduction Algorithm
  38  *  for Integer Programming" of Cook el al. to compute a reduced basis.
  39  * We use \epsilon = 1/4.
  40  *
  41  * If ctx->opt->gbr_only_first is set, the user is only interested
  42  * in the first direction.  In this case we stop the basis reduction when
  43  * the width in the first direction becomes smaller than 2.
  44  */
  45 struct isl_tab *isl_tab_compute_reduced_basis(struct isl_tab *tab)
  46 {
  47         unsigned dim;
  48         struct isl_ctx *ctx;
  49         struct isl_mat *B;
  50         int unbounded;
  51         int i;
  52         GBR_LP *lp = NULL;
  53         GBR_type F_old, alpha, F_new;
  54         int row;
  55         isl_int tmp;
  56         struct isl_vec *b_tmp;
  57         GBR_type *F = NULL;
  58         GBR_type *alpha_buffer[2] = { NULL, NULL };
  59         GBR_type *alpha_saved;
  60         GBR_type F_saved;
  61         int use_saved = 0;
  62         isl_int mu[2];
  63         GBR_type mu_F[2];
  64         GBR_type two;
  65         GBR_type one;
  66         int empty = 0;
  67         int fixed = 0;
  68         int fixed_saved = 0;
  69         int mu_fixed[2];
  70         int n_bounded;
  71         int gbr_only_first;
  72
  73         if (!tab)
  74                 return NULL;
  75
  76         if (tab->empty)
  77                 return tab;
  78
  79         ctx = tab->mat->ctx;
  80         gbr_only_first = ctx->opt->gbr_only_first;
  81         dim = tab->n_var;
  82         B = tab->basis;
  83         if (!B)
  84                 return tab;
  85
  86         n_bounded = dim - tab->n_unbounded;
  87         if (n_bounded <= tab->n_zero + 1)
  88                 return tab;
  89
  90         isl_int_init(tmp);
  91         isl_int_init(mu[0]);
  92         isl_int_init(mu[1]);
  93
  94         GBR_init(alpha);
  95         GBR_init(F_old);
  96         GBR_init(F_new);
  97         GBR_init(F_saved);
  98         GBR_init(mu_F[0]);
  99         GBR_init(mu_F[1]);
 100         GBR_init(two);
 101         GBR_init(one);
 102
 103         b_tmp = isl_vec_alloc(ctx, dim);
 104         if (!b_tmp)
 105                 goto error;
 106
 107         F = isl_alloc_array(ctx, GBR_type, n_bounded);
 108         alpha_buffer[0] = isl_alloc_array(ctx, GBR_type, n_bounded);
 109         alpha_buffer[1] = isl_alloc_array(ctx, GBR_type, n_bounded);
 110         alpha_saved = alpha_buffer[0];
 111
 112         if (!F || !alpha_buffer[0] || !alpha_buffer[1])
 113                 goto error;
 114
 115         for (i = 0; i < n_bounded; ++i) {
 116                 GBR_init(F[i]);
 117                 GBR_init(alpha_buffer[0][i]);
 118                 GBR_init(alpha_buffer[1][i]);
 119         }
 120
 121         GBR_set_ui(two, 2);
 122         GBR_set_ui(one, 1);
 123
 124         lp = GBR_lp_init(tab);
 125         if (!lp)
 126                 goto error;
 127
 128         i = tab->n_zero;
 129
 130         GBR_lp_set_obj(lp, B->row[1+i]+1, dim);
 131         ctx->stats->gbr_solved_lps++;
 132         unbounded = GBR_lp_solve(lp);
 133         isl_assert(ctx, !unbounded, goto error);
 134         GBR_lp_get_obj_val(lp, &F[i]);
 135
 136         if (GBR_lt(F[i], one)) {
 137                 if (!GBR_is_zero(F[i])) {
 138                         empty = GBR_lp_cut(lp, B->row[1+i]+1);
 139                         if (empty)
 140                                 goto done;
 141                         GBR_set_ui(F[i], 0);
 142                 }
 143                 tab->n_zero++;
 144         }
 145
 146         do {
 147                 if (i+1 == tab->n_zero) {
 148                         GBR_lp_set_obj(lp, B->row[1+i+1]+1, dim);
 149                         ctx->stats->gbr_solved_lps++;
 150                         unbounded = GBR_lp_solve(lp);
 151                         isl_assert(ctx, !unbounded, goto error);
 152                         GBR_lp_get_obj_val(lp, &F_new);
 153                         fixed = GBR_lp_is_fixed(lp);
 154                         GBR_set_ui(alpha, 0);
 155                 } else
 156                 if (use_saved) {
 157                         row = GBR_lp_next_row(lp);
 158                         GBR_set(F_new, F_saved);
 159                         fixed = fixed_saved;
 160                         GBR_set(alpha, alpha_saved[i]);
 161                 } else {
 162                         row = GBR_lp_add_row(lp, B->row[1+i]+1, dim);
 163                         GBR_lp_set_obj(lp, B->row[1+i+1]+1, dim);
 164                         ctx->stats->gbr_solved_lps++;
 165                         unbounded = GBR_lp_solve(lp);
 166                         isl_assert(ctx, !unbounded, goto error);
 167                         GBR_lp_get_obj_val(lp, &F_new);
 168                         fixed = GBR_lp_is_fixed(lp);
 169
 170                         GBR_lp_get_alpha(lp, row, &alpha);
 171
 172                         if (i > 0)
 173                                 save_alpha(lp, row-i, i, alpha_saved);
 174
 175                         if (GBR_lp_del_row(lp) < 0)
 176                                 goto error;
 177                 }
 178                 GBR_set(F[i+1], F_new);
 179
 180                 GBR_floor(mu[0], alpha);
 181                 GBR_ceil(mu[1], alpha);
 182
 183                 if (isl_int_eq(mu[0], mu[1]))
 184                         isl_int_set(tmp, mu[0]);
 185                 else {
 186                         int j;
 187
 188                         for (j = 0; j <= 1; ++j) {
 189                                 isl_int_set(tmp, mu[j]);
 190                                 isl_seq_combine(b_tmp->el,
 191                                                 ctx->one, B->row[1+i+1]+1,
 192                                                 tmp, B->row[1+i]+1, dim);
 193                                 GBR_lp_set_obj(lp, b_tmp->el, dim);
 194                                 ctx->stats->gbr_solved_lps++;
 195                                 unbounded = GBR_lp_solve(lp);
 196                                 isl_assert(ctx, !unbounded, goto error);
 197                                 GBR_lp_get_obj_val(lp, &mu_F[j]);
 198                                 mu_fixed[j] = GBR_lp_is_fixed(lp);
 199                                 if (i > 0)
 200                                         save_alpha(lp, row-i, i, alpha_buffer[j]);
 201                         }
 202
 203                         if (GBR_lt(mu_F[0], mu_F[1]))
 204                                 j = 0;
 205                         else
 206                                 j = 1;
 207
 208                         isl_int_set(tmp, mu[j]);
 209                         GBR_set(F_new, mu_F[j]);
 210                         fixed = mu_fixed[j];
 211                         alpha_saved = alpha_buffer[j];
 212                 }
 213                 isl_seq_combine(B->row[1+i+1]+1, ctx->one, B->row[1+i+1]+1,
 214                                 tmp, B->row[1+i]+1, dim);
 215
 216                 if (i+1 == tab->n_zero && fixed) {
 217                         if (!GBR_is_zero(F[i+1])) {
 218                                 empty = GBR_lp_cut(lp, B->row[1+i+1]+1);
 219                                 if (empty)
 220                                         goto done;
 221                                 GBR_set_ui(F[i+1], 0);
 222                         }
 223                         tab->n_zero++;
 224                 }
 225
 226                 GBR_set(F_old, F[i]);
 227
 228                 use_saved = 0;
 229                 /* mu_F[0] = 4 * F_new; mu_F[1] = 3 * F_old */
 230                 GBR_set_ui(mu_F[0], 4);
 231                 GBR_mul(mu_F[0], mu_F[0], F_new);
 232                 GBR_set_ui(mu_F[1], 3);
 233                 GBR_mul(mu_F[1], mu_F[1], F_old);
 234                 if (GBR_lt(mu_F[0], mu_F[1])) {
 235                         B = isl_mat_swap_rows(B, 1 + i, 1 + i + 1);
 236                         if (i > tab->n_zero) {
 237                                 use_saved = 1;
 238                                 GBR_set(F_saved, F_new);
 239                                 fixed_saved = fixed;
 240                                 if (GBR_lp_del_row(lp) < 0)
 241                                         goto error;
 242                                 --i;
 243                         } else {
 244                                 GBR_set(F[tab->n_zero], F_new);
 245                                 if (gbr_only_first && GBR_lt(F[tab->n_zero], two))
 246                                         break;
 247
 248                                 if (fixed) {
 249                                         if (!GBR_is_zero(F[tab->n_zero])) {
 250                                                 empty = GBR_lp_cut(lp, B->row[1+tab->n_zero]+1);
 251                                                 if (empty)
 252                                                         goto done;
 253                                                 GBR_set_ui(F[tab->n_zero], 0);
 254                                         }
 255                                         tab->n_zero++;
 256                                 }
 257                         }
 258                 } else {
 259                         GBR_lp_add_row(lp, B->row[1+i]+1, dim);
 260                         ++i;
 261                 }
 262         } while (i < n_bounded - 1);
 263
 264         if (0) {
 265 done:
 266                 if (empty < 0) {
 267 error:
 268                         isl_mat_free(B);
 269                         B = NULL;
 270                 }
 271         }
 272
 273         GBR_lp_delete(lp);
 274
 275         if (alpha_buffer[1])
 276                 for (i = 0; i < n_bounded; ++i) {
 277                         GBR_clear(F[i]);
 278                         GBR_clear(alpha_buffer[0][i]);
 279                         GBR_clear(alpha_buffer[1][i]);
 280                 }
 281         free(F);
 282         free(alpha_buffer[0]);
 283         free(alpha_buffer[1]);
 284
 285         isl_vec_free(b_tmp);
 286
 287         GBR_clear(alpha);
 288         GBR_clear(F_old);
 289         GBR_clear(F_new);
 290         GBR_clear(F_saved);
 291         GBR_clear(mu_F[0]);
 292         GBR_clear(mu_F[1]);
 293         GBR_clear(two);
 294         GBR_clear(one);
 295
 296         isl_int_clear(tmp);
 297         isl_int_clear(mu[0]);
 298         isl_int_clear(mu[1]);
 299
 300         tab->basis = B;
 301
 302         return tab;
 303 }
 304
 305 struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset)
 306 {
 307         struct isl_mat *basis;
 308         struct isl_tab *tab;
 309
 310         isl_assert(bset->ctx, bset->n_eq == 0, return NULL);
 311
 312         tab = isl_tab_from_basic_set(bset);
 313         tab->basis = isl_mat_identity(bset->ctx, 1 + tab->n_var);
 314         tab = isl_tab_compute_reduced_basis(tab);
 315         if (!tab)
 316                 return NULL;
 317
 318         basis = isl_mat_copy(tab->basis);
 319
 320         isl_tab_free(tab);
 321
 322         return basis;
 323 }