Changeset 934


Ignore:
Timestamp:
Dec 29, 2012 12:17:34 PM (7 years ago)
Author:
pbelotti
Message:

introduced sparsify option. Fixed leak in CouenneScalar?. Half-baked sparsification.

Location:
trunk/Couenne/src/cut/sdpcuts
Files:
5 edited

Legend:

Unmodified
Added
Removed
  • trunk/Couenne/src/cut/sdpcuts/CouenneMatrix.hpp

    r931 r934  
    3636      index_  (index),
    3737      elem_   (elem),
    38       delete_ (elem_ -> code () == COU_EXPRCONST) {}
     38      delete_ (elem_ -> code () == COU_EXPRCONST || (elem_ != elem_ -> Original ())) {}
    3939
    4040    ~CouenneScalar ();
     
    4343      index_  (rhs.index_),
    4444      elem_   (new exprClone (rhs.elem_)),
    45       delete_ (rhs.delete_) {}
     45      delete_ (true) {}
    4646
    4747    CouenneScalar &operator= (const CouenneScalar &rhs) {
    4848      index_  = rhs.index_;
    4949      elem_   = new exprClone (rhs.elem_);
    50       delete_ = rhs.delete_;
     50      delete_ = true;
    5151      return *this;
    5252    }
  • trunk/Couenne/src/cut/sdpcuts/CouenneSdpCuts.cpp

    r933 r934  
    3232  std::string s;
    3333
    34   options -> GetIntegerValue ("sdp_cuts_num_ev", numEigVec_, "couenne.");
    35   options -> GetStringValue  ("sdp_cuts_neg_ev", s,          "couenne.");
    36   onlyNegEV_ = (s == "yes");
     34  options -> GetIntegerValue ("sdp_cuts_num_ev",   numEigVec_, "couenne.");
     35  options -> GetStringValue  ("sdp_cuts_neg_ev",   s,          "couenne."); onlyNegEV_   = (s == "yes");
     36  options -> GetStringValue  ("sdp_cuts_sparsify", s,          "couenne."); useSparsity_ = (s == "yes");
    3737
    3838  CouenneExprMatrix *cauldron = new CouenneExprMatrix;
     
    160160
    161161    delete (*i);
    162 
    163   // Destroy matrix structures
    164162}
    165163
     
    168166CouenneSdpCuts::CouenneSdpCuts (const CouenneSdpCuts &rhs):
    169167
    170   problem_   (rhs. problem_),
    171   numEigVec_ (rhs. numEigVec_),
    172   onlyNegEV_ (rhs. onlyNegEV_) {
     168  problem_     (rhs. problem_),
     169  doNotUse_    (rhs. doNotUse_),
     170  numEigVec_   (rhs. numEigVec_),
     171  onlyNegEV_   (rhs. onlyNegEV_),
     172  useSparsity_ (rhs. useSparsity_) {
    173173
    174174  for (std::vector <CouenneExprMatrix *>::const_iterator
     
    183183CouenneSdpCuts &CouenneSdpCuts::operator= (const CouenneSdpCuts &rhs) {
    184184
    185   problem_   = rhs. problem_;
    186   numEigVec_ = rhs. numEigVec_;
    187   onlyNegEV_ = rhs. onlyNegEV_;
     185  problem_     = rhs. problem_;
     186  doNotUse_    = rhs. doNotUse_;
     187  numEigVec_   = rhs. numEigVec_;
     188  onlyNegEV_   = rhs. onlyNegEV_;
     189  useSparsity_ = rhs. useSparsity_;
    188190
    189191  for (std::vector <CouenneExprMatrix *>::const_iterator
     
    219221     -1, -1,
    220222     "Set to -1 to indicate that all n eigenvectors should be used. Eigenvalues are \
    221 sorted in non-decreasing order, hence selecting 1 will provide cuts on the most negative eigenvalue"
     223sorted in non-decreasing order, hence selecting 1 will provide cuts on the most negative eigenvalue."
    222224    );
    223225
     
    226228     "Only use negative eigenvalues to create sdp cuts.",
    227229     "yes",
    228      "no", "use all eigenvalues regardless of their sign",
    229      "yes", "exclude all non-negative eigenvalues"
     230     "no", "use all eigenvalues regardless of their sign.",
     231     "yes", "exclude all non-negative eigenvalues."
    230232    );
    231233
     
    235237    ("sdp_cuts_sparsify",
    236238     "Make cuts sparse by greedily reducing X one column at a time before extracting eigenvectors.",
     239     "no",
     240     "no", "",
     241     "yes", ""
     242    );
     243
     244#if 0
     245  roptions -> AddStringOption2
     246    ("sdp_cuts_",
     247     "",
    237248     "yes",
    238249     "no", "",
    239250     "yes", ""
    240251    );
    241 
    242 #if 0
    243   roptions -> AddStringOption2
    244     ("sdp_cuts_neg_ev",
    245      "Only use negative eigenvalues to create sdp cuts.",
    246      "yes",
    247      "no", "use all eigenvalues regardless of their sign",
    248      "yes", "exclude all non-negative eigenvalues"
    249     );
    250 #endif
    251 }
     252#endif
     253}
  • trunk/Couenne/src/cut/sdpcuts/CouenneSdpCuts.hpp

    r933 r934  
    5252    std::vector <CouenneExprMatrix *> minors_; ///< minors on which to apply cuts
    5353
    54     int numEigVec_; ///< number of eigenvectors to be used (default n)
     54    int numEigVec_; ///< number of eigenvectors to be used (default: n)
    5555
    5656    bool onlyNegEV_; ///< only use negative eigenvalues (default: yes)
     57
     58    bool useSparsity_; ///< Sparsify eigenvalues before writing inequality (default: no)
    5759
    5860  public:
  • trunk/Couenne/src/cut/sdpcuts/CutGen.cpp

    r933 r934  
    2727//#define DEBUG
    2828
    29 #define SPARSIFY
    30 #define SPARSIFY2
    31 #define SPARSIFY_MINOR_SDP_CUTS
     29//#define SPARSIFY
     30//#define SPARSIFY2
     31//#define SPARSIFY_MINOR_SDP_CUTS
    3232
    3333const bool WISE_SPARSIFY = true;
     
    179179#endif
    180180
    181 #ifdef SPARSIFY_MINOR_SDP_CUTS
    182   double *Acopy = CoinCopyOfArray (A, n * n);
    183 #endif
    184 
    185   double
     181  double
     182    *Acopy = useSparsity_ ? CoinCopyOfArray (A, n * n) : NULL,
    186183    *w = NULL,
    187184    *z = NULL;
     
    221218    genSDPcut (si, cs, minor, work_ev [i], work_ev [i], indA);
    222219
    223 #if (defined SPARSIFY) || (defined SPARSIFY2) || (defined WISE_SPARSIFY)
    224 
    225   int wise_evdec_num = 0;
    226 
    227   int card_sparse_v_mat = 0;
    228   double **sparse_v_mat = new double*[SPARSIFY_MAX_CARD];
    229   for (int i=0; i<SPARSIFY_MAX_CARD; i++)
    230     sparse_v_mat[i] = new double [n];
    231 #endif
    232 
    233 #ifdef SPARSIFY2
    234   int min_nz;
    235 
    236   min_nz = ceil (n * SPARSIFY_NEW_NZ_THRESHOLD);
    237   card_sparse_v_mat = 0;
    238 
    239   sparsify2 (n, A, sparse_v_mat, &card_sparse_v_mat, min_nz, &wise_evdec_num);
    240 
    241   for (int k=0; k < card_sparse_v_mat; k++)
    242     genSDPcut (si, cs, minor, sparse_v_mat [k], sparse_v_mat [k], indA);
    243 #endif
    244 
    245   bool do_next_sparsify = WISE_SPARSIFY;
    246 
    247   if (!WISE_SPARSIFY) {
    248 #if defined SPARSIFY
    249     do_next_sparsify = true;
    250 #endif
    251   }
    252 
    253   if (do_next_sparsify) {
     220  int
     221    wise_evdec_num    = 0,
     222    card_sparse_v_mat = 0,
     223    min_nz;
     224
     225
     226  double **sparse_v_mat = NULL;
     227
     228  if (useSparsity_) {
     229
     230    sparse_v_mat = new double*[SPARSIFY_MAX_CARD];
     231    for (int i=0; i<SPARSIFY_MAX_CARD; i++)
     232      sparse_v_mat[i] = new double [n];
     233
     234    min_nz = ceil (n * SPARSIFY_NEW_NZ_THRESHOLD);
     235    card_sparse_v_mat = 0;
     236
     237    sparsify2 (n, A, sparse_v_mat, &card_sparse_v_mat, min_nz, &wise_evdec_num);
     238
     239    for (int k=0; k < card_sparse_v_mat; k++)
     240      genSDPcut (si, cs, minor, sparse_v_mat [k], sparse_v_mat [k], indA);
     241  }
     242
     243  if (WISE_SPARSIFY || useSparsity_) {
    254244    for (int i=0; i<nVecs; ++i) {
    255245
     
    263253        genSDPcut (si, cs, minor, sparse_v_mat [k], sparse_v_mat [k], indA);
    264254
    265 #ifdef SPARSIFY_MINOR_SDP_CUTS
    266         additionalSDPcuts (si,cs, minor, n, Acopy, sparse_v_mat[k], indA);
    267 #endif
     255        if (useSparsity_)
     256          additionalSDPcuts (si, cs, minor, n, Acopy, sparse_v_mat[k], indA);
    268257      }
    269258    }
     
    274263  delete [] indA;
    275264
    276   do_next_sparsify = WISE_SPARSIFY;
    277 
    278   if (WISE_SPARSIFY) {
    279 #if (defined SPARSIFY) || (defined SPARSIFY2)
    280     do_next_sparsify = true;
    281 #endif
    282   }
    283 
    284   if (do_next_sparsify) {
     265  if (useSparsity_) {
     266
    285267    for (int i=0; i < SPARSIFY_MAX_CARD; i++)
    286268      delete [] sparse_v_mat[i];
     269
    287270    delete [] sparse_v_mat;
     271    delete [] Acopy;
    288272  }
    289273
     
    292276  delete [] A;
    293277  delete [] work_ev;
    294 
    295 #ifdef SPARSIFY_MINOR_SDP_CUTS
    296   delete [] Acopy;
    297 #endif
    298278}
    299279
     
    648628    *zbest      = new double [rnsq],
    649629
    650     *w          = new double [running_n - 1],
    651     *z          = new double [rnsq];
     630    *w          = NULL,//new double [running_n - 1],
     631    *z          = NULL;//new double [rnsq];
    652632
    653633  // remove one column/row at a time to get smaller and smaller minor
    654634
    655635  while (running_n > 1) {
     636
     637    rnsq = (running_n - 1) * (running_n - 1);
    656638
    657639    best_val = 0.;
     
    698680
    699681      std::memcpy (Tbest, Tcopy, rnsq            * sizeof (double));
    700       std::memcpy (zbest, z,     rnsq            * sizeof (double));
     682      CoinCopyN (z, rnsq, zbest); //std::memcpy (zbest, z,     rnsq            * sizeof (double));
    701683      std::memcpy (wbest, w,     (running_n - 1) * sizeof (double));
    702684
    703685      card_ev_best = card_ev;
    704686    }
     687
     688    delete [] w;
     689    delete [] z;
     690
     691    w = z = NULL;
    705692  }
    706693
     
    775762
    776763// Adds SDP cuts using negative eigenvectors where small (smaller than
    777 // COUENNE_EPS) components are fixed to zero
     764// 1 / (10 sqrt n)) components are fixed to zero
    778765
    779766/************************************************************************/
     
    789776    cnt = 0;
    790777
     778  double threshold = 1 / (10 * sqrt ((double) n));
     779
    791780  for (int i=0; i < n; i++)
    792     indices [i] = ((fabs (vector [i]) > COUENNE_EPS) ? (cnt++) : -1);
     781    indices [i] = ((fabs (vector [i]) > threshold) ? (cnt++) : -1);
    793782
    794783  double *subA = new double [cnt*cnt];
     
    920909    }
    921910
    922   *lhs = 0;
     911  *lhs = 0.;
    923912
    924913  for (int i=0; i<n; i++) {
     
    956945  loc_selected[ind_i] = 0;
    957946  (*ploc_card_selected)--;
    958  
    959   if(selected[ind_i] != 1) {
     947
     948  if (selected [ind_i] != 1)
    960949    (*ploc_card_new_selected)--;
    961   }
     950
    962951  (*ploc_lhs) -= delta;
    963952
     
    993982
    994983  *pnchanged = 0;
    995   for(int i=0; i<n; i++) {
     984  for (int i=0; i<n; i++) {
    996985   
    997     curr_ind++;
    998     if(curr_ind == n) {
     986    if (++curr_ind == n)
    999987      curr_ind = 0;
    1000     }
    1001988   
    1002989    int ind_i = order[curr_ind];
     
    1011998      continue;
    1012999   
    1013     double delta = 2 * locmargin[ind_i] - locmat[ind_i * n + ind_i];
     1000    double delta = 2 * locmargin [ind_i] - locmat [ind_i * n + ind_i];
    10141001    if (((type == VALID_DELTA || type == SELECTED) && (*ploc_lhs - delta < min_delta)) ||
    10151002        ((type == POS_DELTA)                       && (delta > 0))) {
    10161003
    1017       zero_comp(ind_i, delta, n, selected, loc_selected,
    1018                 ploc_card_selected, ploc_card_new_selected,
    1019                 ploc_lhs, locmargin, locmat, locv, evidx, wise, evdec_num, recomp_gap, threshold);
     1004      zero_comp (ind_i, delta, n, selected, loc_selected,
     1005                 ploc_card_selected, ploc_card_new_selected,
     1006                 ploc_lhs, locmargin, locmat, locv, evidx, wise, evdec_num, recomp_gap, threshold);
    10201007      (*pnchanged)++;
    10211008    }
     
    10351022                               int *pcard_v_mat) const {
    10361023
    1037   (*pnew_selected) = 0;
    1038 
    1039   for(int i=0; i<n; i++) {
     1024  *pnew_selected = 0;
     1025
     1026  for (int i=0; i<n; i++) {
    10401027    if(loc_selected[i]) {
    10411028      sparse_v_mat[*pcard_v_mat][i] = locv[i];
     
    10461033      }
    10471034    }
    1048     else {
     1035    else
    10491036      sparse_v_mat[*pcard_v_mat][i] = 0;
    1050     }
    10511037  }
    10521038
     
    10641050
    10651051  if(loc_card_selected + init_card_selected == n) {
    1066     if(*has_init_vect == 1) {
    1067 
    1068       return;
    1069     }
    1070     else {
    1071       (*has_init_vect) = 1;
    1072     }
     1052    if (*has_init_vect == 1) return;
     1053    else
     1054       (*has_init_vect) = 1;
    10731055  }
    10741056       
     
    10901072    card_selected          = 0,
    10911073    loc_card_selected      = 0,
     1074
    10921075    *selected     = new int [n],
    10931076    *loc_selected = new int [n],
     
    10961079  double
    10971080    min_delta,
    1098     sq_np = sqrt((double)n),
    1099     is_zero = 1/(10 * sq_np),
    1100     lhs = 0,
    1101     loc_lhs = 0,
     1081    is_zero = 1 / (10 * sqrt ((double) n)),
     1082    lhs     = 0.,
     1083    loc_lhs = 0.,
     1084
    11021085    *margin    = new double  [n],
    11031086    *locv      = new double  [n],
    11041087    *locv_orig = new double  [n],
    1105     *locmargin = new double  [n],
    1106     *mat       = new double  [n*n],
    1107     *locmat    = new double  [n*n];
     1088    *locmargin = new double  [n], 
     1089    *locmat    = new double  [n*n],
     1090    *mat       = CoinCopyOfArray (sol, n*n);
    11081091
    11091092  *card_v_mat = 0;
     
    11111094  for (i=0; i<n; i++) {
    11121095
    1113     selected[i] = 0;
    1114     //    mat[i] = new double[n*n];
    1115     //locmat[i] = new double[n];
    1116     order[i] = i;
     1096    order [i] = i;
    11171097
    11181098    // zero small components in v
    1119     if (fabs(v[i]) < is_zero) {
    1120 
    1121       locv_orig[i] = 0;
    1122       selected[i] = -1; // -1: ind will be set to 0 in loc_selected
     1099    if (fabs (v[i]) < is_zero) {
     1100
     1101      locv_orig [i] = 0;
     1102      selected  [i] = -1; // -1: ind will be set to 0 in loc_selected
    11231103      card_selected++;
    1124     } else
    1125       locv_orig[i] = v[i];
     1104
     1105    } else {
     1106      selected  [i] = 0;
     1107      locv_orig [i] = v[i];
     1108    }
    11261109  }
    11271110
     
    11391122  update_sparsify_structures (n, locv_orig, margin, mat, &lhs, NULL, evidx, false, evdec_num);
    11401123
    1141   int init_card_selected = card_selected; // to recognize if cut from original
    1142   // vector is generated
    1143   int has_init_vect = 0;
    1144        
     1124  int
     1125    init_card_selected = card_selected, // to recognize if cut from original
     1126    has_init_vect = 0,                  // vector is generated
     1127    start_point = -1;                   // order [start_point]: index that should not be removed
     1128
    11451129  min_delta = lhs * (use_new_sparsify ? SPARSIFY_NEW_DELTA : SPARSIFY_OLD_DELTA); // do not weaken the cut too much
    1146   int start_point = -1; // order[start_point]: index that should not be removed
    1147        
     1130
    11481131  while (card_selected < n) {
    11491132
    1150     for(i=0; i<n; i++)
     1133    for (i=0; i<n; i++)
     1134
    11511135      if (selected [order [i]] == 0) {
    11521136        start_point = i;
     
    11571141    loc_card_new_selected = n;
    11581142    loc_lhs = lhs;
    1159     double recomp_gap = fabs(lhs*WISE_SPARSIFY_GAP);
    1160     double threshold = lhs + recomp_gap;
     1143
     1144    double
     1145      recomp_gap = fabs (lhs * WISE_SPARSIFY_GAP),
     1146      threshold  = lhs + recomp_gap;
    11611147
    11621148    // restore locv (might have been changed by WISE_SPARSIFY during the generation of the last sparse cut)
    1163     for(i=0;i<n;i++)
    1164       locv[i] = locv_orig[i];
     1149    CoinCopyN (locv_orig, n, locv);
    11651150
    11661151    for(i=0; i<n; i++) {
     
    11781163      locmargin[i] = margin[i];
    11791164      for(j=0; j<n; j++)
    1180         locmat[i * n + j] = mat[i*n+j];
    1181     }
    1182 
    1183     if (loc_lhs < min_delta) {
     1165        locmat[i * n + j] = mat [i * n + j];
     1166    }
     1167
     1168    if (loc_lhs >= min_delta) {
     1169
     1170      // use vector as is
     1171
     1172      card_selected = n;
     1173
     1174      if (onlyNegEV_) {
     1175
     1176        int new_selected = 0;
     1177                       
     1178        add_v_cut (n, loc_selected, loc_card_selected, locv,
     1179                   init_card_selected, &has_init_vect,
     1180                   selected, &card_selected, &new_selected,
     1181                   sparse_v_mat, card_v_mat);
     1182      }
     1183
     1184    } else {
    11841185
    11851186      int changed = 1;
     
    12581259      } /* while(changed) */
    12591260
    1260       if((loc_card_selected < n * (use_new_sparsify ? SPARSIFY_NEW_NZ_THRESHOLD : SPARSIFY_OLD_NZ_THRESHOLD)) || (*card_v_mat == 0)) {
     1261      if ((loc_card_selected < n * (use_new_sparsify ? SPARSIFY_NEW_NZ_THRESHOLD : SPARSIFY_OLD_NZ_THRESHOLD)) || (*card_v_mat == 0)) {
    12611262
    12621263        int new_selected = 0;
     
    12671268                  sparse_v_mat, card_v_mat);
    12681269      } else {
    1269         selected[order[start_point]] = 1;
     1270        selected [order [start_point]] = 1;
    12701271        card_selected++;
    12711272      }
    1272     } else {
    1273       // loc_lhs >= min_delta  use vector as is
    1274 
    1275       card_selected = n;
    1276 
    1277 #ifndef ONLY_NEG_EIGENV
    1278       int new_selected = 0;
    1279                        
    1280       add_v_cut(n, loc_selected, loc_card_selected, locv,
    1281                 init_card_selected, &has_init_vect,
    1282                 selected, &card_selected, &new_selected,
    1283                 sparse_v_mat, card_v_mat);
    1284 #endif
    1285 
    1286     }
    1287   } /* while(card_selected < n) */
     1273    }
     1274  } /* while (card_selected < n) */
    12881275
    12891276  delete[] order;
  • trunk/Couenne/src/cut/sdpcuts/dsyevx_wrapper.cpp

    r930 r934  
    1616
    1717#include "CouenneConfig.h"
    18 
    19 //#include "IpLapack.hpp"
    2018
    2119extern "C" {
     
    8785
    8886  F77_FUNC
    89     (dsyevx,DSYEVX) 
     87    (dsyevx,DSYEVX)
    9088    (&jobz, &range, &uplo, &n,
    9189     A, &lda,
     
    10098      if(ifail[i] > 0) {
    10199        printf("### WARNING: dsyevx_wrapper(): ifail[%d]: %d   curr_ev[%d]=%.18f\n"
    102                ,i, ifail[i],ifail[i],w[ifail[i]]);
     100               , i, ifail [i], ifail [i], w [ifail [i]]);
    103101      }
    104102    }
Note: See TracChangeset for help on using the changeset viewer.