Line data Source code
1 : /*
2 : * Copyright 2006-2007 Universiteit Leiden
3 : * Copyright 2008-2009 Katholieke Universiteit Leuven
4 : *
5 : * Use of this software is governed by the MIT license
6 : *
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
11 : */
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 :
20 53833066 : static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha)
21 : {
22 : int i;
23 :
24 165713026 : for (i = 0; i < n; ++i)
25 111879960 : GBR_lp_get_alpha(lp, first + i, &alpha[i]);
26 53833066 : }
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 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.
39 : *
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.
44 : *
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.
48 : */
49 3355293 : struct 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 3355293 : 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 3355293 : GBR_type *F = NULL;
61 3355293 : GBR_type *alpha_buffer[2] = { NULL, NULL };
62 : GBR_type *alpha_saved;
63 : GBR_type F_saved;
64 3355293 : int use_saved = 0;
65 : isl_int mu[2];
66 : GBR_type mu_F[2];
67 : GBR_type two;
68 : GBR_type one;
69 3355293 : int empty = 0;
70 3355293 : int fixed = 0;
71 3355293 : int fixed_saved = 0;
72 : int mu_fixed[2];
73 : int n_bounded;
74 : int gbr_only_first;
75 :
76 3355293 : if (!tab)
77 0 : return NULL;
78 :
79 3355293 : if (tab->empty)
80 0 : return tab;
81 :
82 3355293 : ctx = tab->mat->ctx;
83 3355293 : gbr_only_first = ctx->opt->gbr_only_first;
84 3355293 : dim = tab->n_var;
85 3355293 : B = tab->basis;
86 3355293 : if (!B)
87 0 : return tab;
88 :
89 3355293 : n_bounded = dim - tab->n_unbounded;
90 3355293 : if (n_bounded <= tab->n_zero + 1)
91 0 : return tab;
92 :
93 3355293 : isl_int_init(tmp);
94 3355293 : isl_int_init(mu[0]);
95 3355293 : isl_int_init(mu[1]);
96 :
97 3355293 : GBR_init(alpha);
98 3355293 : GBR_init(F_old);
99 3355293 : GBR_init(F_new);
100 3355293 : GBR_init(F_saved);
101 3355293 : GBR_init(mu_F[0]);
102 3355293 : GBR_init(mu_F[1]);
103 3355293 : GBR_init(two);
104 3355293 : GBR_init(one);
105 :
106 3355293 : b_tmp = isl_vec_alloc(ctx, dim);
107 3355293 : if (!b_tmp)
108 0 : goto error;
109 :
110 3355293 : F = isl_alloc_array(ctx, GBR_type, n_bounded);
111 3355293 : alpha_buffer[0] = isl_alloc_array(ctx, GBR_type, n_bounded);
112 3355293 : alpha_buffer[1] = isl_alloc_array(ctx, GBR_type, n_bounded);
113 3355293 : alpha_saved = alpha_buffer[0];
114 :
115 3355293 : if (!F || !alpha_buffer[0] || !alpha_buffer[1])
116 : goto error;
117 :
118 20477723 : for (i = 0; i < n_bounded; ++i) {
119 17122430 : GBR_init(F[i]);
120 17122430 : GBR_init(alpha_buffer[0][i]);
121 17122430 : GBR_init(alpha_buffer[1][i]);
122 : }
123 :
124 3355293 : GBR_set_ui(two, 2);
125 3355293 : GBR_set_ui(one, 1);
126 :
127 3355293 : lp = GBR_lp_init(tab);
128 3355293 : if (!lp)
129 0 : goto error;
130 :
131 3355293 : i = tab->n_zero;
132 :
133 3355293 : GBR_lp_set_obj(lp, B->row[1+i]+1, dim);
134 3355293 : ctx->stats->gbr_solved_lps++;
135 3355293 : if (GBR_lp_solve(lp) < 0)
136 0 : goto error;
137 3355293 : GBR_lp_get_obj_val(lp, &F[i]);
138 :
139 3355293 : if (GBR_lt(F[i], one)) {
140 0 : if (!GBR_is_zero(F[i])) {
141 0 : empty = GBR_lp_cut(lp, B->row[1+i]+1);
142 0 : if (empty)
143 0 : goto done;
144 0 : GBR_set_ui(F[i], 0);
145 : }
146 0 : tab->n_zero++;
147 : }
148 :
149 : do {
150 32810237 : if (i+1 == tab->n_zero) {
151 0 : GBR_lp_set_obj(lp, B->row[1+i+1]+1, dim);
152 0 : ctx->stats->gbr_solved_lps++;
153 0 : if (GBR_lp_solve(lp) < 0)
154 0 : goto error;
155 0 : GBR_lp_get_obj_val(lp, &F_new);
156 0 : fixed = GBR_lp_is_fixed(lp);
157 0 : GBR_set_ui(alpha, 0);
158 : } else
159 32810237 : if (use_saved) {
160 11186262 : row = GBR_lp_next_row(lp);
161 11186262 : GBR_set(F_new, F_saved);
162 11186262 : fixed = fixed_saved;
163 11186262 : GBR_set(alpha, alpha_saved[i]);
164 : } else {
165 21623975 : row = GBR_lp_add_row(lp, B->row[1+i]+1, dim);
166 21623975 : GBR_lp_set_obj(lp, B->row[1+i+1]+1, dim);
167 21623975 : ctx->stats->gbr_solved_lps++;
168 21623975 : if (GBR_lp_solve(lp) < 0)
169 0 : goto error;
170 21623975 : GBR_lp_get_obj_val(lp, &F_new);
171 21623975 : fixed = GBR_lp_is_fixed(lp);
172 :
173 21623975 : GBR_lp_get_alpha(lp, row, &alpha);
174 :
175 21623975 : if (i > 0)
176 17107750 : save_alpha(lp, row-i, i, alpha_saved);
177 :
178 21623975 : if (GBR_lp_del_row(lp) < 0)
179 0 : goto error;
180 : }
181 32810237 : GBR_set(F[i+1], F_new);
182 :
183 32810237 : GBR_floor(mu[0], alpha);
184 32810237 : GBR_ceil(mu[1], alpha);
185 :
186 32810237 : if (isl_int_eq(mu[0], mu[1]))
187 9318367 : isl_int_set(tmp, mu[0]);
188 : else {
189 : int j;
190 :
191 70475610 : for (j = 0; j <= 1; ++j) {
192 46983740 : isl_int_set(tmp, mu[j]);
193 140951220 : isl_seq_combine(b_tmp->el,
194 93967480 : ctx->one, B->row[1+i+1]+1,
195 46983740 : tmp, B->row[1+i]+1, dim);
196 46983740 : GBR_lp_set_obj(lp, b_tmp->el, dim);
197 46983740 : ctx->stats->gbr_solved_lps++;
198 46983740 : if (GBR_lp_solve(lp) < 0)
199 0 : goto error;
200 46983740 : GBR_lp_get_obj_val(lp, &mu_F[j]);
201 46983740 : mu_fixed[j] = GBR_lp_is_fixed(lp);
202 46983740 : if (i > 0)
203 36725316 : save_alpha(lp, row-i, i, alpha_buffer[j]);
204 : }
205 :
206 23491870 : if (GBR_lt(mu_F[0], mu_F[1]))
207 13762644 : j = 0;
208 : else
209 9729226 : j = 1;
210 :
211 23491870 : isl_int_set(tmp, mu[j]);
212 23491870 : GBR_set(F_new, mu_F[j]);
213 23491870 : fixed = mu_fixed[j];
214 23491870 : alpha_saved = alpha_buffer[j];
215 : }
216 32810237 : isl_seq_combine(B->row[1+i+1]+1, ctx->one, B->row[1+i+1]+1,
217 32810237 : tmp, B->row[1+i]+1, dim);
218 :
219 32810237 : if (i+1 == tab->n_zero && fixed) {
220 0 : if (!GBR_is_zero(F[i+1])) {
221 0 : empty = GBR_lp_cut(lp, B->row[1+i+1]+1);
222 0 : if (empty)
223 0 : goto done;
224 0 : GBR_set_ui(F[i+1], 0);
225 : }
226 0 : tab->n_zero++;
227 : }
228 :
229 32810237 : GBR_set(F_old, F[i]);
230 :
231 32810237 : use_saved = 0;
232 : /* mu_F[0] = 4 * F_new; mu_F[1] = 3 * F_old */
233 32810237 : GBR_set_ui(mu_F[0], 4);
234 32810237 : GBR_mul(mu_F[0], mu_F[0], F_new);
235 32810237 : GBR_set_ui(mu_F[1], 3);
236 32810237 : GBR_mul(mu_F[1], mu_F[1], F_old);
237 32810237 : if (GBR_lt(mu_F[0], mu_F[1])) {
238 15463151 : B = isl_mat_swap_rows(B, 1 + i, 1 + i + 1);
239 15463151 : if (i > tab->n_zero) {
240 11186262 : use_saved = 1;
241 11186262 : GBR_set(F_saved, F_new);
242 11186262 : fixed_saved = fixed;
243 11186262 : if (GBR_lp_del_row(lp) < 0)
244 0 : goto error;
245 11186262 : --i;
246 : } else {
247 4276889 : GBR_set(F[tab->n_zero], F_new);
248 4276889 : if (gbr_only_first && GBR_lt(F[tab->n_zero], two))
249 1829002 : break;
250 :
251 2447887 : if (fixed) {
252 0 : if (!GBR_is_zero(F[tab->n_zero])) {
253 0 : empty = GBR_lp_cut(lp, B->row[1+tab->n_zero]+1);
254 0 : if (empty)
255 0 : goto done;
256 0 : GBR_set_ui(F[tab->n_zero], 0);
257 : }
258 0 : tab->n_zero++;
259 : }
260 : }
261 : } else {
262 17347086 : GBR_lp_add_row(lp, B->row[1+i]+1, dim);
263 17347086 : ++i;
264 : }
265 30981235 : } while (i < n_bounded - 1);
266 :
267 : if (0) {
268 : done:
269 0 : if (empty < 0) {
270 : error:
271 0 : isl_mat_free(B);
272 0 : B = NULL;
273 : }
274 : }
275 :
276 3355293 : GBR_lp_delete(lp);
277 :
278 3355293 : if (alpha_buffer[1])
279 20477723 : for (i = 0; i < n_bounded; ++i) {
280 17122430 : GBR_clear(F[i]);
281 17122430 : GBR_clear(alpha_buffer[0][i]);
282 17122430 : GBR_clear(alpha_buffer[1][i]);
283 : }
284 3355293 : free(F);
285 3355293 : free(alpha_buffer[0]);
286 3355293 : free(alpha_buffer[1]);
287 :
288 3355293 : isl_vec_free(b_tmp);
289 :
290 3355293 : GBR_clear(alpha);
291 3355293 : GBR_clear(F_old);
292 3355293 : GBR_clear(F_new);
293 3355293 : GBR_clear(F_saved);
294 3355293 : GBR_clear(mu_F[0]);
295 3355293 : GBR_clear(mu_F[1]);
296 3355293 : GBR_clear(two);
297 3355293 : GBR_clear(one);
298 :
299 3355293 : isl_int_clear(tmp);
300 3355293 : isl_int_clear(mu[0]);
301 3355293 : isl_int_clear(mu[1]);
302 :
303 3355293 : tab->basis = B;
304 :
305 3355293 : return tab;
306 : }
307 :
308 : /* Compute an affine form of a reduced basis of the given basic
309 : * non-parametric set, which is assumed to be bounded and not
310 : * include any integer divisions.
311 : * The first column and the first row correspond to the constant term.
312 : *
313 : * If the input contains any equalities, we first create an initial
314 : * basis with the equalities first. Otherwise, we start off with
315 : * the identity matrix.
316 : */
317 0 : __isl_give isl_mat *isl_basic_set_reduced_basis(__isl_keep isl_basic_set *bset)
318 : {
319 : struct isl_mat *basis;
320 : struct isl_tab *tab;
321 :
322 0 : if (!bset)
323 0 : return NULL;
324 :
325 0 : if (isl_basic_set_dim(bset, isl_dim_div) != 0)
326 0 : isl_die(bset->ctx, isl_error_invalid,
327 : "no integer division allowed", return NULL);
328 0 : if (isl_basic_set_dim(bset, isl_dim_param) != 0)
329 0 : isl_die(bset->ctx, isl_error_invalid,
330 : "no parameters allowed", return NULL);
331 :
332 0 : tab = isl_tab_from_basic_set(bset, 0);
333 0 : if (!tab)
334 0 : return NULL;
335 :
336 0 : if (bset->n_eq == 0)
337 0 : tab->basis = isl_mat_identity(bset->ctx, 1 + tab->n_var);
338 : else {
339 : isl_mat *eq;
340 0 : unsigned nvar = isl_basic_set_total_dim(bset);
341 0 : eq = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, bset->n_eq,
342 : 1, nvar);
343 0 : eq = isl_mat_left_hermite(eq, 0, NULL, &tab->basis);
344 0 : tab->basis = isl_mat_lin_to_aff(tab->basis);
345 0 : tab->n_zero = bset->n_eq;
346 0 : isl_mat_free(eq);
347 : }
348 0 : tab = isl_tab_compute_reduced_basis(tab);
349 0 : if (!tab)
350 0 : return NULL;
351 :
352 0 : basis = isl_mat_copy(tab->basis);
353 :
354 0 : isl_tab_free(tab);
355 :
356 0 : return basis;
357 : }
|
