polysign_cdd_template.cc

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