Changeset 2151 for trunk


Ignore:
Timestamp:
Mar 4, 2015 10:40:35 AM (4 years ago)
Author:
forrest
Message:

allow for automatically weakening some cuts

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/Cbc/src/CbcCutGenerator.cpp

    r2105 r2151  
    616616            const OsiRowCutDebugger * debugger = solver->getRowCutDebugger();
    617617#endif
     618            //#define WEAKEN_CUTS 1
     619#ifdef WEAKEN_CUTS
     620            const double * lower = solver->getColLower();
     621            const double * upper = solver->getColUpper();
     622            const double * solution = solver->getColSolution();
     623#endif
    618624            for (k = numberRowCutsBefore; k < numberRowCutsAfter; k++) {
    619625                OsiRowCut * thisCut = cs.rowCutPtr(k) ;
     626#ifdef WEAKEN_CUTS
     627                // weaken cut if coefficients not integer
     628               
     629                double lb=thisCut->lb();
     630                double ub=thisCut->ub();
     631                if (lb<-1.0e100||ub>1.0e100) {
     632                  // normal cut
     633                  CoinPackedVector rpv = thisCut->row();
     634                  const int n = rpv.getNumElements();
     635                  const int * indices = rpv.getIndices();
     636                  const double * elements = rpv.getElements();
     637                  double bound=0.0;
     638                  double sum=0.0;
     639                  bool integral=true;
     640                  int nInteger=0;
     641                  for (int k=0; k<n; k++) {
     642                    double value = fabs(elements[k]);
     643                    int column=indices[k];
     644                    sum += value;
     645                    if (value!=floor(value+0.5))
     646                      integral=false;
     647                    if (solver->isInteger(column)) {
     648                      nInteger++;
     649                      double largerBound = CoinMax(fabs(lower[column]),
     650                                                   fabs(upper[column]));
     651                      double solutionBound=fabs(solution[column])+10.0;
     652                      bound += CoinMin(largerBound,solutionBound);
     653                    }
     654                  }
     655#if WEAKEN_CUTS ==1
     656                  // leave if all 0-1
     657                  if (nInteger==bound)
     658                    integral=true;
     659#endif
     660                  if (!integral) {
     661                    double weakenBy=1.0e-7*(bound+sum);
     662#if WEAKEN_CUTS>2
     663                    weakenBy *= 10.0;
     664#endif             
     665                    if (lb<-1.0e100)
     666                      thisCut->setUb(ub+weakenBy);
     667                    else
     668                      thisCut->setLb(lb-weakenBy);
     669                  }
     670                }
     671#endif
    620672#ifdef CGL_DEBUG
    621673                if (debugger && debugger->onOptimalPath(*solver)) {
     674#if CGL_DEBUG>1
     675                    const double * optimal = debugger->optimalSolution();
     676                    CoinPackedVector rpv = thisCut->row();
     677                    const int n = rpv.getNumElements();
     678                    const int * indices = rpv.getIndices();
     679                    const double * elements = rpv.getElements();
     680                   
     681                    double lb=thisCut->lb();
     682                    double ub=thisCut->ub();
     683                    double sum=0.0;
     684                   
     685                    for (int k=0; k<n; k++){
     686                      int column=indices[k];
     687                      sum += optimal[column]*elements[k];
     688                    }
     689                    // is it nearly violated
     690                    if (sum >ub - 1.0e-8 ||sum < lb + 1.0e-8) {
     691                      double violation=CoinMax(sum-ub,lb-sum);
     692                      std::cout<<generatorName_<<" cut with "<<n
     693                               <<" coefficients, nearly cuts off known solutions by "<<violation
     694                               <<", lo="<<lb<<", ub="<<ub<<std::endl;
     695                      for (int k=0; k<n; k++){
     696                        int column=indices[k];
     697                        std::cout<<"( "<<column<<" , "<<elements[k]<<" ) ";
     698                        if ((k%4)==3)
     699                          std::cout <<std::endl;
     700                      }
     701                      std::cout <<std::endl;
     702                      std::cout <<"Non zero solution values are"<<std::endl;
     703                      int j=0;
     704                      for (int k=0; k<n; k++){
     705                        int column=indices[k];
     706                        if (fabs(optimal[column])>1.0e-9) {
     707                          std::cout<<"( "<<column<<" , "<<optimal[column]<<" ) ";
     708                          if ((j%4)==3)
     709                            std::cout <<std::endl;
     710                          j++;
     711                        }
     712                      }
     713                      std::cout <<std::endl;
     714                    }
     715#endif
    622716                    assert(!debugger->invalidCut(*thisCut));
    623717                    if(debugger->invalidCut(*thisCut))
Note: See TracChangeset for help on using the changeset viewer.