basis_reduction_templ.c

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