4 #include <barvinok/options.h>
5 #include <barvinok/util.h>
8 #define ALLOCN(type,n) (type*)malloc((n) * sizeof(type))
10 #define EMPTY_DOMAIN -2
12 static LPX
*solve_lp(int dir
, Polyhedron
*P
, Value
*f
, Value denom
)
19 ind
= ALLOCN(int, 1+P
->Dimension
);
20 val
= ALLOCN(double, 1+P
->Dimension
);
21 lp
= lpx_create_prob();
22 lpx_set_obj_dir(lp
, dir
);
23 lpx_add_rows(lp
, P
->NbConstraints
);
24 lpx_add_cols(lp
, P
->Dimension
);
26 for (j
= 0; j
< P
->NbConstraints
; ++j
) {
27 int type
= j
< P
->NbEq
? LPX_FX
: LPX_LO
;
28 for (k
= 0, l
= 0; k
< P
->Dimension
; ++k
) {
29 if (value_zero_p(P
->Constraint
[j
][1+k
]))
32 val
[1+l
] = VALUE_TO_DOUBLE(P
->Constraint
[j
][1+k
]);
35 lpx_set_mat_row(lp
, 1+j
, l
, ind
, val
);
36 lpx_set_row_bnds(lp
, 1+j
, type
,
37 -VALUE_TO_DOUBLE(P
->Constraint
[j
][1+P
->Dimension
]), 0);
39 for (k
= 0, l
= 0; k
< P
->Dimension
; ++k
) {
40 lpx_set_col_bnds(lp
, 1+k
, LPX_FR
, 0, 0);
44 lpx_set_int_parm(lp
, LPX_K_MSGLEV
, 0);
46 /* objective function */
47 for (j
= 0; j
< P
->Dimension
; ++j
)
48 lpx_set_obj_coef(lp
, 1+j
, VALUE_TO_DOUBLE(f
[j
]) /
49 VALUE_TO_DOUBLE(denom
));
50 lpx_set_obj_coef(lp
, 0, VALUE_TO_DOUBLE(f
[P
->Dimension
]) /
51 VALUE_TO_DOUBLE(denom
));
59 static enum lp_result
polyhedron_affine_minmax(int dir
, Polyhedron
*P
,
60 Value
*f
, Value denom
, Value
*opt
)
62 enum lp_result res
= lp_ok
;
63 LPX
*lp
= solve_lp(dir
, P
, f
, denom
);
65 switch (lpx_get_status(lp
)) {
68 value_set_si(*opt
, (int)ceil(lpx_get_obj_val(lp
)-1e-10));
70 value_set_si(*opt
, (int)floor(lpx_get_obj_val(lp
)+1e-10));
85 static int polyhedron_affine_minmax_sign(int dir
, Polyhedron
*P
, Matrix
*T
,
91 assert(P
->Dimension
== T
->NbColumns
-1);
92 assert(T
->NbRows
== 2);
94 lp
= solve_lp(dir
, P
, T
->p
[0], T
->p
[1][P
->Dimension
]);
95 switch (lpx_get_status(lp
)) {
97 opt
= lpx_get_obj_val(lp
);
99 sign
= opt
< 0 ? -1 : opt
> 0 ? 1 : 0;
101 if (opt
< -0.5/VALUE_TO_DOUBLE(T
->p
[1][P
->Dimension
]))
103 else if (opt
> 0.5/VALUE_TO_DOUBLE(T
->p
[1][P
->Dimension
]))
125 enum order_sign
glpk_polyhedron_affine_sign(Polyhedron
*D
, Matrix
*T
,
126 struct barvinok_options
*options
)
128 int rational
= !POL_ISSET(options
->MaxRays
, POL_INTEGER
);
131 return order_undefined
;
133 int min
= polyhedron_affine_minmax_sign(LPX_MIN
, D
, T
, rational
);
134 if (min
== EMPTY_DOMAIN
)
135 return order_undefined
;
138 int max
= polyhedron_affine_minmax_sign(LPX_MAX
, D
, T
, rational
);
139 assert(max
!= EMPTY_DOMAIN
);
148 return order_unknown
;
151 enum lp_result
glpk_polyhedron_range(Polyhedron
*D
, Value
*obj
, Value denom
,
152 Value
*min
, Value
*max
,
153 struct barvinok_options
*options
)
160 res
= polyhedron_affine_minmax(LPX_MIN
, D
, obj
, denom
, min
);
163 res
= polyhedron_affine_minmax(LPX_MAX
, D
, obj
, denom
, max
);