Changeset 975


Ignore:
Timestamp:
Feb 23, 2011 3:34:56 PM (11 years ago)
Author:
lou
Message:

Documentation, code comments.

Location:
branches/CglWorking101215/src/CglClique
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • branches/CglWorking101215/src/CglClique/CglClique.cpp

    r913 r975  
    8383                        const CglTreeInfo info) const
    8484{
    85    int i;
    86    bool has_petol_set = petol != -1.0;
    87 
    88    if (! has_petol_set)
    89       si.getDblParam(OsiPrimalTolerance, petol);
    90    int numberOriginalRows = si.getNumRows();
    91    if (info.inTree&&justOriginalRows_)
    92      numberOriginalRows = info.formulation_rows;
    93    int numberRowCutsBefore = cs.sizeRowCuts();
    94    // First select which rows/columns we are interested in.
    95    if (!setPacking_) {
    96       selectFractionalBinaries(si);
    97       if (!sp_orig_row_ind) {
    98          selectRowCliques(si,numberOriginalRows);
    99       }
    100    } else {
    101       selectFractionals(si);
    102       delete[] sp_orig_row_ind;
    103       sp_numrows = numberOriginalRows;
    104       //sp_numcols = si.getNumCols();
    105       sp_orig_row_ind = new int[sp_numrows];
    106       for (i = 0; i < sp_numrows; ++i)
    107          sp_orig_row_ind[i] = i;
    108    }
    109    // Just original rows
    110    if (justOriginalRows_&&info.inTree)
    111      sp_numrows = CoinMin(info.formulation_rows,sp_numrows);
    112      
    113 
    114    createSetPackingSubMatrix(si);
    115    fgraph.edgenum = createNodeNode();
    116    createFractionalGraph();
    117 
    118    cl_indices = new int[sp_numcols];
    119    cl_del_indices = new int[sp_numcols];
     85   int i ;
     86/*
     87  Grab a value for the minimum acceptable violation, if not already set by
     88  the client.
     89*/
     90   bool has_petol_set = (petol != -1.0) ;
     91   if (!has_petol_set)
     92      si.getDblParam(OsiPrimalTolerance,petol) ;
     93/*
     94  Consider only the original constraints, or all constraints?
     95*/
     96   int numberOriginalRows = si.getNumRows() ;
     97   if (info.inTree && justOriginalRows_)
     98     numberOriginalRows = info.formulation_rows ;
     99   int numberRowCutsBefore = cs.sizeRowCuts() ;
     100/*
     101  Select the columns of interest, then the rows of interest.  Variables of
     102  interest x<j> are fractional binary variables. Rows of interest have
     103  the form SUM{j} x<j> + (stuff with positive coefficients) <= 1 or = 1.
     104
     105  If the user has asserted that this is a set packing problem, all variables
     106  are assumed to be binary and all rows are assumed to be cliques.
     107*/
     108  delete[] sp_orig_row_ind ;
     109  if (!setPacking_) {
     110    selectFractionalBinaries(si) ;
     111    selectRowCliques(si,numberOriginalRows) ;
     112  } else {
     113    selectFractionals(si) ;
     114    sp_numrows = numberOriginalRows ;
     115    //sp_numcols = si.getNumCols() ;
     116    sp_orig_row_ind = new int[sp_numrows] ;
     117    for (i = 0; i < sp_numrows; ++i)
     118         sp_orig_row_ind[i] = i ;
     119  }
     120  // jjf: Just original rows
     121  /*
     122    We just did this! Change to an assert to check.  -- lh, 110222 --
     123  */
     124  if (justOriginalRows_ && info.inTree)
     125     // sp_numrows = CoinMin(info.formulation_rows,sp_numrows) ;
     126     assert(sp_numrows <= info.formulation_rows) ;
     127/*
     128  Create a set-packing submatrix: Just the fractional binary variables.
     129 
     130  Then create a column-column (node-node) incidence matrix. The entry for
     131  columns i,j is true iff columns i and j have a row in common (i.e., both
     132  variables are present in some constraint).
     133
     134  Finally, create fgraph (fractional graph). One node for each column with an
     135  edge if two columns are incident in the node-node matrix. A similar
     136  organisation to a packed matrix: nodes[i].nbrs points to the start of the
     137  block of neighbour indices in all_nbrs.
     138*/
     139   createSetPackingSubMatrix(si) ;
     140   fgraph.edgenum = createNodeNode() ;
     141   createFractionalGraph() ;
     142
     143   cl_indices = new int[sp_numcols] ;
     144   cl_del_indices = new int[sp_numcols] ;
    120145
    121146   if (do_row_clique)
    122       find_rcl(cs);
     147      find_rcl(cs) ;
    123148   if (do_star_clique)
    124       find_scl(cs);
     149      find_scl(cs) ;
    125150   if (!info.inTree&&((info.options&4)==4||((info.options&8)&&!info.pass))) {
    126      int numberRowCutsAfter = cs.sizeRowCuts();
     151     int numberRowCutsAfter = cs.sizeRowCuts() ;
    127152     for (int i=numberRowCutsBefore;i<numberRowCutsAfter;i++)
    128        cs.rowCutPtr(i)->setGloballyValid();
    129    }
    130 
    131    delete[] cl_indices;     cl_indices = 0;
    132    delete[] cl_del_indices; cl_del_indices = 0;
    133 
    134    deleteFractionalGraph();
    135    delete[] node_node;      node_node = 0;
    136    deleteSetPackingSubMatrix();
    137 
    138    if (! has_petol_set)
    139       petol = -1;
     153       cs.rowCutPtr(i)->setGloballyValid() ;
     154   }
     155
     156   delete[] cl_indices;     cl_indices = 0 ;
     157   delete[] cl_del_indices; cl_del_indices = 0 ;
     158
     159   deleteFractionalGraph() ;
     160   delete[] node_node;      node_node = 0 ;
     161   deleteSetPackingSubMatrix() ;
     162/*
     163  Restore to unset state if not set at start.
     164*/
     165   if (!has_petol_set)
     166      petol = -1.0 ;
    140167}
    141168
     
    155182CglClique::find_rcl(OsiCuts& cs) const
    156183{
    157    const int nodenum = fgraph.nodenum;
    158    const fnode *nodes = fgraph.nodes;
     184   const int nodenum = fgraph.nodenum ;
     185   const fnode *nodes = fgraph.nodes ;
    159186
    160187   /* A flag for each column that might be used to extend the current row
    161188      clique */
    162    bool *cand = new bool[nodenum];
     189   bool *cand = new bool[nodenum] ;
    163190   /* In cl_indices we'll list the indices of the 'true' entries in cand */
    164191   /* The degree of each candidate (those listed in cl_indices) */
    165    int *degrees = new int[nodenum];
     192   int *degrees = new int[nodenum] ;
    166193
    167194   /** An array used in the recursive complete enumeration of maximal cliques.
    168195       The first cl_length entries are used. */
    169    bool* label = new bool[nodenum];
    170 
    171    int i, j, k;
     196   bool* label = new bool[nodenum] ;
     197
     198   int i, j, k ;
    172199
    173200   /* initialize global variables */
    174    cl_del_length = 0;
    175    cl_length = 0;
    176 
    177    int clique_count = 0;
    178    int largest_length = 0;
     201   cl_del_length = 0 ;
     202   cl_length = 0 ;
     203
     204   int clique_count = 0 ;
     205   int largest_length = 0 ;
    179206
    180207   /* for each row of the matrix */
     
    182209
    183210      /* if the row is of zero length, take the next row */
    184       const int len = sp_row_start[j+1] - sp_row_start[j];
     211      const int len = sp_row_start[j+1] - sp_row_start[j] ;
    185212      if (!len)
    186          continue;
     213         continue ;
    187214
    188215      /* the beginning of the row to be considered */
    189       const int *row = sp_row_ind + sp_row_start[j];
     216      const int *row = sp_row_ind + sp_row_start[j] ;
    190217
    191218      /* copy the row of node_node corresponding to the first column in 'row'
    192219         into cand, and take the AND of this vector with every row of
    193220         node_node corresponding to the rest of the columns in 'row' to
    194          determine those columns that are non-orthog to every column in row */
     221         determine those columns that are non-orthog to every column in row
     222         Notice that because node_node[k,k] = false, the columns in the row
     223         will not be included in the set of candidates. */
    195224      std::copy(node_node + row[0]*nodenum, node_node + (row[0]+1)*nodenum,
    196                 cand);
     225                cand) ;
    197226      for (i = 1; i < len; i++) {
    198          const bool* node_node_col = node_node + row[i] * nodenum;
     227         const bool* node_node_col = node_node + row[i] * nodenum ;
    199228         for (k = 0; k < nodenum; k++)
    200             cand[k] &= node_node_col[k];
     229            cand[k] &= node_node_col[k] ;
    201230      }
    202       cl_length = 0;
     231      cl_length = 0 ;
    203232      for (k = 0; k < nodenum; k++)
    204233         if (cand[k])
    205             cl_indices[cl_length++] = k;
    206       largest_length = CoinMax(cl_length, largest_length);
     234            cl_indices[cl_length++] = k ;
     235      largest_length = CoinMax(cl_length, largest_length) ;
    207236
    208237      /* if there is anything in indices, enumerate (or greedily find)
    209          maximal cliques */
     238        maximal cliques */
    210239      if (cl_length > 0) {
    211          cl_perm_length = len;
    212          cl_perm_indices = row;
     240         cl_perm_length = len ;
     241         cl_perm_indices = row ;
    213242         if (cl_length <= rcl_candidate_length_threshold) {
    214243            for (i = 0; i < cl_length; i++)
    215                label[i] = false;
    216             int pos = 0;
    217             clique_count += enumerate_maximal_cliques(pos, label, cs);
     244               label[i] = false ;
     245            int pos = 0 ;
     246            clique_count += enumerate_maximal_cliques(pos, label, cs) ;
    218247         } else {
    219248            /* order cl_indices into decreasing order of their degrees */
    220249            for (i = 0; i < cl_length; i++)
    221                degrees[i] = nodes[cl_indices[i]].degree;
     250               degrees[i] = nodes[cl_indices[i]].degree ;
    222251            CoinSort_2(degrees, degrees + cl_length, cl_indices,
    223                        CoinFirstGreater_2<int,int>());
    224             clique_count += greedy_maximal_clique(cs);
     252                       CoinFirstGreater_2<int,int>()) ;
     253            clique_count += greedy_maximal_clique(cs) ;
    225254         }
    226255      }
     
    229258   if (rcl_report_result) {
    230259      printf("\nrcl Found %i new violated cliques with the row-clique method",
    231              clique_count);
     260             clique_count) ;
    232261      printf("\nrcl The largest admissible number was %i (threshold %i)\n",
    233              largest_length, rcl_candidate_length_threshold);
     262             largest_length, rcl_candidate_length_threshold) ;
    234263      if (largest_length < rcl_candidate_length_threshold)
    235          printf("rcl    all row cliques have been enumerated\n");
     264         printf("rcl    all row cliques have been enumerated\n") ;
    236265      else
    237          printf("rcl    not all row cliques have been eliminated\n");
    238    }
    239 
    240    delete[] degrees;
    241    delete[] cand;
    242    delete[] label;
     266         printf("rcl    not all row cliques have been eliminated\n") ;
     267   }
     268
     269   delete[] degrees ;
     270   delete[] cand ;
     271   delete[] label ;
    243272}
    244273
     
    256285 * or 1 then the min degree node can be deleted at once.
    257286 * All cliques are enumerated in v U star(v) if the min degree is smaller
    258  * than the threshold  scl_candidate_length_threshold, otherwise attemp to
     287 * than the threshold  scl_candidate_length_threshold, otherwise attempt to
    259288 * find maximal clique greedily.
    260289 *
     
    265294CglClique::find_scl(OsiCuts& cs) const
    266295{
    267    const int nodenum = fgraph.nodenum;
    268    const fnode *nodes = fgraph.nodes;
     296   const int nodenum = fgraph.nodenum ;
     297   const fnode *nodes = fgraph.nodes ;
    269298
    270299   // Return at once if no nodes - otherwise we get invalid reads
    271300   if (!nodenum)
    272      return;
    273    int *current_indices = new int[nodenum];
    274    int *current_degrees = new int[nodenum];
    275    double *current_values = new double[nodenum];
    276 
    277    int *star = cl_indices;
    278    int *star_deg = new int[nodenum];
     301     return ;
     302   int *current_indices = new int[nodenum] ;
     303   int *current_degrees = new int[nodenum] ;
     304   double *current_values = new double[nodenum] ;
     305
     306   int *star = cl_indices ;
     307   int *star_deg = new int[nodenum] ;
    279308
    280309   /** An array used in the recursive complete enumeration of maximal cliques.
    281310       The first cl_length entries are used. */
    282    bool* label = new bool[nodenum];
    283 
    284    int i, cnt1 = 0, cnt2 = 0, cnt3 = 0;
    285    int clique_cnt_e = 0, clique_cnt_g = 0;
    286    int largest_star_size = 0;
     311   bool* label = new bool[nodenum] ;
     312
     313   int i, cnt1 = 0, cnt2 = 0, cnt3 = 0 ;
     314   int clique_cnt_e = 0, clique_cnt_g = 0 ;
     315   int largest_star_size = 0 ;
    287316
    288317   /* initialize global variables */
    289    cl_del_length = 0;
     318   cl_del_length = 0 ;
    290319
    291320   /* initialize current_nodes, current_degrees and current_values */
    292    int current_nodenum = nodenum;
     321   int current_nodenum = nodenum ;
    293322   for (i = 0; i < nodenum; i++) {
    294       current_indices[i] = i;
    295       current_degrees[i] = nodes[i].degree;
    296       current_values[i] = nodes[i].val;
     323      current_indices[i] = i ;
     324      current_degrees[i] = nodes[i].degree ;
     325      current_values[i] = nodes[i].val ;
    297326   }
    298327   
    299328   /* find first node to be checked */
    300329   int best_ind = scl_choose_next_node(current_nodenum, current_indices,
    301                                        current_degrees, current_values);
    302 
    303    int v = current_indices[best_ind];
    304    int v_deg = current_degrees[best_ind];
    305    double v_val = current_values[best_ind];
     330                                       current_degrees, current_values) ;
     331
     332   int v = current_indices[best_ind] ;
     333   int v_deg = current_degrees[best_ind] ;
     334   double v_val = current_values[best_ind] ;
    306335     
    307336   /* while there are nodes left in the graph ... (more precisely, while
     
    311340      /* if the best node is of degree < 2 then it can be deleted */
    312341      if (v_deg < 2) {
    313          cl_del_indices[cl_del_length++] = v;
     342         cl_del_indices[cl_del_length++] = v ;
    314343         scl_delete_node(best_ind, current_nodenum,
    315                          current_indices, current_degrees, current_values);
     344                         current_indices, current_degrees, current_values) ;
    316345         best_ind = scl_choose_next_node(current_nodenum, current_indices,
    317                                          current_degrees, current_values);
    318          v = current_indices[best_ind];
    319          v_deg = current_degrees[best_ind];
    320          v_val = current_values[best_ind];
    321          largest_star_size = CoinMax(largest_star_size, v_deg);
    322          continue;
     346                                         current_degrees, current_values) ;
     347         v = current_indices[best_ind] ;
     348         v_deg = current_degrees[best_ind] ;
     349         v_val = current_values[best_ind] ;
     350         largest_star_size = CoinMax(largest_star_size, v_deg) ;
     351         continue ;
    323352      }
    324353
    325354      /* star will contain the indices of v's neighbors (but not v's index) */
    326       const bool* node_node_start = node_node + nodenum * v;
    327       int& star_length = cl_length;
    328       star_length = 0;
    329       double star_val = v_val;
     355      const bool* node_node_start = node_node + nodenum * v ;
     356      int& star_length = cl_length ;
     357      star_length = 0 ;
     358      double star_val = v_val ;
    330359      for (i = 0; i < current_nodenum; i++) {
    331          const int other_node = current_indices[i];
     360         const int other_node = current_indices[i] ;
    332361         if (node_node_start[other_node]) {
    333             star[star_length] = other_node;
    334             star_deg[star_length++] = current_degrees[i];
    335             star_val += current_values[i];
     362            star[star_length] = other_node ;
     363            star_deg[star_length++] = current_degrees[i] ;
     364            star_val += current_values[i] ;
    336365         }
    337366      }
     
    341370      if (star_val >= 1 + petol) {
    342371         /* node whose star we're evaluating is always in */
    343          cl_perm_length = 1;
    344          cl_perm_indices = &v;
     372         cl_perm_length = 1 ;
     373         cl_perm_indices = &v ;
    345374
    346375         /* find maximal violated cliques in star. cliques found here might not
     
    353382            /* enumerate if v_deg is small enough */
    354383            for (i = 0; i < star_length; i++)
    355                label[i] = false;
    356             int pos = 0;
    357             clique_cnt_e += enumerate_maximal_cliques(pos, label, cs);
    358             cnt1++;
     384               label[i] = false ;
     385            int pos = 0 ;
     386            clique_cnt_e += enumerate_maximal_cliques(pos, label, cs) ;
     387            cnt1++ ;
    359388         } else {
    360389            /* greedily find if v_deg is too big */
    361390            /* order nodes in *decreasing* order of their degrees in star */
    362391            CoinSort_2(star_deg, star_deg + star_length, star,
    363                        CoinFirstGreater_2<int,int>());
     392                       CoinFirstGreater_2<int,int>()) ;
    364393            /* find maxl clique greedily, including v */
    365             clique_cnt_g += greedy_maximal_clique(cs);
    366             cnt2++;
     394            clique_cnt_g += greedy_maximal_clique(cs) ;
     395            cnt2++ ;
    367396         }
    368397      } else {
    369          cnt3++;
     398         cnt3++ ;
    370399      }
    371400      /* delete v from current_indices */
    372       cl_del_indices[cl_del_length++] = v;
     401      cl_del_indices[cl_del_length++] = v ;
    373402      scl_delete_node(best_ind, current_nodenum,
    374                       current_indices, current_degrees, current_values);
     403                      current_indices, current_degrees, current_values) ;
    375404      best_ind = scl_choose_next_node(current_nodenum, current_indices,
    376                                       current_degrees, current_values);
    377       v = current_indices[best_ind];
    378       v_deg = current_degrees[best_ind];
    379       v_val = current_values[best_ind];
    380       largest_star_size = CoinMax(largest_star_size, v_deg);
    381    }
    382 
    383    const int clique_cnt = clique_cnt_e + clique_cnt_g;
     405                                      current_degrees, current_values) ;
     406      v = current_indices[best_ind] ;
     407      v_deg = current_degrees[best_ind] ;
     408      v_val = current_values[best_ind] ;
     409      largest_star_size = CoinMax(largest_star_size, v_deg) ;
     410   }
     411
     412   const int clique_cnt = clique_cnt_e + clique_cnt_g ;
    384413
    385414   if (scl_report_result) {
    386415      printf("\nscl Found %i new violated cliques with the star-clique method",
    387              clique_cnt);
     416             clique_cnt) ;
    388417      printf("\nscl The largest star size was %i (threshold %i)\n",
    389418             largest_star_size, scl_candidate_length_threshold); // par
    390419      printf("scl Enumeration %i times, found %i maxl cliques\n",
    391              cnt1, clique_cnt_e);
     420             cnt1, clique_cnt_e) ;
    392421      printf("scl Greedy %i times, found %i maxl cliques\n",
    393              cnt2, clique_cnt_g);
     422             cnt2, clique_cnt_g) ;
    394423      printf("scl Skipped a star b/c of small solution value %i times\n",
    395              cnt3);
     424             cnt3) ;
    396425
    397426      if (cnt2 == 0)
    398          printf("scl    all cliques have been enumerated\n");
     427         printf("scl    all cliques have been enumerated\n") ;
    399428      else
    400          printf("scl    not all cliques have been eliminated\n");
    401    }
    402 
    403    delete[] current_indices;
    404    delete[] current_degrees;
    405    delete[] current_values;
    406    delete[] star_deg;
    407    delete[] label;
     429         printf("scl    not all cliques have been eliminated\n") ;
     430   }
     431
     432   delete[] current_indices ;
     433   delete[] current_degrees ;
     434   delete[] current_values ;
     435   delete[] star_deg ;
     436   delete[] label ;
    408437}
    409438
     
    420449                                const double *current_values) const
    421450{
    422    int best = 0;
    423    int best_deg = current_degrees[0];
    424    double best_val = current_values[0];
    425    int i;
     451   int best = 0 ;
     452   int best_deg = current_degrees[0] ;
     453   double best_val = current_values[0] ;
     454   int i ;
    426455
    427456   switch (scl_next_node_rule) { // p->par.scl_which_node
     
    429458      for (i = 1; i < current_nodenum; i++)
    430459         if (current_degrees[i] < best_deg) {
    431             best = i;
    432             best_deg = current_degrees[i];
     460            best = i ;
     461            best_deg = current_degrees[i] ;
    433462         }
    434       break;
     463      break ;
    435464   case SCL_MAX_DEGREE: // NOTE: could use stl::max_element
    436465      for (i = 1; i < current_nodenum; i++)
    437466         if (current_degrees[i] > best_deg) {
    438             best = i;
    439             best_deg = current_degrees[i];
     467            best = i ;
     468            best_deg = current_degrees[i] ;
    440469         }
    441       break;
     470      break ;
    442471   case SCL_MAX_XJ_MAX_DEG:
    443472      for (i = 1; i < current_nodenum; i++) {
    444473         if (current_values[i] > best_val) {
    445             best = i;
    446             best_val = current_values[i];
    447             best_deg = current_degrees[i];
     474            best = i ;
     475            best_val = current_values[i] ;
     476            best_deg = current_degrees[i] ;
    448477         } else if (current_values[i] == best_val &&
    449478                    current_degrees[i] > best_deg) {
    450             best = i;
    451             best_deg = current_degrees[i];
     479            best = i ;
     480            best_deg = current_degrees[i] ;
    452481         }
    453482      }
    454       break;
     483      break ;
    455484   default:
    456       printf("ERROR: bad starcl_which_node (in scl_choose_next_node\n");
    457       break;
    458    }
    459    return(best);
     485      printf("ERROR: bad starcl_which_node (in scl_choose_next_node\n") ;
     486      break ;
     487   }
     488   return(best) ;
    460489}
    461490
     
    487516                           double *current_values) const
    488517{
    489    const int v = current_indices[del_ind];
     518   const int v = current_indices[del_ind] ;
    490519
    491520   /* delete the entry corresponding to del_ind from current_indices,
     
    493522   memmove(reinterpret_cast<char *>(current_indices + del_ind),
    494523           reinterpret_cast<char *>(current_indices + (del_ind+1)),
    495            (current_nodenum-del_ind-1) * sizeof(int));
     524           (current_nodenum-del_ind-1) * sizeof(int)) ;
    496525   memmove(reinterpret_cast<char *>(current_degrees + del_ind),
    497526           reinterpret_cast<char *>(current_degrees + (del_ind+1)),
    498            (current_nodenum-del_ind-1) * sizeof(int));
     527           (current_nodenum-del_ind-1) * sizeof(int)) ;
    499528   memmove(reinterpret_cast<char *>(current_values + del_ind),
    500529           reinterpret_cast<char *>(current_values + (del_ind+1)),
    501            (current_nodenum-del_ind-1) * sizeof(double));
    502    current_nodenum--;
     530           (current_nodenum-del_ind-1) * sizeof(double)) ;
     531   current_nodenum-- ;
    503532   
    504533   /* decrease the degrees of v's neighbors by 1 */
    505    const bool* node_node_start = node_node + (fgraph.nodenum * v);
     534   const bool* node_node_start = node_node + (fgraph.nodenum * v) ;
    506535   for (int i = 0; i < current_nodenum; ++i)
    507536      if (node_node_start[current_indices[i]])
    508          current_degrees[i]--;
     537         current_degrees[i]-- ;
    509538}
    510539
     
    540569CglClique::enumerate_maximal_cliques(int& pos, bool* label, OsiCuts& cs) const
    541570{
    542    const fnode *nodes = fgraph.nodes;
    543    const int nodenum = fgraph.nodenum;
    544 
    545    int i, j, k, cnt;
     571   const fnode *nodes = fgraph.nodes ;
     572   const int nodenum = fgraph.nodenum ;
     573
     574   int i, j, k, cnt ;
    546575
    547576   /* starting from position pos, find the first node in cl_indices that
    548577      can be added to the clique, and label it with true */
    549578   while (pos < cl_length) {
    550       label[pos] = true;
    551       const bool* node_node_start = node_node + cl_indices[pos] * nodenum;
     579      label[pos] = true ;
     580      const bool* node_node_start = node_node + cl_indices[pos] * nodenum ;
    552581      for (j = 0; j < pos; j++)
    553582         if (label[j] && ! node_node_start[cl_indices[j]]) {
    554             label[pos] = false;
    555             break;
     583            label[pos] = false ;
     584            break ;
    556585         }
    557586      if (label[pos++] == true)
    558          break;
     587         break ;
    559588   }
    560589
    561590   /* found counts the number of maximal violated cliques that have been sent
    562591      to the lp under the current level of recursion */
    563    int found = 0;
     592   int found = 0 ;
    564593
    565594   /* if not all nodes are labeled: recurse by setting the last node
    566       labeled true once to true and once to false;
     595      labeled true once to true and once to false ;
    567596      otherwise check whether the clique found is maximal and violated */
    568597   if (pos < cl_length) {
    569       found += enumerate_maximal_cliques(pos, label, cs);
    570       label[pos-1] = false;
    571       found += enumerate_maximal_cliques(pos, label, cs);
     598      found += enumerate_maximal_cliques(pos, label, cs) ;
     599      label[pos-1] = false ;
     600      found += enumerate_maximal_cliques(pos, label, cs) ;
    572601   } else {
    573602      /* check if the clique can be extended on cl_indices */
    574603
    575604      /* copy indices of the clique into coef (not user inds, coef is a tmp) */
    576       int* coef = new int[cl_length + cl_perm_length];
     605      int* coef = new int[cl_length + cl_perm_length] ;
    577606      for (j = cl_length - 1, cnt = 0; j >= 0; j--)
    578607         if (label[j])
    579             coef[cnt++] = cl_indices[j];
     608            coef[cnt++] = cl_indices[j] ;
    580609      if (!cnt) {
    581          delete[] coef;
    582          return(found);
     610         delete[] coef ;
     611         return(found) ;
    583612      }
    584613     
     
    586615      for (k = cl_length - 1; k >= 0; k--) {
    587616         if (!label[k]) {
    588             const bool* node_node_start = node_node + cl_indices[k] * nodenum;
     617            const bool* node_node_start = node_node + cl_indices[k] * nodenum ;
    589618            for (i = cnt - 1; i >= 0; i--)
    590619               if (!node_node_start[coef[i]])
    591                   break;
     620                  break ;
    592621            /* if k can be added to the clique, return (the clique is not
    593622               maximal, so it will be or was recorded) */
    594623            if (i < 0) {
    595                delete[] coef;
    596                return(found);
     624               delete[] coef ;
     625               return(found) ;
    597626            }
    598627         }
     
    602631         fill relative indices into coef */
    603632      for (j = 0; j < cl_perm_length; j++)
    604          coef[cnt++] = cl_perm_indices[j];
     633         coef[cnt++] = cl_perm_indices[j] ;
    605634     
    606635      /* check if clique is violated */
    607       double lhs = 0;
     636      double lhs = 0 ;
    608637      for (j = 0; j < cnt; j++)
    609          lhs += nodes[coef[j]].val;
     638         lhs += nodes[coef[j]].val ;
    610639      if (lhs < 1 + petol) {
    611          delete[] coef;
    612          return(found);
     640         delete[] coef ;
     641         return(found) ;
    613642      }
    614643     
     
    616645         discarded (was already counted) */
    617646      for (i = 0; i < cl_del_length; i++) {
    618          const bool* node_node_start = node_node + cl_del_indices[i]*nodenum;
     647         const bool* node_node_start = node_node + cl_del_indices[i]*nodenum ;
    619648         for (j = cnt - 1; j >= 0; j--)
    620649            if (!node_node_start[coef[j]])
    621                break;
     650               break ;
    622651         /* if cl_del_indices[i] can be added to the clique, return */
    623652         if (j < 0) {
    624             delete[] coef;
    625             return(found);
     653            delete[] coef ;
     654            return(found) ;
    626655         }
    627656      }
    628657
    629       recordClique(cnt, coef, cs);
    630       delete[] coef;
     658      recordClique(cnt, coef, cs) ;
     659      delete[] coef ;
    631660     
    632       ++found;
    633    }
    634 
    635    return(found);
     661      ++found ;
     662   }
     663
     664   return(found) ;
    636665}
    637666
     
    648677CglClique::greedy_maximal_clique(OsiCuts& cs) const
    649678{
    650    assert(cl_length > 0);
    651    const fnode *nodes = fgraph.nodes;
    652    const int nodenum = fgraph.nodenum;
    653    int i, j;
    654 
    655    int * coef = new int[cl_length + cl_perm_length];
    656    coef[0] = cl_indices[0];
    657    int cnt = 1;
     679   assert(cl_length > 0) ;
     680   const fnode *nodes = fgraph.nodes ;
     681   const int nodenum = fgraph.nodenum ;
     682   int i, j ;
     683
     684   int *coef = new int[cl_length + cl_perm_length] ;
     685   coef[0] = cl_indices[0] ;
     686   int cnt = 1 ;
     687   /*
     688     Candidates are adjacent to every variable in the row, but not necessarily
     689     adjacent to one another. Add candidates until we run across one that is
     690     not adjacent to some candidate we've already added.
     691   */
    658692   for (j = 1; j < cl_length; j++) {
    659       const int var = cl_indices[j];
    660       const bool* node_node_start = node_node + var * nodenum;
     693      const int var = cl_indices[j] ;
     694      const bool* node_node_start = node_node + var * nodenum ;
    661695      for (i = cnt-1; i >= 0; i--)
    662696         if (!node_node_start[coef[i]])
    663             break;
     697            break ;
    664698      if (i < 0)
    665          coef[cnt++] = var;
    666    }
    667 
     699         coef[cnt++] = var ;
     700   }
     701   /*
     702     Recall that the columns in the row are not included in the set of
     703     candidates.
     704   */
    668705   for (j = 0; j < cl_perm_length; j++)
    669       coef[cnt++] = cl_perm_indices[j];
     706      coef[cnt++] = cl_perm_indices[j] ;
    670707
    671708   /* now coef contains the clique */
    672709   /* only cliques of size at least 3 are interesting */
    673710   if (cnt < 3) {
    674       delete[] coef;
    675       return(0);
     711      delete[] coef ;
     712      return(0) ;
    676713   }
    677714
    678715   /* compute lhs */
    679    double lhs = 0;
     716   double lhs = 0 ;
    680717   for (j = 0; j < cnt; j++)
    681       lhs += nodes[coef[j]].val;
     718      lhs += nodes[coef[j]].val ;
    682719
    683720   if (lhs > 1 + petol) {
    684       recordClique(cnt, coef, cs);
    685       delete[] coef;
    686       return(1);
    687    }
    688 
    689    delete[] coef;
    690    return(0);
     721      recordClique(cnt, coef, cs) ;
     722      delete[] coef ;
     723      return(1) ;
     724   }
     725
     726   delete[] coef ;
     727   return(0) ;
    691728}
    692729
     
    701738   /* transform relative indices into user indices and order them */
    702739   for (int j = len - 1; j >= 0; j--)
    703       indices[j] = sp_orig_col_ind[indices[j]];
    704    std::sort(indices, indices + len);
    705    OsiRowCut rowcut;
    706    double* coef = new double[len];
    707    std::fill(coef, coef + len, 1.0);
    708    rowcut.setRow(len, indices, coef);
    709    rowcut.setUb(1.0);
    710    CoinAbsFltEq equal(1.0e-12);
    711    cs.insertIfNotDuplicate(rowcut,equal);
    712    delete[] coef;
     740      indices[j] = sp_orig_col_ind[indices[j]] ;
     741   std::sort(indices, indices + len) ;
     742   OsiRowCut rowcut ;
     743   double* coef = new double[len] ;
     744   std::fill(coef, coef + len, 1.0) ;
     745   rowcut.setRow(len, indices, coef) ;
     746   rowcut.setUb(1.0) ;
     747   CoinAbsFltEq equal(1.0e-12) ;
     748   cs.insertIfNotDuplicate(rowcut,equal) ;
     749   delete[] coef ;
    713750}
    714751
     
    719756CglClique::clone() const
    720757{
    721   return new CglClique(*this);
     758  return new CglClique(*this) ;
    722759}
    723760
     
    727764CglClique::generateCpp( FILE * fp)
    728765{
    729   CglClique other;
    730   fprintf(fp,"0#include \"CglClique.hpp\"\n");
    731   fprintf(fp,"3  CglClique clique;\n");
     766  CglClique other ;
     767  fprintf(fp,"0#include \"CglClique.hpp\"\n") ;
     768  fprintf(fp,"3  CglClique clique;\n") ;
    732769  std::string types[] = {"SCL_MIN_DEGREE","SCL_MAX_DEGREE",
    733                          "SCL_MAX_XJ_MAX_DEG"};
     770                         "SCL_MAX_XJ_MAX_DEG"} ;
    734771  if (scl_next_node_rule!=other.scl_next_node_rule)
    735772    fprintf(fp,"3  clique.setStarCliqueNextNodeMethod(CglClique::%s);\n",
    736             types[scl_next_node_rule].c_str());
     773            types[scl_next_node_rule].c_str()) ;
    737774  else
    738775    fprintf(fp,"4  clique.setStarCliqueNextNodeMethod(CglClique::%s);\n",
    739             types[scl_next_node_rule].c_str());
     776            types[scl_next_node_rule].c_str()) ;
    740777  if (scl_candidate_length_threshold!=other.scl_candidate_length_threshold)
    741778    fprintf(fp,"3  clique.setStarCliqueCandidateLengthThreshold(%d);\n",
    742             scl_candidate_length_threshold);
     779            scl_candidate_length_threshold) ;
    743780  else
    744781    fprintf(fp,"4  clique.setStarCliqueCandidateLengthThreshold(%d);\n",
    745             scl_candidate_length_threshold);
     782            scl_candidate_length_threshold) ;
    746783  if (rcl_candidate_length_threshold!=other.rcl_candidate_length_threshold)
    747784    fprintf(fp,"3  clique.setRowCliqueCandidateLengthThreshold(%d);\n",
    748             rcl_candidate_length_threshold);
     785            rcl_candidate_length_threshold) ;
    749786  else
    750787    fprintf(fp,"4  clique.setRowCliqueCandidateLengthThreshold(%d);\n",
    751             rcl_candidate_length_threshold);
     788            rcl_candidate_length_threshold) ;
    752789  if (scl_report_result!=other.scl_report_result)
    753790    fprintf(fp,"3  clique.setStarCliqueReport(%s);\n",
    754             scl_report_result ? "true" : "false");
     791            scl_report_result ? "true" : "false") ;
    755792  else
    756793    fprintf(fp,"4  clique.setStarCliqueReport(%s);\n",
    757             scl_report_result ? "true" : "false");
     794            scl_report_result ? "true" : "false") ;
    758795  if (rcl_report_result!=other.rcl_report_result)
    759796    fprintf(fp,"3  clique.setRowCliqueReport(%s);\n",
    760             rcl_report_result ? "true" : "false");
     797            rcl_report_result ? "true" : "false") ;
    761798  else
    762799    fprintf(fp,"4  clique.setRowCliqueReport(%s);\n",
    763             rcl_report_result ? "true" : "false");
     800            rcl_report_result ? "true" : "false") ;
    764801  if (do_star_clique!=other.do_star_clique)
    765802    fprintf(fp,"3  clique.setDoStarClique(%s);\n",
    766             do_star_clique ? "true" : "false");
     803            do_star_clique ? "true" : "false") ;
    767804  else
    768805    fprintf(fp,"4  clique.setDoStarClique(%s);\n",
    769             do_star_clique ? "true" : "false");
     806            do_star_clique ? "true" : "false") ;
    770807  if (do_row_clique!=other.do_row_clique)
    771808    fprintf(fp,"3  clique.setDoRowClique(%s);\n",
    772             do_row_clique ? "true" : "false");
     809            do_row_clique ? "true" : "false") ;
    773810  else
    774811    fprintf(fp,"4  clique.setDoRowClique(%s);\n",
    775             do_row_clique ? "true" : "false");
     812            do_row_clique ? "true" : "false") ;
    776813  if (petol!=other.petol)
    777     fprintf(fp,"3  clique.setMinViolation(%g);\n",petol);
     814    fprintf(fp,"3  clique.setMinViolation(%g);\n",petol) ;
    778815  else
    779     fprintf(fp,"4  clique.setMinViolation(%g);\n",petol);
     816    fprintf(fp,"4  clique.setMinViolation(%g);\n",petol) ;
    780817  if (getAggressiveness()!=other.getAggressiveness())
    781     fprintf(fp,"3  clique.setAggressiveness(%d);\n",getAggressiveness());
     818    fprintf(fp,"3  clique.setAggressiveness(%d);\n",getAggressiveness()) ;
    782819  else
    783     fprintf(fp,"4  clique.setAggressiveness(%d);\n",getAggressiveness());
    784   return "clique";
     820    fprintf(fp,"4  clique.setAggressiveness(%d);\n",getAggressiveness()) ;
     821  return "clique" ;
    785822}
    786823/*****************************************************************************/
     
    791828{
    792829  if (solver)
    793     fakeSolver_ = solver->clone();
     830    fakeSolver_ = solver->clone() ;
    794831  else
    795     fakeSolver_ = NULL;
     832    fakeSolver_ = NULL ;
    796833  if (fakeSolver_) {
    797     probing_ = new CglProbing();
    798     probing_->refreshSolver(fakeSolver_);
     834    probing_ = new CglProbing() ;
     835    probing_->refreshSolver(fakeSolver_) ;
    799836  } else {
    800     probing_ = NULL;
     837    probing_ = NULL ;
    801838  }
    802839                             
     
    807844{
    808845  if (rhs.fakeSolver_) {
    809     fakeSolver_ = rhs.fakeSolver_->clone();
    810     probing_ = new CglProbing(*rhs.probing_);
    811     probing_->refreshSolver(fakeSolver_);
     846    fakeSolver_ = rhs.fakeSolver_->clone() ;
     847    probing_ = new CglProbing(*rhs.probing_) ;
     848    probing_->refreshSolver(fakeSolver_) ;
    812849  } else {
    813     fakeSolver_ = NULL;
    814     probing_ = NULL;
     850    fakeSolver_ = NULL ;
     851    probing_ = NULL ;
    815852  }
    816853}
     
    822859CglFakeClique::clone() const
    823860{
    824   return new CglFakeClique(*this);
     861  return new CglFakeClique(*this) ;
    825862}
    826863
     
    828865CglFakeClique::~CglFakeClique()
    829866{
    830   delete fakeSolver_;
    831   delete probing_;
     867  delete fakeSolver_ ;
     868  delete probing_ ;
    832869}
    833870// Assign solver (generator takes over ownership)
     
    835872CglFakeClique::assignSolver(OsiSolverInterface * fakeSolver)
    836873{
    837   delete fakeSolver_;
    838   fakeSolver_ = fakeSolver;
     874  delete fakeSolver_ ;
     875  fakeSolver_ = fakeSolver ;
    839876  if (fakeSolver_) {
    840     delete [] sp_orig_row_ind;
    841     sp_orig_row_ind=NULL;
     877    delete [] sp_orig_row_ind ;
     878    sp_orig_row_ind=NULL ;
    842879  }
    843880  if (probing_)
    844     probing_->refreshSolver(fakeSolver_);
     881    probing_->refreshSolver(fakeSolver_) ;
    845882}
    846883// Generate cuts
     
    850887{
    851888  if (fakeSolver_) {
    852     assert (si.getNumCols()==fakeSolver_->getNumCols());
    853     fakeSolver_->setColLower(si.getColLower());
    854     fakeSolver_->setColSolution(si.getColSolution());
    855     fakeSolver_->setColUpper(si.getColUpper());
    856     CglClique::generateCuts(*fakeSolver_,cs,info);
     889    assert (si.getNumCols()==fakeSolver_->getNumCols()) ;
     890    fakeSolver_->setColLower(si.getColLower()) ;
     891    fakeSolver_->setColSolution(si.getColSolution()) ;
     892    fakeSolver_->setColUpper(si.getColUpper()) ;
     893    CglClique::generateCuts(*fakeSolver_,cs,info) ;
    857894    if (probing_) {
    858895      // get and set branch and bound cutoff
    859       double cutoff;
    860       si.getDblParam(OsiDualObjectiveLimit,cutoff);
    861       fakeSolver_->setDblParam(OsiDualObjectiveLimit,cutoff);
    862       probing_->generateCuts(*fakeSolver_,cs,info);
     896      double cutoff ;
     897      si.getDblParam(OsiDualObjectiveLimit,cutoff) ;
     898      fakeSolver_->setDblParam(OsiDualObjectiveLimit,cutoff) ;
     899      probing_->generateCuts(*fakeSolver_,cs,info) ;
    863900    }
    864901  } else {
    865902    // just use real solver
    866     CglClique::generateCuts(si,cs,info);
     903    CglClique::generateCuts(si,cs,info) ;
    867904  }
    868905}
  • branches/CglWorking101215/src/CglClique/CglClique.hpp

    r913 r975  
    99#include "CglCutGenerator.hpp"
    1010
    11 //class OsiCuts;
    12 //class OsiSolverInterface;
    13 
     11/*! \brief Classical cliques
     12
     13  We're looking for violated classical clique constraints on binary variables:
     14  \verbatim
     15  SUM{j} x(j) = 1 or SUM{j} x(j) <= 1.
     16  \endverbatim
     17  The general approach is to identify binary variables with fractional values
     18  in the current solution, form an adjacency graph on these variables, and
     19  look for cliques in the adjacency graph. Two variables are adjacent if both
     20  occur together in at least one suitable constraint. A suitable constraint is
     21  defined as
     22  - The constraint is an `=' or `<=' constraint with row upper bound of 1.0.
     23  - All fractional binary variables have coefficients of 1.0.
     24  - All other coefficients in the row are positive.
     25
     26  For an explanation of the algorithms, see, for example, Hoffman, K. and
     27  Padberg, M., "Solving Airline Crew Scheduling Problems by Branch-and-Cut",
     28  Management Science 39(6), June, 1993.
     29*/
    1430class CglClique : public CglCutGenerator {
    1531
    16     friend void CglCliqueUnitTest(const OsiSolverInterface * siP,
    17                                   const std::string mpdDir );
     32  friend void CglCliqueUnitTest(const OsiSolverInterface *siP,
     33                                const std::string mpdDir) ;
     34
    1835public:
    19     /// Copy constructor
    20     CglClique(const CglClique& rhs);
    21     /// Clone
    22     virtual CglCutGenerator * clone() const;
    23 
    24     /// Assignment operator
    25     CglClique& operator=(const CglClique& rhs);
    26    
    27 public:
    28    
    29     virtual void
    30     generateCuts(const OsiSolverInterface& si, OsiCuts & cs,
    31                  const CglTreeInfo info = CglTreeInfo()) const;
    32    
    33     /**@name Constructors and destructors */
    34     //@{
    35     /** Default constructor.
    36         If the setPacking argument is set to true then CglClique will assume that the
    37         problem in the solverinterface passed to the generateCuts() method
    38         describes a set packing problem, i.e.,
    39         - all variables are binary
    40         - the matrix is a 0-1 matrix
    41         - all constraints are '= 1' or '<= 1'
    42        
    43         Otherwise the user can use the considerRows() method to set the list of
    44         clique rows, that is,
    45         - all coeffs corresponding to binary variables at fractional level is 1
    46         - all other coeffs are non-negative
    47         - the constraint is '= 1' or '<= 1'.
    48 
    49         If the user does not set the list of clique rows then CglClique will
    50         start the generateCuts() methods by scanning the matrix for them.
    51         Also justOriginalRows can be set to true to limit clique creation
    52     */
    53     CglClique(bool setPacking = false, bool justOriginalRows = false);
    54     /// Destructor
    55     virtual ~CglClique() {}
    56     /// Create C++ lines to get to current state
    57     virtual std::string generateCpp( FILE * fp);
    58 
    59     void considerRows(const int numRows, const int* rowInd);
    60 
    61 public:
    62     /** possible choices for selecting the next node in the star clique search
    63      */
    64     enum scl_next_node_method {
    65         SCL_MIN_DEGREE,
    66         SCL_MAX_DEGREE,
    67         SCL_MAX_XJ_MAX_DEG
    68     };
    69 
    70     void setStarCliqueNextNodeMethod(scl_next_node_method method) {
    71         scl_next_node_rule = method;
    72     }
    73 
    74     void setStarCliqueCandidateLengthThreshold(int maxlen) {
    75         scl_candidate_length_threshold = maxlen;
    76     }
    77     void setRowCliqueCandidateLengthThreshold(int maxlen) {
    78         rcl_candidate_length_threshold = maxlen;
    79     }
    80 
    81     void setStarCliqueReport(bool yesno = true) { scl_report_result = yesno; }
    82     void setRowCliqueReport(bool yesno = true) { rcl_report_result = yesno; }
    83 
    84     void setDoStarClique(bool yesno = true) { do_star_clique = yesno; }
    85     void setDoRowClique(bool yesno = true) { do_row_clique = yesno; }
    86 
    87     void setMinViolation(double minviol) { petol = minviol; }
    88     double getMinViolation() const { return petol; }
     36
     37  /*! \name Cut generation */
     38  //@{
     39  /*! \brief Generate cuts from cliques
     40
     41    Generate cliques as requested and process them into cuts.
     42  */
     43  virtual void
     44  generateCuts(const OsiSolverInterface &si, OsiCuts &cs,
     45               const CglTreeInfo info = CglTreeInfo()) const ;
     46  //@}
     47
     48  /*! \brief Possible choices for selecting the next node in the star
     49             clique search.
     50
     51    Minimum degree is the classic choice. The default is maximum value, then
     52    maximum degree.
     53  */
     54  enum scl_next_node_method {
     55      SCL_MIN_DEGREE,           ///< minimum degree
     56      SCL_MAX_DEGREE,           ///< maximum degree
     57      SCL_MAX_XJ_MAX_DEG        ///< maximum value, then maximum degree
     58  } ;
     59
     60  /*! \name Cut generation control */
     61  //@{
     62
     63  /// Set method for selecting next node in star clique search
     64  inline void setStarCliqueNextNodeMethod(scl_next_node_method method)
     65  { scl_next_node_rule = method ; }
     66
     67  /*! \brief The maximal length of the candidate list to extend a row clique.
     68 
     69    See #scl_candidate_length_threshold.
     70  */
     71  inline void setStarCliqueCandidateLengthThreshold(int maxlen)
     72  { scl_candidate_length_threshold = maxlen ; }
     73
     74  /*! \brief The maximal length of the candidate list to extend a star clique.
     75 
     76    See #rcl_candidate_length_threshold.
     77  */
     78  inline void setRowCliqueCandidateLengthThreshold(int maxlen)
     79  { rcl_candidate_length_threshold = maxlen ; }
     80
     81  /// Control star clique formation
     82  inline void setDoStarClique(bool yesno = true) { do_star_clique = yesno ; }
     83  /// Control row clique formation
     84  inline void setDoRowClique(bool yesno = true) { do_row_clique = yesno ; }
     85
     86  /*! \brief Set minimum acceptable violation of clique cuts
     87
     88    The default value is -1.0. If #petol = -1.0, whether by default or because
     89    it's been set to -1.0, the actual value used will be the solver's primal
     90    tolerance.
     91  */
     92  inline void setMinViolation(double minviol) { petol = minviol; }
     93  /// Get minimum acceptable violation of clique cuts
     94  inline double getMinViolation() const { return petol; }
     95  //@}
     96
     97  /*! \name Constructors and destructors */
     98  //@{
     99  /*! \brief Default constructor.
     100
     101    If \p setPacking is set to true then CglClique will assume that the
     102    problem describes a set packing problem, i.e.,
     103      - all variables are binary
     104      - the matrix is a 0-1 matrix
     105      - all constraints are '= 1' or '<= 1'
     106     
     107    Otherwise, CglClique will start the #generateCuts method by scanning
     108    the matrix for suitable rows.
     109
     110    \p justOriginalRows can be set to true to limit the constraints that are
     111    considered when in the search tree; see #justOriginalRows_.
     112  */
     113  CglClique(bool setPacking = false, bool justOriginalRows = false) ;
     114  /// Copy constructor
     115  CglClique(const CglClique& rhs) ;
     116  /// Clone
     117  virtual CglCutGenerator * clone() const ;
     118  /// Assignment operator
     119  CglClique& operator=(const CglClique& rhs) ;
     120 
     121  /// Destructor
     122  virtual ~CglClique() {}
     123  //@}
     124
     125  /*! \name Utility methods */
     126  //@{
     127  /// Control printing of detailed statistics on the star clique method
     128  inline void setStarCliqueReport(bool yesno = true)
     129  { scl_report_result = yesno ; }
     130  /// Control printing of detailed statistics on the row clique method
     131  inline void setRowCliqueReport(bool yesno = true)
     132  { rcl_report_result = yesno ; }
     133
     134  /// Create C++ lines to get to current state
     135  virtual std::string generateCpp( FILE * fp) ;
     136  //@}
    89137
    90138private:
     
    93141    friend struct frac_graph ;
    94142
    95     /** A node of the fractional graph. There is a node for every variable at
    96         fractional level. */
     143    /*! \brief A node of the fractional graph.
     144   
     145      There is a node for every variable at fractional level.
     146    */
    97147    struct fnode {
    98         /** pointer into all_nbr */
    99         int          *nbrs;
    100         /** 1-x_i-x_j, needed for odd holes, in the same order as the adj list,
    101             pointer into all_edgecost */
    102         double       *edgecosts;
    103         /** degree of the node */
    104         int           degree;
    105         /** the fractional value of the variable corresponding to this node */
    106         double        val;
    107     };
    108 
    109     /** A graph corresponding to a fractional solution of an LP. Two nodes are
    110         adjacent iff their columns are non-orthogonal. */
     148      /// Start of neighbours of this node in frac_graph::all_nbr
     149      int *nbrs ;
     150      /*! \brief 1-x_i-x_j, needed for odd holes
     151     
     152        Currently unused.
     153      */
     154      double *edgecosts ;
     155      /// degree of the node
     156      int degree ;
     157      /// the fractional value of the variable corresponding to this node
     158      double val ;
     159    } ;
     160
     161    /*! \brief A graph corresponding to a fractional solution of an LP.
     162   
     163      Two nodes are adjacent iff their columns are non-orthogonal.
     164    */
    111165    struct frac_graph {
    112         /** # of nodes = # of fractional values in the LP solution */
    113         int    nodenum;
    114         /** # of edges in the graph */
    115         int    edgenum;
    116         /** density= edgenum/(nodenum choose 2) */
    117         double density;
    118         int    min_deg_node;
    119         int    min_degree;
    120         int    max_deg_node;
    121         int    max_degree;
    122         /** The array of the nodes in the graph */
    123         fnode  *nodes;
    124         /** The array of all the neighbors. First the indices of the nodes
    125             adjacent to node 0 are listed, then those adjacent to node 1, etc. */
    126         int    *all_nbr;
    127         /** The array of the costs of the edges going to the neighbors */
    128         double *all_edgecost;
    129 
    130         frac_graph() :
    131             nodenum(0), edgenum(0), density(0),
    132             min_deg_node(0), min_degree(0), max_deg_node(0), max_degree(0),
    133             nodes(0), all_nbr(0), all_edgecost(0) {}
    134     };
     166      /*! \brief The number of nodes in the graph
     167     
     168        The number of fractional values in the LP solution
     169      */
     170      int nodenum ;
     171      /// The number of edges in the graph
     172      int edgenum ;
     173      /*! \brief density
     174     
     175        (actual edges)/(potential edges) = edgenum/(nodenum choose 2)
     176      */
     177      double density ;
     178      /// Node with minimum degree
     179      int min_deg_node ;
     180      /// Minimum degree
     181      int min_degree ;
     182      /// Node with maximum degree
     183      int max_deg_node ;
     184      /// Maximum degree
     185      int max_degree ;
     186      /*! \brief The array of the nodes in the graph
     187
     188        nodes[i] points to the start of the neighbours of i in #all_nbr
     189      */
     190      fnode *nodes ;
     191      /*! \brief The array of all the neighbours.
     192     
     193        First the indices of the nodes adjacent to node 0 are listed, then
     194        those adjacent to node 1, etc.
     195      */
     196      int *all_nbr ;
     197      /*! \brief The array of the costs of the edges going to the neighbors
     198     
     199        Currently unused.
     200      */
     201      double *all_edgecost ;
     202      /// Constructor
     203      frac_graph() :
     204          nodenum(0), edgenum(0), density(0),
     205          min_deg_node(0), min_degree(0), max_deg_node(0), max_degree(0),
     206          nodes(0), all_nbr(0), all_edgecost(0) {}
     207    } ;
    135208
    136209protected:
    137     /** An indicator showing whether the whole matrix in the solverinterface is
    138         a set packing problem or not */
     210
     211    /*! \brief True if the whole matrix is a set packing problem. */
    139212    bool setPacking_;
    140     /// True if just look at original rows
     213    /*! \brief True to consider only original rows.
     214
     215      Note that this is ineffective at the root, where all rows will always be
     216      considered.
     217    */
    141218    bool justOriginalRows_;
    142     /** pieces of the set packing part of the solverinterface */
     219
     220    /// Number of clique rows under consideration
    143221    mutable int sp_numrows;
     222    /// Original row index for clique rows
    144223    mutable int* sp_orig_row_ind;
     224    /// Number of fractional binary variables
    145225    mutable int sp_numcols;
     226    /// Original column index for fractional binary variables
    146227    mutable int* sp_orig_col_ind;
     228    /*! \brief Solution value for fractional binary variables
     229
     230      Correlated with #sp_orig_col_ind.
     231    */
    147232    mutable double* sp_colsol;
     233    /// Column starts for the set packing submatrix
    148234    mutable int* sp_col_start;
     235    /// Row indices for columns of the set packing submatrix
    149236    mutable int* sp_col_ind;
     237    /// Row starts for the set packing submatrix
    150238    mutable int* sp_row_start;
     239    /// Column indices for the rows of the set packing submatrix
    151240    mutable int* sp_row_ind;
    152241
    153     /** the intersection graph corresponding to the set packing problem */
     242    /// The intersection graph corresponding to the set packing problem
    154243    mutable frac_graph fgraph;
    155     /** the node-node incidence matrix of the intersection graph. */
     244    /*! \brief The node-node incidence matrix of the intersection graph.
     245   
     246      This is stored as a full sp_numcols x sp_numcols matrix.
     247    */
    156248    mutable bool* node_node;
    157249
    158     /** The primal tolerance in the solverinterface. */
     250    /*! \brief Minimum acceptable clique violation
     251   
     252      The default set by the constructor is -1.0. If petol is -1.0 when
     253      #generateCuts is called (whether set by default or by the user), the
     254      actual value used will be the solver's primal tolerance.
     255    */
    159256    mutable double petol;
    160257
    161     /** data for the star clique algorithm */
    162 
    163     /** Parameters */
     258    /*! \name Clique control parameters */
    164259    /**@{*/
    165     /** whether to do the row clique algorithm or not. */
     260    /** True to generate row cliques. */
    166261    bool do_row_clique;
    167     /** whether to do the star clique algorithm or not. */
     262    /** True to generate star cliques. */
    168263    bool do_star_clique;
    169264
    170265    /** How the next node to be added to the star clique should be selected */
    171266    scl_next_node_method scl_next_node_rule;
    172     /** In the star clique method the maximal length of the candidate list
    173         (those nodes that are in a star, i.e., connected to the center of the
    174         star) to allow complete enumeration of maximal cliques. Otherwise a
    175         greedy algorithm is used. */
     267    /*! \brief Maximum number of candidates for complete enumeration of
     268               star cliques.
     269
     270      In the star clique method, the maximal length of the candidate list
     271      (those nodes that are in a star, i.e., connected to the center of the
     272      star) to allow complete enumeration of all maximal cliques. If the
     273      candidate list is longer, a greedy algorithm is used.
     274    */
    176275    int scl_candidate_length_threshold;
    177     /** whether to give a detailed statistics on the star clique method */
     276
     277    /** True to report detailed statistics on the star clique method */
    178278    bool scl_report_result;
    179279
    180     /** In the row clique method the maximal length of the candidate list
    181         (those nodes that can extend the row clique, i.e., connected to all
    182         nodes in the row clique) to allow complete enumeration of maximal
    183         cliques. Otherwise a greedy algorithm is used. */
     280    /*! \brief Maximum number of candidates for complete enumeration of
     281               row cliques.
     282     
     283      In the row clique method, the maximal length of the candidate list
     284      (those nodes that can extend the row clique, i.e., connected to all
     285      nodes in the row clique) to allow complete enumeration of all maximal
     286      cliques. If the candidate list is longer, a greedy algorithm is used.
     287    */
    184288    int rcl_candidate_length_threshold;
    185     /** whether to give a detailed statistics on the row clique method */
     289
     290    /** True to report detailed statistics on the row clique method */
    186291    bool rcl_report_result;
    187292    /**@}*/
    188293
    189     /** variables/arrays that are used across many methods */
     294    /*! \name Variables/arrays that are used across many methods */
    190295    /**@{*/
    191     /** List of indices that must be in the to be created clique. This is just
     296    /** List of indices that must be in the to-be-created clique. This is just
    192297        a pointer, it is never new'd and therefore does not need to be
    193298        delete[]'d either. */
     
    212317
    213318private:
    214     /** Scan through the variables and select those that are binary and are at
    215         a fractional level. */
    216     void selectFractionalBinaries(const OsiSolverInterface& si) const;
    217     /** Scan through the variables and select those that are at a fractional
    218         level. We already know that everything is binary. */
     319    /*! \brief Scan through the variables and select those that are binary
     320               and have a fractional value.
     321
     322      The definition of fractional is asymmetric: x* > tol1 and x* < tol2,
     323      where tol1 is the solver's primal tolerance and tol2 is the value set
     324      for #petol. It's possible this is an error; there's some special-case
     325      code in this method that does not make sense in context.
     326    */
     327    void selectFractionalBinaries(const OsiSolverInterface &si) const;
     328
     329    /*! \brief Scan through the variables and select those that have a
     330               fractional value.
     331
     332      This method assumes that all the variables are binary, hence it does not
     333      check this. The definition of fractional is symmetric, x* > tol1 and
     334      x* < tol2, tol1 = tol2 = solver's primal tolerance.
     335    */
    219336    void selectFractionals(const OsiSolverInterface& si) const;
    220337    /**  */
     
    258375void CglCliqueUnitTest(const OsiSolverInterface * siP,
    259376                       const std::string mpdDir);
    260 /// This works on a fake solver i.e. invented rows
     377
    261378class CglProbing;
     379/*! This works on a fake solver i.e. invented rows
     380
     381  In more words, you can load in an Osi (#fakeSolver_) of your choosing.
     382  When the #generateCuts method is called, the loaded Osi is used, if
     383  present. If it's not present, then the si supplied as a parameter to
     384  #generatCuts will be used. If it, too, is absent, things will end badly.
     385
     386  CglFakeClique also conceals a CglProbing object, which is invoked iff the
     387  loaded Osi is used.
     388*/
    262389class CglFakeClique : public CglClique {
    263390 
     
    278405  //@{
    279406  /** Default constructor.
    280       If the setPacking argument is set to true then CglFakeClique will assume that the
     407      If the setPacking argument is set to true then CglFakeClique will
     408      assume that the
    281409      problem in the solverinterface passed to the generateCuts() method
    282410      describes a set packing problem, i.e.,
     
    285413      - all constraints are '= 1' or '<= 1'
    286414     
    287       Otherwise the user can use the considerRows() method to set the list of
    288       clique rows, that is,
    289       - all coeffs corresponding to binary variables at fractional level is 1
    290       - all other coeffs are non-negative
    291       - the constraint is '= 1' or '<= 1'.
    292      
    293       If the user does not set the list of clique rows then CglFakeClique will
     415      Otherwise, CglFakeClique will
    294416      start the generateCuts() methods by scanning the matrix for them.
    295417  */
  • branches/CglWorking101215/src/CglClique/CglCliqueHelper.cpp

    r913 r975  
    2525
    2626   const int numcols = si.getNumCols();
     27/*
     28  This can't be correct. Compare the conditions on this special case with the
     29  handling of petol in generateCuts, and notice that we use lclPetol against
     30  the lower bound and petol against the upper bound in the following loop.
     31  As long as petol is positive, or exactly -1.0 (the default), behaviour will
     32  be sane because petol will be > 0 when we get here.
     33  -- lh, 110222 --
     34*/
    2735   if (petol<0.0) {
    2836     // do all if not too many
     
    8593
    8694/*===========================================================================*
     95  Collect rows that have clique potential. All fractional variables
     96  must have coefficients of +1.0; the row upper bound must be 1.0, and all
     97  other coefficients must be positive.
    8798 *===========================================================================*/
    8899
     
    143154
    144155/*===========================================================================*
    145   Create the set packing submatrix
     156  Create the set packing submatrix. At the end of this, we have a column-major
     157  representation in sp_col_start, sp_col_ind and a row-major representation in
     158  sp_row_start, sp_row_ind.
     159
     160  Since all nonzero coefficients are 1.0, no need to store them.
    146161 *===========================================================================*/
    147162void
     
    157172   const CoinPackedMatrix& mcol = *si.getMatrixByCol();
    158173   const int numrows = si.getNumRows();
     174/*
     175  Construct a back reference from original row index -> clique row index.
     176  Rows not under consideration have value -1.
     177*/
    159178   int* clique = new int[numrows];
    160179   std::fill(clique, clique+numrows, -1);
    161180   for (i = 0; i < sp_numrows; ++i)
    162181      clique[sp_orig_row_ind[i]] = i;
    163 
     182/*
     183  Count the number of entries in each row and column in the submatrix.
     184*/
    164185   for (j = 0; j < sp_numcols; ++j) {
    165186      const CoinShallowPackedVector& vec = mcol.getVector(sp_orig_col_ind[j]);
     
    172193      }
    173194   }
    174 
     195/*
     196  Transform the vectors of row and column lengths into row and column start
     197  vectors.
     198*/
    175199   std::partial_sum(sp_col_start, sp_col_start+sp_numcols, sp_col_start);
    176200   std::rotate(sp_col_start, sp_col_start+sp_numcols,
     
    183207/*
    184208  Now create the vectors with row indices for each column (sp_col_ind) and
    185   column indices for each row (sp_row_ind). It turns out that
    186   CoinIsOrthogonal assumes that the row indices for a given column are listed
    187   in ascending order. This is *not* a solver-independent assumption! At best,
    188   one can hope that the underlying solver will produce an index vector that's
    189   either ascending or descending. Under that assumption, compare the first
    190   and last entries and proceed accordingly. Eventually some solver will come
    191   along that hands back an index vector in random order, and CoinIsOrthogonal
    192   will break.  Until then, try and avoid the cost of a sort.
     209  column indices for each row (sp_row_ind). It turns out that CoinIsOrthogonal
     210  assumes that the row indices for a given column are listed in ascending
     211  order. Try to guess whether the original matrix has entries in ascending or
     212  descending order and fill accordingly, but sort to guarantee ascending
     213  order.
    193214*/
    194215   sp_col_ind = new int[nzcnt];
    195216   sp_row_ind = new int[nzcnt];
    196    int last=0;
     217   int last = 0;
    197218   for (j = 0; j < sp_numcols; ++j) {
    198219      const CoinShallowPackedVector& vec = mcol.getVector(sp_orig_col_ind[j]);
     
    217238        }
    218239      }
    219       // sort
    220240      std::sort(sp_col_ind+last,sp_col_ind+sp_col_start[j]);
    221241      last=sp_col_start[j];
    222242   }
     243/*
     244  Rotate one more time to restore correct row and column starts.
     245*/
    223246   std::rotate(sp_col_start, sp_col_start+sp_numcols,
    224247               sp_col_start + (sp_numcols+1));
     
    233256/*****************************************************************************/
    234257
     258/*
     259  Keep in mind that all coefficients are 0 or 1, and 0's are kept in a packed
     260  matrix. As soon as we hit a pair of matching indices, the vectors are not
     261  orthogonal.
     262
     263  Note that the method also assumes that coefficients are sorted in ascending
     264  order.
     265*/
    235266static inline bool
    236267CoinIsOrthogonal(const int* first0, const int* last0,
     
    264295   int min_degree, max_degree, min_deg_node, max_deg_node;
    265296
    266 #  ifdef ZEROFAULT
    267    // May be read below even if sp_numcols == 0
    268297   nodes[0].degree = 0 ;
    269 #  endif
    270298
    271299   int i, j, total_deg, old_total;
     
    316344
    317345/*===========================================================================*
    318  * Construct the node-node incidence matrix from the fractional graph.
     346 * Construct the node-node incidence matrix from the set packing submatrix.
     347 * Two columns are incident if they are not orthogonal (i.e., they are both
     348 * present in some row). Note that node_node[k,k] = false; this is important
     349 * during greedy clique formation.
    319350 *===========================================================================*/
    320351int
Note: See TracChangeset for help on using the changeset viewer.