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_options_private.h>
17#include "isl_basis_reduction.h"
18
19static void save_alpha(GBR_LP *lp, int first, int n, GBR_type *alpha)
20{
21	int i;
22
23	for (i = 0; i < n; ++i)
24		GBR_lp_get_alpha(lp, first + i, &alpha[i]);
25}
26
27/* Compute a reduced basis for the set represented by the tableau "tab".
28 * tab->basis, which must be initialized by the calling function to an affine
29 * unimodular basis, is updated to reflect the reduced basis.
30 * The first tab->n_zero rows of the basis (ignoring the constant row)
31 * are assumed to correspond to equalities and are left untouched.
32 * tab->n_zero is updated to reflect any additional equalities that
33 * have been detected in the first rows of the new basis.
34 * The final tab->n_unbounded rows of the basis are assumed to correspond
35 * to unbounded directions and are also left untouched.
36 * In particular this means that the remaining rows are assumed to
37 * correspond to bounded directions.
38 *
39 * This function implements the algorithm described in
40 * "An Implementation of the Generalized Basis Reduction Algorithm
41 *  for Integer Programming" of Cook el al. to compute a reduced basis.
42 * We use \epsilon = 1/4.
43 *
44 * If ctx->opt->gbr_only_first is set, the user is only interested
45 * in the first direction.  In this case we stop the basis reduction when
46 * the width in the first direction becomes smaller than 2.
47 */
48struct isl_tab *isl_tab_compute_reduced_basis(struct isl_tab *tab)
49{
50	unsigned dim;
51	struct isl_ctx *ctx;
52	struct isl_mat *B;
53	int unbounded;
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	unbounded = GBR_lp_solve(lp);
136	isl_assert(ctx, !unbounded, 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			unbounded = GBR_lp_solve(lp);
154			isl_assert(ctx, !unbounded, 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
159		if (use_saved) {
160			row = GBR_lp_next_row(lp);
161			GBR_set(F_new, F_saved);
162			fixed = fixed_saved;
163			GBR_set(alpha, alpha_saved[i]);
164		} else {
165			row = GBR_lp_add_row(lp, B->row[1+i]+1, dim);
166			GBR_lp_set_obj(lp, B->row[1+i+1]+1, dim);
167			ctx->stats->gbr_solved_lps++;
168			unbounded = GBR_lp_solve(lp);
169			isl_assert(ctx, !unbounded, goto error);
170			GBR_lp_get_obj_val(lp, &F_new);
171			fixed = GBR_lp_is_fixed(lp);
172
173			GBR_lp_get_alpha(lp, row, &alpha);
174
175			if (i > 0)
176				save_alpha(lp, row-i, i, alpha_saved);
177
178			if (GBR_lp_del_row(lp) < 0)
179				goto error;
180		}
181		GBR_set(F[i+1], F_new);
182
183		GBR_floor(mu[0], alpha);
184		GBR_ceil(mu[1], alpha);
185
186		if (isl_int_eq(mu[0], mu[1]))
187			isl_int_set(tmp, mu[0]);
188		else {
189			int j;
190
191			for (j = 0; j <= 1; ++j) {
192				isl_int_set(tmp, mu[j]);
193				isl_seq_combine(b_tmp->el,
194						ctx->one, B->row[1+i+1]+1,
195						tmp, B->row[1+i]+1, dim);
196				GBR_lp_set_obj(lp, b_tmp->el, dim);
197				ctx->stats->gbr_solved_lps++;
198				unbounded = GBR_lp_solve(lp);
199				isl_assert(ctx, !unbounded, goto error);
200				GBR_lp_get_obj_val(lp, &mu_F[j]);
201				mu_fixed[j] = GBR_lp_is_fixed(lp);
202				if (i > 0)
203					save_alpha(lp, row-i, i, alpha_buffer[j]);
204			}
205
206			if (GBR_lt(mu_F[0], mu_F[1]))
207				j = 0;
208			else
209				j = 1;
210
211			isl_int_set(tmp, mu[j]);
212			GBR_set(F_new, mu_F[j]);
213			fixed = mu_fixed[j];
214			alpha_saved = alpha_buffer[j];
215		}
216		isl_seq_combine(B->row[1+i+1]+1, ctx->one, B->row[1+i+1]+1,
217				tmp, B->row[1+i]+1, dim);
218
219		if (i+1 == tab->n_zero && fixed) {
220			if (!GBR_is_zero(F[i+1])) {
221				empty = GBR_lp_cut(lp, B->row[1+i+1]+1);
222				if (empty)
223					goto done;
224				GBR_set_ui(F[i+1], 0);
225			}
226			tab->n_zero++;
227		}
228
229		GBR_set(F_old, F[i]);
230
231		use_saved = 0;
232		/* mu_F[0] = 4 * F_new; mu_F[1] = 3 * F_old */
233		GBR_set_ui(mu_F[0], 4);
234		GBR_mul(mu_F[0], mu_F[0], F_new);
235		GBR_set_ui(mu_F[1], 3);
236		GBR_mul(mu_F[1], mu_F[1], F_old);
237		if (GBR_lt(mu_F[0], mu_F[1])) {
238			B = isl_mat_swap_rows(B, 1 + i, 1 + i + 1);
239			if (i > tab->n_zero) {
240				use_saved = 1;
241				GBR_set(F_saved, F_new);
242				fixed_saved = fixed;
243				if (GBR_lp_del_row(lp) < 0)
244					goto error;
245				--i;
246			} else {
247				GBR_set(F[tab->n_zero], F_new);
248				if (gbr_only_first && GBR_lt(F[tab->n_zero], two))
249					break;
250
251				if (fixed) {
252					if (!GBR_is_zero(F[tab->n_zero])) {
253						empty = GBR_lp_cut(lp, B->row[1+tab->n_zero]+1);
254						if (empty)
255							goto done;
256						GBR_set_ui(F[tab->n_zero], 0);
257					}
258					tab->n_zero++;
259				}
260			}
261		} else {
262			GBR_lp_add_row(lp, B->row[1+i]+1, dim);
263			++i;
264		}
265	} while (i < n_bounded - 1);
266
267	if (0) {
268done:
269		if (empty < 0) {
270error:
271			isl_mat_free(B);
272			B = NULL;
273		}
274	}
275
276	GBR_lp_delete(lp);
277
278	if (alpha_buffer[1])
279		for (i = 0; i < n_bounded; ++i) {
280			GBR_clear(F[i]);
281			GBR_clear(alpha_buffer[0][i]);
282			GBR_clear(alpha_buffer[1][i]);
283		}
284	free(F);
285	free(alpha_buffer[0]);
286	free(alpha_buffer[1]);
287
288	isl_vec_free(b_tmp);
289
290	GBR_clear(alpha);
291	GBR_clear(F_old);
292	GBR_clear(F_new);
293	GBR_clear(F_saved);
294	GBR_clear(mu_F[0]);
295	GBR_clear(mu_F[1]);
296	GBR_clear(two);
297	GBR_clear(one);
298
299	isl_int_clear(tmp);
300	isl_int_clear(mu[0]);
301	isl_int_clear(mu[1]);
302
303	tab->basis = B;
304
305	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 */
317struct isl_mat *isl_basic_set_reduced_basis(struct isl_basic_set *bset)
318{
319	struct isl_mat *basis;
320	struct isl_tab *tab;
321
322	if (!bset)
323		return NULL;
324
325	if (isl_basic_set_dim(bset, isl_dim_div) != 0)
326		isl_die(bset->ctx, isl_error_invalid,
327			"no integer division allowed", return NULL);
328	if (isl_basic_set_dim(bset, isl_dim_param) != 0)
329		isl_die(bset->ctx, isl_error_invalid,
330			"no parameters allowed", return NULL);
331
332	tab = isl_tab_from_basic_set(bset, 0);
333	if (!tab)
334		return NULL;
335
336	if (bset->n_eq == 0)
337		tab->basis = isl_mat_identity(bset->ctx, 1 + tab->n_var);
338	else {
339		isl_mat *eq;
340		unsigned nvar = isl_basic_set_total_dim(bset);
341		eq = isl_mat_sub_alloc6(bset->ctx, bset->eq, 0, bset->n_eq,
342					1, nvar);
343		eq = isl_mat_left_hermite(eq, 0, NULL, &tab->basis);
344		tab->basis = isl_mat_lin_to_aff(tab->basis);
345		tab->n_zero = bset->n_eq;
346		isl_mat_free(eq);
347	}
348	tab = isl_tab_compute_reduced_basis(tab);
349	if (!tab)
350		return NULL;
351
352	basis = isl_mat_copy(tab->basis);
353
354	isl_tab_free(tab);
355
356	return basis;
357}
358