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