polysign_cdd_template.cc

   1 #define GMPRATIONAL
   2 #include <setoper.h>
   3 #include <cdd.h>
   4 #include <barvinok/util.h>
   5 #include "polysign.h"
   6 #include "initcdd.h"
   7
   8 #define EMPTY_DOMAIN    -2
   9
  10 static int polyhedron_affine_minmax(DD_LPObjectiveType obj, Polyhedron *P,
  11                                     Matrix *T, bool rational)
  12 {
  13     DD_LPType  *lp;
  14     assert(P->Dimension == T->NbColumns-1);
  15     assert(T->NbRows == 2);
  16     DD_rowrange irev = P->NbConstraints;
  17     DD_rowrange rows = irev + P->NbEq + 1;
  18     DD_colrange cols = 1 + P->Dimension;
  19     lp = DD_CreateLPData(obj, DD_Rational, rows, cols);
  20     lp->Homogeneous = DD_FALSE;
  21     lp->objective = obj;
  22
  23     for (DD_rowrange j = 0; j < P->NbConstraints; ++j) {
  24         for (DD_colrange k = 0; k < P->Dimension; ++k) {
  25             DD_set_si(lp->A[j][1+k], 5);
  26             DD_set_z(lp->A[j][1+k], P->Constraint[j][1+k]);
  27         }
  28         DD_set_z(lp->A[j][0], P->Constraint[j][1+P->Dimension]);
  29         if (j < P->NbEq) {
  30             set_addelem(lp->equalityset, j+1);
  31             for (DD_colrange k = 0; k < P->Dimension; ++k)
  32                 DD_neg(lp->A[irev][1+k], lp->A[j][1+k]);
  33             DD_neg(lp->A[irev][0], lp->A[j][0]);
  34             ++irev;
  35         }
  36     }
  37     /* objective function */
  38     for (DD_colrange k = 0; k < P->Dimension; ++k)
  39         DD_set_z(lp->A[rows-1][1+k], T->p[0][k]);
  40     DD_set_z(lp->A[rows-1][0], T->p[0][P->Dimension]);
  41
  42     DD_ErrorType err = DD_NoError;
  43     DD_LPSolve(lp, DD_DualSimplex, &err);
  44     assert(err == DD_NoError);
  45
  46     int sign;
  47     if (lp->LPS == DD_Optimal) {
  48         if (rational)
  49             DD_rat_sign(sign, obj, lp->optvalue);
  50         else
  51             /* The objective function has integer coefficients,
  52              * so the optimal should be an integer (over the integer points)
  53              */
  54             DD_int_sign(sign, obj, lp->optvalue);
  55     } else if (lp->LPS == DD_DualInconsistent) {
  56         if (obj == DD_LPmin)
  57             sign = -1;
  58         else
  59             sign = 1;
  60     } else if (lp->LPS == DD_Inconsistent) {
  61         sign = EMPTY_DOMAIN;
  62     } else
  63         assert(0);
  64
  65     DD_FreeLPData(lp);
  66     return sign;
  67 }
  68
  69 enum order_sign cdd_polyhedron_affine_sign(Polyhedron *D, Matrix *T,
  70                                             struct barvinok_options *options)
  71 {
  72     if (emptyQ2(D))
  73         return order_undefined;
  74
  75     INIT_CDD;
  76     bool rational = !POL_ISSET(options->MaxRays, POL_INTEGER);
  77     int min = polyhedron_affine_minmax(DD_LPmin, D, T, rational);
  78     if (min == EMPTY_DOMAIN)
  79         return order_undefined;
  80     if (min > 0)
  81         return order_gt;
  82     int max = polyhedron_affine_minmax(DD_LPmax, D, T, rational);
  83     assert(max != EMPTY_DOMAIN);
  84     if (max < 0)
  85         return order_lt;
  86     if (min == max)
  87         return order_eq;
  88     if (max == 0)
  89         return order_le;
  90     if (min == 0)
  91         return order_ge;
  92     return order_unknown;
  93 }