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