4 #include <barvinok/util.h>
5 #include <barvinok/options.h>
9 #define EMPTY_DOMAIN -2
11 static DD_LPType
*solve_lp(DD_LPObjectiveType obj
, Polyhedron
*P
,
15 DD_rowrange irev
= P
->NbConstraints
;
16 DD_rowrange rows
= irev
+ P
->NbEq
+ 1;
17 DD_colrange cols
= 1 + P
->Dimension
;
18 lp
= DD_CreateLPData(obj
, DD_Rational
, rows
, cols
);
19 lp
->Homogeneous
= DD_FALSE
;
22 for (DD_rowrange j
= 0; j
< P
->NbConstraints
; ++j
) {
23 for (DD_colrange k
= 0; k
< P
->Dimension
; ++k
) {
24 DD_set_si(lp
->A
[j
][1+k
], 5);
25 DD_set_z(lp
->A
[j
][1+k
], P
->Constraint
[j
][1+k
]);
27 DD_set_z(lp
->A
[j
][0], P
->Constraint
[j
][1+P
->Dimension
]);
29 set_addelem(lp
->equalityset
, j
+1);
30 for (DD_colrange k
= 0; k
< P
->Dimension
; ++k
)
31 DD_neg(lp
->A
[irev
][1+k
], lp
->A
[j
][1+k
]);
32 DD_neg(lp
->A
[irev
][0], lp
->A
[j
][0]);
36 /* objective function */
37 for (DD_colrange k
= 0; k
< P
->Dimension
; ++k
)
38 DD_set_z(lp
->A
[rows
-1][1+k
], f
[k
]);
39 DD_set_z(lp
->A
[rows
-1][0], f
[P
->Dimension
]);
41 DD_ErrorType err
= DD_NoError
;
42 DD_LPSolve(lp
, DD_DualSimplex
, &err
);
43 assert(err
== DD_NoError
);
48 static lp_result
polyhedron_affine_minmax(DD_LPObjectiveType obj
, Polyhedron
*P
,
49 Value
*f
, Value denom
, Value
*opt
)
51 lp_result res
= lp_ok
;
52 DD_LPType
*lp
= solve_lp(obj
, P
, f
);
53 assert(value_one_p(denom
));
58 DD_ceil(*opt
, lp
->optvalue
);
60 DD_floor(*opt
, lp
->optvalue
);
62 case DD_DualInconsistent
:
75 static int polyhedron_affine_minmax_sign(DD_LPObjectiveType obj
, Polyhedron
*P
,
76 Matrix
*T
, bool rational
)
78 assert(P
->Dimension
== T
->NbColumns
-1);
79 assert(T
->NbRows
== 2);
80 DD_LPType
*lp
= solve_lp(obj
, P
, T
->p
[0]);
83 if (lp
->LPS
== DD_Optimal
) {
85 DD_rat_sign(sign
, obj
, lp
->optvalue
);
87 /* The objective function has integer coefficients,
88 * so the optimal should be an integer (over the integer points)
90 DD_int_sign(sign
, obj
, lp
->optvalue
);
91 } else if (lp
->LPS
== DD_DualInconsistent
) {
96 } else if (lp
->LPS
== DD_Inconsistent
) {
105 enum order_sign
cdd_polyhedron_affine_sign(Polyhedron
*D
, Matrix
*T
,
106 struct barvinok_options
*options
)
109 return order_undefined
;
112 bool rational
= !POL_ISSET(options
->MaxRays
, POL_INTEGER
);
113 int min
= polyhedron_affine_minmax_sign(DD_LPmin
, D
, T
, rational
);
114 if (min
== EMPTY_DOMAIN
)
115 return order_undefined
;
118 int max
= polyhedron_affine_minmax_sign(DD_LPmax
, D
, T
, rational
);
119 assert(max
!= EMPTY_DOMAIN
);
128 return order_unknown
;
131 enum lp_result
cdd_polyhedron_range(Polyhedron
*D
, Value
*obj
, Value denom
,
132 Value
*min
, Value
*max
,
133 struct barvinok_options
*options
)
141 res
= polyhedron_affine_minmax(DD_LPmin
, D
, obj
, denom
, min
);
144 res
= polyhedron_affine_minmax(DD_LPmax
, D
, obj
, denom
, max
);