isl_sample.c: drop_constraints_involving: avoid NULL pointer dereference
[isl.git] / basis_reduction_templ.c
blob305431f07e383a3a05f8b9cad21feb4bf9e8b884
1 /*
2 * Copyright 2006-2007 Universiteit Leiden
3 * Copyright 2008-2009 Katholieke Universiteit Leuven
5 * Use of this software is governed by the GNU LGPLv2.1 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_basis_reduction.h"
16 static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha)
18 int i;
20 for (i = 0; i < n; ++i)
21 GBR_lp_get_alpha(lp, first + i, &alpha[i]);
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.
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.
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.
45 struct isl_tab *isl_tab_compute_reduced_basis(struct isl_tab *tab)
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;
73 if (!tab)
74 return NULL;
76 if (tab->empty)
77 return tab;
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;
86 n_bounded = dim - tab->n_unbounded;
87 if (n_bounded <= tab->n_zero + 1)
88 return tab;
90 isl_int_init(tmp);
91 isl_int_init(mu[0]);
92 isl_int_init(mu[1]);
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);
103 b_tmp = isl_vec_alloc(ctx, dim);
104 if (!b_tmp)
105 goto error;
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];
112 if (!F || !alpha_buffer[0] || !alpha_buffer[1])
113 goto error;
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]);
121 GBR_set_ui(two, 2);
122 GBR_set_ui(one, 1);
124 lp = GBR_lp_init(tab);
125 if (!lp)
126 goto error;
128 i = tab->n_zero;
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]);
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);
143 tab->n_zero++;
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);
170 GBR_lp_get_alpha(lp, row, &alpha);
172 if (i > 0)
173 save_alpha(lp, row-i, i, alpha_saved);
175 if (GBR_lp_del_row(lp) < 0)
176 goto error;
178 GBR_set(F[i+1], F_new);
180 GBR_floor(mu[0], alpha);
181 GBR_ceil(mu[1], alpha);
183 if (isl_int_eq(mu[0], mu[1]))
184 isl_int_set(tmp, mu[0]);
185 else {
186 int j;
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]);
203 if (GBR_lt(mu_F[0], mu_F[1]))
204 j = 0;
205 else
206 j = 1;
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];
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);
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);
223 tab->n_zero++;
226 GBR_set(F_old, F[i]);
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;
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);
255 tab->n_zero++;
258 } else {
259 GBR_lp_add_row(lp, B->row[1+i]+1, dim);
260 ++i;
262 } while (i < n_bounded - 1);
264 if (0) {
265 done:
266 if (empty < 0) {
267 error:
268 isl_mat_free(B);
269 B = NULL;
273 GBR_lp_delete(lp);
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]);
281 free(F);
282 free(alpha_buffer[0]);
283 free(alpha_buffer[1]);
285 isl_vec_free(b_tmp);
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);
296 isl_int_clear(tmp);
297 isl_int_clear(mu[0]);
298 isl_int_clear(mu[1]);
300 tab->basis = B;
302 return tab;
305 struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset)
307 struct isl_mat *basis;
308 struct isl_tab *tab;
310 isl_assert(bset->ctx, bset->n_eq == 0, return NULL);
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;
318 basis = isl_mat_copy(tab->basis);
320 isl_tab_free(tab);
322 return basis;