[Cgl-tickets] [COIN-OR Cut Generator Library] #17: CoinIsOrthogonal fails unless packed vector indices are in ascending order

[COIN-OR Cut Generator Library]

#17: CoinIsOrthogonal fails unless packed vector indices are in ascending order
-----------------------+----------------------------------------------------
 Reporter:  lou        |       Owner:  somebody
     Type:  defect     |      Status:  new     
 Priority:  major      |   Milestone:          
Component:  CglClique  |     Version:  trunk   
 Keywords:             |  
-----------------------+----------------------------------------------------
 {{{CoinIsOrthogonal}}} fails unless the vector of indices in a packed
 vector is sorted in ascending order. Some solvers return the indices in
 descending order. The following change allows
 {{{CglClique::createSetPackingSubMatrix}}} to convert descending order
 into ascending order as the working matrix is created. This will fail if a
 solver returns indices in some random order, but until one comes along, be
 can try to avoid a sort. This code should replace the final loop in the
 routine:
 {{{
 /*
   Now create the vectors with row indices for each column (sp_col_ind) and
   column indices for each row (sp_row_ind). It turns out that
   CoinIsOrthogonal assumes that the row indices for a given column are
 listed
   in ascending order. This is *not* a solver-independent assumption! At
 best,
   one can hope that the underlying solver will produce an index vector
 that's
   either ascending or descending. Under that assumption, compare the first
   and last entries and proceed accordingly. Eventually some solver will
 come
   along that hands back an index vector in random order, and
 CoinIsOrthogonal
   will break.  Until then, try and avoid the cost of a sort.
 */
    sp_col_ind = new int[nzcnt];
    sp_row_ind = new int[nzcnt];

    for (j = 0; j < sp_numcols; ++j) {
       const CoinShallowPackedVector& vec =
 mcol.getVector(sp_orig_col_ind[j]);
       const int len = vec.getNumElements();
       const int* ind = vec.getIndices();
       if (ind[0] < ind[len-1]) {
         for (i = 0; i < len; ++i) {
            const int sp_row = clique[ind[i]];
            if (sp_row >= 0) {
               sp_col_ind[sp_col_start[j]++] = sp_row;
               sp_row_ind[sp_row_start[sp_row]++] = j;
            }
         }
       }
       else {
         for (i = len-1; i >= 0; --i) {
            const int sp_row = clique[ind[i]];
            if (sp_row >= 0) {
               sp_col_ind[sp_col_start[j]++] = sp_row;
               sp_row_ind[sp_row_start[sp_row]++] = j;
            }
         }
       }
    }
    std::rotate(sp_col_start, sp_col_start+sp_numcols,
                sp_col_start + (sp_numcols+1));

 }}}

-- 
Ticket URL: <https://projects.coin-or.org:8888/Cgl/ticket/17>
COIN-OR Cut Generator Library <http://projects.coin-or.org/Cgl>
A library of mixed-integer programming cutting plane generators.