Originally posted by: vera_deschamps

I am currently implementing a model using the C++ Concert API, and I make use of an upper triangular matrix of decision variables x_ij, i, j = 1, ..., n and i < j. Currently I am implementing this array via

    IloBoolVar *variables = new IloBoolVar[n * n];

    for (int i = 0; i < n - 1; ++i)
        for (int j = i + 1; j < n; ++j) {
            stringstream sstr; sstr << "x_" << i << "_" << j;
            variables[i * number_of_nodes + j] = IloBoolVar (env, sstr.str().c_str());
        }

I was wondering whether I should rather use IloBoolVarArray's for performance reasons. I need to implement cut and lazy constraint callbacks which need to extract the values of the array, either via getValue (in the case above) or getValues (should I use  a IloBoolVarArray), and I'm unsure whether individual calls to getValue are much slower than fewer calls to getValues?

In case getValues is the better choice, is there a good way to implement upper triangular variable matrices?

Many thanks

In general, a single call to getValues() will be faster than a loop over getValue().

There is no special class or similar to explicitly support upper triangular matrices. However, one can do better than what you did: Instead of allocating an array of length n*n you only need an array of length (n*(n+1))/2, the other slots in the n*n arrays would never be used. You could also wrap this into a class and in the accessor functions assert that you never access anything in the lower triangle, never access anything out of bounds, etc. Something like this (untested and not optimized in any way) maybe:

class UpperTriangular {
   IloBoolVarArray data;
   IloInt dim;

   static IloInt map(IloInt row, IloInt col, IloInt d) {
      assert(row >= 0 && row < d);
      assert(col >= 0 && col < d);
      assert(col >= row); // upper triangular
      return ((d * (d + 1)) / 2
              - ((d - row) * (d - row + 1)) / 2
              + (col - row));
   }

public:
   UpperTriangular(IloEnv env, IloInt dimension, char const *name = 0)
      : data(env, (dimension * (dimension + 1)) / 2),
        dim(dimension)
   {
      if ( name ) {
         for (IloInt row = 0; row < dim; ++row)
            for (IloInt col = row; col < dim; ++col) {
               std::stringstream s;
               s << name << "[" << row << "," << col << "]";
               data[map(row, col, dim)].setName(s.str().c_str());
            }
      }
   }
   void end() { data.end(); }

   IloBoolVarArray &getData() { return data; }
   IloBoolVarArray const getData() const { return data; }

   IloInt getDimension () const { return dim; }

   IloInt getIndex(IloInt row, IloInt col) const {
      return map(row, col, dim);
   }

   IloBoolVar operator() (IloInt row, IloInt col) {
      return data[map(row, col, dim)];
   }

};

Then you can do something like

UpperTriangular ut(env, n);
...
cplex.solve();
IloNumArray vals(env);
cplex.getValues(vals, ut.getData());
IloNum value_at_i_j = vals[ut.getIndex(i, j)];

Of course, the 'vals' array could be wrapped into the UpperTriangular class as well ...

Originally posted by: vera_deschamps

This is great -- thank you! I have modified the bounds slightly (as I have a "strictly" upper triangular matrix), and it indeed works faster than before!

Many thanks