Originally posted by: Vincent Tkindt

Dear all,

I am faced with a serious problem: the lack of real documentation on some advanced C functions under CPLEX. I talk about CPXbinvarow(). My aim is to implement the Tomlin pseudo-costs which improve upon those of Driebeeck (also known as those of Beale et al. ?), currently returned by the function CPXmdleave().

First, let me recall the how can be expressed the basic and non basic variables starting from an (optimal) basis to the LP... X_p refers to a basic variable, x_q to a non basic one.

X₀=a₀₀+\sum (-a_0j)x_j                    // The objective function value

Xp=a_p0-\sum a_pjxj                  // For any basic variable Xp                 

Clearly, -a_0j is the reduced cost of the non basic variable x_j. Also, as x_j is equal to 0 in the LP solution, then a_p0 is the value of variable X_p in this solution. The a_pj coefficients are the simplex tableau coefficients.

My problem is how to link these mathematical statements (very well known in math prog) with the CPLEX C functions. For instance, to retrieve the a_pj coefficients I wrote the code :

 unsigned int uiLoop,uiNbRows;
 int *piHead;

 // We now retrieve the coefficient only for the basic variables of the original problem (and not the slack variables which correspond to non tight constraints)
 piHead=(int *)malloc(sizeof(int)*CPXgetnumrows(env, lp));
 CPXgetbhead(env, lp, piHead, NULL); 

  // We first count the number of basic variables (the boolean as well as the other ones)
 STNumRow=0;
 for (uiLoop=0;uiLoop<CPXgetnumrows(env, lp); uiLoop++ ) if (piHead[uiLoop]>=0) STNumRow++;
 STNumCol=CPXgetnumcols(env, lp);
uiNbRows=0;
 for ( uiLoop= 0; uiLoop < CPXgetnumrows(env, lp); uiLoop++ ) 
         { /* get tableau row for basis entry 'uiLoop' */ 
                 if ( piHead[uiLoop] >= 0 ) 
                 { 
                     pdSTCoefficients[uiNbRows]=(double *)malloc(sizeof(double)*STNumCol); 
                     CPXbinvarow(env, lp, uiLoop, pdSTCoefficients[uiNbRows]); 

                         uiNbRows++;
                         puiBasicVarIndex[piHead[uiLoop]]=uiLoop;
                 }         
         } 

 free(piHead);

And so, I have in matrix pdSTCoefficients[row][col] the simplex tableau coefficient of basic variable piHead[row] and variable col. This is what I guessed but....:

   * How are ranked the variables in the second dimension of that matrix? Does pdSTCoefficients[row][col]  correspond to the "col"-th variable in their order of creation in the LP model? Since it is not the case for the rows (we need a call to CPXgetbhea()), I wonder what is the situation with the columns order.

   * To what correspond exactly pdSTCoefficients[p][j] ?  a_qj , with q=piHead[p]?  -a_qj , with q=piHead[p] ? Does pdSTCoefficients[p][0] contains a_q0 , with q=piHead[p]?

   * Does pdSTCoefficients[0][j] contains the reduced costs ?

There is a serious lack of documentation, to the best of my knowledge, and I am currently blocked.

I computed the down Tomlin's penalty on an instance and get worse value than what CPXmdleave() returns me, while it should not be the case.

It would be very very nice if someone knowing deeply CPLEX solver could help me.

Vincent

Originally posted by: RWunderling

You don't need piHead.

http://www-01.ibm.com/support/knowledgecenter/SSSA5P_12.6.2/ilog.odms.cplex.help/refcallablelibrary/cpxapi/binvarow.html?cp=SSSA5P_12.6.2%2F2-8-3-5-1

Clearly tells you that CPXbinvarow (env, lp, i, row); returns the i'th tableau row for the current basis in the dense array row.

Alternatively you can query the tableau by column using CPXbinvacol (env, lp, j, col):

http://www-01.ibm.com/support/knowledgecenter/SSSA5P_12.6.2/ilog.odms.cplex.help/refcallablelibrary/cpxapi/binvacol.html?cp=SSSA5P_12.6.2%2F2-8-3-5-0

Within numerical tolerances you would get col[i] == row[j].

Hope this helps,

Roland

Roland

Originally posted by: Vincent Tkindt

Dear Roland,

unfortunately, I definitely needs piHead, since the order of the row and the number of the basic variables is unknown from CPXbinvarow().

My question is more related to the order of the columns: when I call CPXbinvarow(i,j), do I get the coefficient for variable j or for the j-th variable in a given order (as used by CPLEX) ?

Besides, what is the sign of the coefficient with respect to standard mathematical formulations of basic variables?

Vincent

Originally posted by: RWunderling

You cannot pass j to CPXbinvarow - please check the documentation.  Mathematically (in TeX notation) you have:

CPXbinvarow (env, lp, i, z):  z = (B^{-1} A)_i  =>  z[j] = (B^{-1} A)_{ij}

Roland