1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
/*
* Copyright 2008-2009 Katholieke Universiteit Leuven
*
* Use of this software is governed by the MIT license
*
* Written by Sven Verdoolaege, K.U.Leuven, Departement
* Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
*/
#include <isl/map.h>
#include <isl/vec.h>
#include <isl/lp.h>
#include "isl_piplib.h"
#include "isl_map_piplib.h"
static void copy_solution(struct isl_vec *vec, int maximize, isl_int *opt,
isl_int *opt_denom, PipQuast *sol)
{
int i;
PipList *list;
isl_int tmp;
if (opt) {
if (opt_denom) {
isl_seq_cpy_from_pip(opt,
&sol->list->vector->the_vector[0], 1);
isl_seq_cpy_from_pip(opt_denom,
&sol->list->vector->the_deno[0], 1);
} else if (maximize)
mpz_fdiv_q(*opt, sol->list->vector->the_vector[0],
sol->list->vector->the_deno[0]);
else
mpz_cdiv_q(*opt, sol->list->vector->the_vector[0],
sol->list->vector->the_deno[0]);
}
if (!vec)
return;
isl_int_init(tmp);
isl_int_set_si(vec->el[0], 1);
for (i = 0, list = sol->list->next; list; ++i, list = list->next) {
isl_seq_cpy_from_pip(&vec->el[1 + i],
&list->vector->the_deno[0], 1);
isl_int_lcm(vec->el[0], vec->el[0], vec->el[1 + i]);
}
for (i = 0, list = sol->list->next; list; ++i, list = list->next) {
isl_seq_cpy_from_pip(&tmp, &list->vector->the_deno[0], 1);
isl_int_divexact(tmp, vec->el[0], tmp);
isl_seq_cpy_from_pip(&vec->el[1 + i],
&list->vector->the_vector[0], 1);
isl_int_mul(vec->el[1 + i], vec->el[1 + i], tmp);
}
isl_int_clear(tmp);
}
enum isl_lp_result isl_pip_solve_lp(struct isl_basic_map *bmap, int maximize,
isl_int *f, isl_int denom, isl_int *opt,
isl_int *opt_denom,
struct isl_vec **vec)
{
enum isl_lp_result res = isl_lp_ok;
PipMatrix *domain = NULL;
PipOptions *options;
PipQuast *sol;
unsigned total;
total = isl_basic_map_total_dim(bmap);
domain = isl_basic_map_to_pip(bmap, 0, 1, 0);
if (!domain)
goto error;
entier_set_si(domain->p[0][1], -1);
isl_int_set(domain->p[0][domain->NbColumns - 1], f[0]);
isl_seq_cpy_to_pip(domain->p[0]+2, f+1, total);
options = pip_options_init();
if (!options)
goto error;
options->Urs_unknowns = -1;
options->Maximize = maximize;
options->Nq = 0;
sol = pip_solve(domain, NULL, -1, options);
pip_options_free(options);
if (!sol)
goto error;
if (vec) {
isl_ctx *ctx = isl_basic_map_get_ctx(bmap);
*vec = isl_vec_alloc(ctx, 1 + total);
}
if (vec && !*vec)
res = isl_lp_error;
else if (!sol->list)
res = isl_lp_empty;
else if (entier_zero_p(sol->list->vector->the_deno[0]))
res = isl_lp_unbounded;
else
copy_solution(*vec, maximize, opt, opt_denom, sol);
pip_matrix_free(domain);
pip_quast_free(sol);
return res;
error:
if (domain)
pip_matrix_free(domain);
return isl_lp_error;
}
|
