deprecate isl_basic_set_drop_constraint
[isl.git] / basis_reduction_templ.c
blob98d8141372b017087f628d04cd17b4bddeb06387
1 /*
2 * Copyright 2006-2007 Universiteit Leiden
3 * Copyright 2008-2009 Katholieke Universiteit Leuven
5 * Use of this software is governed by the MIT license
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
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"
20 static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha)
22 int i;
24 for (i = 0; i < n; ++i)
25 GBR_lp_get_alpha(lp, first + i, &alpha[i]);
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 affine
30 * 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 that
34 * have been detected in the first rows of the new basis.
35 * The final tab->n_unbounded rows of the basis are assumed to correspond
36 * to unbounded directions and are also left untouched.
37 * In particular this means that the remaining rows are assumed to
38 * correspond to bounded directions.
40 * This function implements the algorithm described in
41 * "An Implementation of the Generalized Basis Reduction Algorithm
42 * for Integer Programming" of Cook el al. to compute a reduced basis.
43 * We use \epsilon = 1/4.
45 * If ctx->opt->gbr_only_first is set, the user is only interested
46 * in the first direction. In this case we stop the basis reduction when
47 * the width in the first direction becomes smaller than 2.
49 struct isl_tab *isl_tab_compute_reduced_basis(struct isl_tab *tab)
51 unsigned dim;
52 struct isl_ctx *ctx;
53 struct isl_mat *B;
54 int unbounded;
55 int i;
56 GBR_LP *lp = NULL;
57 GBR_type F_old, alpha, F_new;
58 int row;
59 isl_int tmp;
60 struct isl_vec *b_tmp;
61 GBR_type *F = NULL;
62 GBR_type *alpha_buffer[2] = { NULL, NULL };
63 GBR_type *alpha_saved;
64 GBR_type F_saved;
65 int use_saved = 0;
66 isl_int mu[2];
67 GBR_type mu_F[2];
68 GBR_type two;
69 GBR_type one;
70 int empty = 0;
71 int fixed = 0;
72 int fixed_saved = 0;
73 int mu_fixed[2];
74 int n_bounded;
75 int gbr_only_first;
77 if (!tab)
78 return NULL;
80 if (tab->empty)
81 return tab;
83 ctx = tab->mat->ctx;
84 gbr_only_first = ctx->opt->gbr_only_first;
85 dim = tab->n_var;
86 B = tab->basis;
87 if (!B)
88 return tab;
90 n_bounded = dim - tab->n_unbounded;
91 if (n_bounded <= tab->n_zero + 1)
92 return tab;
94 isl_int_init(tmp);
95 isl_int_init(mu[0]);
96 isl_int_init(mu[1]);
98 GBR_init(alpha);
99 GBR_init(F_old);
100 GBR_init(F_new);
101 GBR_init(F_saved);
102 GBR_init(mu_F[0]);
103 GBR_init(mu_F[1]);
104 GBR_init(two);
105 GBR_init(one);
107 b_tmp = isl_vec_alloc(ctx, dim);
108 if (!b_tmp)
109 goto error;
111 F = isl_alloc_array(ctx, GBR_type, n_bounded);
112 alpha_buffer[0] = isl_alloc_array(ctx, GBR_type, n_bounded);
113 alpha_buffer[1] = isl_alloc_array(ctx, GBR_type, n_bounded);
114 alpha_saved = alpha_buffer[0];
116 if (!F || !alpha_buffer[0] || !alpha_buffer[1])
117 goto error;
119 for (i = 0; i < n_bounded; ++i) {
120 GBR_init(F[i]);
121 GBR_init(alpha_buffer[0][i]);
122 GBR_init(alpha_buffer[1][i]);
125 GBR_set_ui(two, 2);
126 GBR_set_ui(one, 1);
128 lp = GBR_lp_init(tab);
129 if (!lp)
130 goto error;
132 i = tab->n_zero;
134 GBR_lp_set_obj(lp, B->row[1+i]+1, dim);
135 ctx->stats->gbr_solved_lps++;
136 unbounded = GBR_lp_solve(lp);
137 isl_assert(ctx, !unbounded, goto error);
138 GBR_lp_get_obj_val(lp, &F[i]);
140 if (GBR_lt(F[i], one)) {
141 if (!GBR_is_zero(F[i])) {
142 empty = GBR_lp_cut(lp, B->row[1+i]+1);
143 if (empty)
144 goto done;
145 GBR_set_ui(F[i], 0);
147 tab->n_zero++;
150 do {
151 if (i+1 == tab->n_zero) {
152 GBR_lp_set_obj(lp, B->row[1+i+1]+1, dim);
153 ctx->stats->gbr_solved_lps++;
154 unbounded = GBR_lp_solve(lp);
155 isl_assert(ctx, !unbounded, goto error);
156 GBR_lp_get_obj_val(lp, &F_new);
157 fixed = GBR_lp_is_fixed(lp);
158 GBR_set_ui(alpha, 0);
159 } else
160 if (use_saved) {
161 row = GBR_lp_next_row(lp);
162 GBR_set(F_new, F_saved);
163 fixed = fixed_saved;
164 GBR_set(alpha, alpha_saved[i]);
165 } else {
166 row = GBR_lp_add_row(lp, B->row[1+i]+1, dim);
167 GBR_lp_set_obj(lp, B->row[1+i+1]+1, dim);
168 ctx->stats->gbr_solved_lps++;
169 unbounded = GBR_lp_solve(lp);
170 isl_assert(ctx, !unbounded, goto error);
171 GBR_lp_get_obj_val(lp, &F_new);
172 fixed = GBR_lp_is_fixed(lp);
174 GBR_lp_get_alpha(lp, row, &alpha);
176 if (i > 0)
177 save_alpha(lp, row-i, i, alpha_saved);
179 if (GBR_lp_del_row(lp) < 0)
180 goto error;
182 GBR_set(F[i+1], F_new);
184 GBR_floor(mu[0], alpha);
185 GBR_ceil(mu[1], alpha);
187 if (isl_int_eq(mu[0], mu[1]))
188 isl_int_set(tmp, mu[0]);
189 else {
190 int j;
192 for (j = 0; j <= 1; ++j) {
193 isl_int_set(tmp, mu[j]);
194 isl_seq_combine(b_tmp->el,
195 ctx->one, B->row[1+i+1]+1,
196 tmp, B->row[1+i]+1, dim);
197 GBR_lp_set_obj(lp, b_tmp->el, dim);
198 ctx->stats->gbr_solved_lps++;
199 unbounded = GBR_lp_solve(lp);
200 isl_assert(ctx, !unbounded, goto error);
201 GBR_lp_get_obj_val(lp, &mu_F[j]);
202 mu_fixed[j] = GBR_lp_is_fixed(lp);
203 if (i > 0)
204 save_alpha(lp, row-i, i, alpha_buffer[j]);
207 if (GBR_lt(mu_F[0], mu_F[1]))
208 j = 0;
209 else
210 j = 1;
212 isl_int_set(tmp, mu[j]);
213 GBR_set(F_new, mu_F[j]);
214 fixed = mu_fixed[j];
215 alpha_saved = alpha_buffer[j];
217 isl_seq_combine(B->row[1+i+1]+1, ctx->one, B->row[1+i+1]+1,
218 tmp, B->row[1+i]+1, dim);
220 if (i+1 == tab->n_zero && fixed) {
221 if (!GBR_is_zero(F[i+1])) {
222 empty = GBR_lp_cut(lp, B->row[1+i+1]+1);
223 if (empty)
224 goto done;
225 GBR_set_ui(F[i+1], 0);
227 tab->n_zero++;
230 GBR_set(F_old, F[i]);
232 use_saved = 0;
233 /* mu_F[0] = 4 * F_new; mu_F[1] = 3 * F_old */
234 GBR_set_ui(mu_F[0], 4);
235 GBR_mul(mu_F[0], mu_F[0], F_new);
236 GBR_set_ui(mu_F[1], 3);
237 GBR_mul(mu_F[1], mu_F[1], F_old);
238 if (GBR_lt(mu_F[0], mu_F[1])) {
239 B = isl_mat_swap_rows(B, 1 + i, 1 + i + 1);
240 if (i > tab->n_zero) {
241 use_saved = 1;
242 GBR_set(F_saved, F_new);
243 fixed_saved = fixed;
244 if (GBR_lp_del_row(lp) < 0)
245 goto error;
246 --i;
247 } else {
248 GBR_set(F[tab->n_zero], F_new);
249 if (gbr_only_first && GBR_lt(F[tab->n_zero], two))
250 break;
252 if (fixed) {
253 if (!GBR_is_zero(F[tab->n_zero])) {
254 empty = GBR_lp_cut(lp, B->row[1+tab->n_zero]+1);
255 if (empty)
256 goto done;
257 GBR_set_ui(F[tab->n_zero], 0);
259 tab->n_zero++;
262 } else {
263 GBR_lp_add_row(lp, B->row[1+i]+1, dim);
264 ++i;
266 } while (i < n_bounded - 1);
268 if (0) {
269 done:
270 if (empty < 0) {
271 error:
272 isl_mat_free(B);
273 B = NULL;
277 GBR_lp_delete(lp);
279 if (alpha_buffer[1])
280 for (i = 0; i < n_bounded; ++i) {
281 GBR_clear(F[i]);
282 GBR_clear(alpha_buffer[0][i]);
283 GBR_clear(alpha_buffer[1][i]);
285 free(F);
286 free(alpha_buffer[0]);
287 free(alpha_buffer[1]);
289 isl_vec_free(b_tmp);
291 GBR_clear(alpha);
292 GBR_clear(F_old);
293 GBR_clear(F_new);
294 GBR_clear(F_saved);
295 GBR_clear(mu_F[0]);
296 GBR_clear(mu_F[1]);
297 GBR_clear(two);
298 GBR_clear(one);
300 isl_int_clear(tmp);
301 isl_int_clear(mu[0]);
302 isl_int_clear(mu[1]);
304 tab->basis = B;
306 return tab;
309 /* Compute an affine form of a reduced basis of the given basic
310 * non-parametric set, which is assumed to be bounded and not
311 * include any integer divisions.
312 * The first column and the first row correspond to the constant term.
314 * If the input contains any equalities, we first create an initial
315 * basis with the equalities first. Otherwise, we start off with
316 * the identity matrix.
318 struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset)
320 struct isl_mat *basis;
321 struct isl_tab *tab;
323 if (!bset)
324 return NULL;
326 if (isl_basic_set_dim(bset, isl_dim_div) != 0)
327 isl_die(bset->ctx, isl_error_invalid,
328 "no integer division allowed", return NULL);
329 if (isl_basic_set_dim(bset, isl_dim_param) != 0)
330 isl_die(bset->ctx, isl_error_invalid,
331 "no parameters allowed", return NULL);
333 tab = isl_tab_from_basic_set(bset, 0);
334 if (!tab)
335 return NULL;
337 if (bset->n_eq == 0)
338 tab->basis = isl_mat_identity(bset->ctx, 1 + tab->n_var);
339 else {
340 isl_mat *eq;
341 unsigned nvar = isl_basic_set_total_dim(bset);
342 eq = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, bset->n_eq,
343 1, nvar);
344 eq = isl_mat_left_hermite(eq, 0, NULL, &tab->basis);
345 tab->basis = isl_mat_lin_to_aff(tab->basis);
346 tab->n_zero = bset->n_eq;
347 isl_mat_free(eq);
349 tab = isl_tab_compute_reduced_basis(tab);
350 if (!tab)
351 return NULL;
353 basis = isl_mat_copy(tab->basis);
355 isl_tab_free(tab);
357 return basis;