Changeset 1100


Ignore:
Timestamp:
Nov 6, 2008 4:48:31 PM (11 years ago)
Author:
forrest
Message:

add in a few modifications and naive heuristic

Location:
trunk/Cbc/src
Files:
9 edited

Legend:

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

    r904 r1100  
    2323    model_(NULL),
    2424   id_(-1),
     25#ifdef CBC_DETERMINISTIC_THREAD
     26   position_(-1),
     27#endif
    2528   preferredWay_(0)
    2629{
     
    3235    model_(model),
    3336    id_(-1),
     37#ifdef CBC_DETERMINISTIC_THREAD
     38    position_(-1),
     39#endif
    3440    preferredWay_(0)
    3541{
     
    4854  model_ = rhs.model_;
    4955  id_ = rhs.id_;
     56#ifdef CBC_DETERMINISTIC_THREAD
     57  position_ = rhs.position_;
     58#endif
    5059  preferredWay_ = rhs.preferredWay_;
    5160}
     
    5968    model_ = rhs.model_;
    6069    id_ = rhs.id_;
     70#ifdef CBC_DETERMINISTIC_THREAD
     71    position_ = rhs.position_;
     72#endif
    6173    preferredWay_ = rhs.preferredWay_;
    6274  }
  • trunk/Cbc/src/CbcBranchBase.hpp

    r933 r1100  
    215215  { return id_;}
    216216 
     217#ifdef CBC_DETERMINISTIC_THREAD
     218  /// Get position in object_ list
     219  inline int position() const
     220  { return position_;}
     221 
     222  /// Set position in object_ list
     223  inline void setPosition(int position)
     224  { position_ = position;}
     225#endif
     226 
    217227   /// update model
    218228  inline void setModel(CbcModel * model)
     
    239249  /// Identifier (normally column number in matrix)
    240250  int id_;
     251#ifdef CBC_DETERMINISTIC_THREAD
     252  /// Position in object list
     253  int position_;
     254#endif
    241255  /// If -1 down always chosen first, +1 up always, 0 normal
    242256  int preferredWay_;
  • trunk/Cbc/src/CbcHeuristicFPump.cpp

    r1088 r1100  
    19051905    }
    19061906  }
    1907      
     1907  //double * saveSolution = CoinCopyOfArray(solution,numberColumns);
    19081908  // return rounded solution
    19091909  for (i=0;i<numberIntegers;i++) {
     
    19681968  memset(rowActivity,0,numberRows*sizeof(double));
    19691969  solver->getMatrixByCol()->times(solution,rowActivity) ;
    1970   double largestInfeasibility =0.0;
     1970  double largestInfeasibility =primalTolerance;
     1971  double sumInfeasibility=0.0;
     1972  int numberBadRows=0;
    19711973  for (i=0 ; i < numberRows ; i++) {
    1972     largestInfeasibility = CoinMax(largestInfeasibility,
    1973                                rowLower[i]-rowActivity[i]);
    1974     largestInfeasibility = CoinMax(largestInfeasibility,
    1975                                rowActivity[i]-rowUpper[i]);
    1976   }
     1974    double value;
     1975    value = rowLower[i]-rowActivity[i];
     1976    if (value>primalTolerance) {
     1977      numberBadRows++;
     1978      largestInfeasibility = CoinMax(largestInfeasibility,value);
     1979      sumInfeasibility += value;
     1980    }
     1981    value = rowActivity[i]-rowUpper[i];
     1982    if (value>primalTolerance) {
     1983      numberBadRows++;
     1984      largestInfeasibility = CoinMax(largestInfeasibility,value);
     1985      sumInfeasibility += value;
     1986    }
     1987  }
     1988#if 0
     1989  if (largestInfeasibility>primalTolerance&&numberBadRows*10<numberRows) {
     1990    // Can we improve by flipping
     1991    for (int iPass=0;iPass<10;iPass++) {
     1992      int numberColumns = solver->getNumCols();
     1993      const CoinPackedMatrix * matrixByCol = solver->getMatrixByCol();
     1994      const double * element = matrixByCol->getElements();
     1995      const int * row = matrixByCol->getIndices();
     1996      const CoinBigIndex * columnStart = matrixByCol->getVectorStarts();
     1997      const int * columnLength = matrixByCol->getVectorLengths();
     1998      double oldSum = sumInfeasibility;
     1999      // First improve by moving continuous ones
     2000      for (int iColumn=0;iColumn<numberColumns;iColumn++) {
     2001        if (!solver->isInteger(iColumn)) {
     2002          double solValue = solution[iColumn];
     2003          double thetaUp = columnUpper[iColumn]-solValue;
     2004          double improvementUp=0.0;
     2005          if (thetaUp>primalTolerance) {
     2006            // can go up
     2007            for (CoinBigIndex j=columnStart[iColumn];
     2008                 j<columnStart[iColumn]+columnLength[iColumn];j++) {
     2009              int iRow = row[j];
     2010              double distanceUp = rowUpper[iRow]-rowActivity[iRow];
     2011              double distanceDown = rowLower[iRow]-rowActivity[iRow];
     2012              double el = element[j];
     2013              if (el>0.0) {
     2014                // positive element
     2015                if (distanceUp>0.0) {
     2016                  if (thetaUp*el>distanceUp)
     2017                    thetaUp=distanceUp/el;
     2018                } else {
     2019                  improvementUp -= el;
     2020                }
     2021                if (distanceDown>0.0) {
     2022                  if (thetaUp*el>distanceDown)
     2023                    thetaUp=distanceDown/el;
     2024                  improvementUp += el;
     2025                }
     2026              } else {
     2027                // negative element
     2028                if (distanceDown<0.0) {
     2029                  if (thetaUp*el<distanceDown)
     2030                    thetaUp=distanceDown/el;
     2031                } else {
     2032                  improvementUp += el;
     2033                }
     2034                if (distanceUp<0.0) {
     2035                  if (thetaUp*el<distanceUp)
     2036                    thetaUp=distanceUp/el;
     2037                  improvementUp -= el;
     2038                }
     2039              }
     2040            }
     2041          }
     2042          double thetaDown = solValue-columnLower[iColumn];
     2043          double improvementDown=0.0;
     2044          if (thetaDown>primalTolerance) {
     2045            // can go down
     2046            for (CoinBigIndex j=columnStart[iColumn];
     2047                 j<columnStart[iColumn]+columnLength[iColumn];j++) {
     2048              int iRow = row[j];
     2049              double distanceUp = rowUpper[iRow]-rowActivity[iRow];
     2050              double distanceDown = rowLower[iRow]-rowActivity[iRow];
     2051              double el = -element[j]; // not change in sign form up
     2052              if (el>0.0) {
     2053                // positive element
     2054                if (distanceUp>0.0) {
     2055                  if (thetaDown*el>distanceUp)
     2056                    thetaDown=distanceUp/el;
     2057                } else {
     2058                  improvementDown -= el;
     2059                }
     2060                if (distanceDown>0.0) {
     2061                  if (thetaDown*el>distanceDown)
     2062                    thetaDown=distanceDown/el;
     2063                  improvementDown += el;
     2064                }
     2065              } else {
     2066                // negative element
     2067                if (distanceDown<0.0) {
     2068                  if (thetaDown*el<distanceDown)
     2069                    thetaDown=distanceDown/el;
     2070                } else {
     2071                  improvementDown += el;
     2072                }
     2073                if (distanceUp<0.0) {
     2074                  if (thetaDown*el<distanceUp)
     2075                    thetaDown=distanceUp/el;
     2076                  improvementDown -= el;
     2077                }
     2078              }
     2079            }
     2080            if (thetaUp<1.0e-8)
     2081              improvementUp=0.0;
     2082            if (thetaDown<1.0e-8)
     2083              improvementDown=0.0;
     2084            double theta;
     2085            if (improvementUp>=improvementDown) {
     2086              theta=thetaUp;
     2087            } else {
     2088              improvementUp=improvementDown;
     2089              theta=-thetaDown;
     2090            }
     2091            if (improvementUp>1.0e-8&&fabs(theta)>1.0e-8) {
     2092              // Could move
     2093              double oldSum=0.0;
     2094              double newSum=0.0;
     2095              solution[iColumn] += theta;
     2096              for (CoinBigIndex j=columnStart[iColumn];
     2097                   j<columnStart[iColumn]+columnLength[iColumn];j++) {
     2098                int iRow = row[j];
     2099                double lower = rowLower[iRow];
     2100                double upper = rowUpper[iRow];
     2101                double value = rowActivity[iRow];
     2102                if (value>upper)
     2103                  oldSum += value-upper;
     2104                else if (value<lower)
     2105                  oldSum += lower-value;
     2106                value += theta*element[j];
     2107                rowActivity[iRow]=value;
     2108                if (value>upper)
     2109                  newSum += value-upper;
     2110                else if (value<lower)
     2111                  newSum += lower-value;
     2112              }
     2113              assert (newSum<=oldSum);
     2114              sumInfeasibility += newSum-oldSum;
     2115            }
     2116          }
     2117        }
     2118      }
     2119      // Now flip some integers?
     2120#if 0
     2121      for (i=0;i<numberIntegers;i++) {
     2122        int iColumn = integerVariable[i];
     2123        double solValue = solution[iColumn];
     2124        assert (fabs(solValue-floor(solValue+0.5))<1.0e-8);
     2125        double improvementUp=0.0;
     2126        if (columnUpper[iColumn]>=solValue+1.0) {
     2127          // can go up
     2128          double oldSum=0.0;
     2129          double newSum=0.0;
     2130          for (CoinBigIndex j=columnStart[iColumn];
     2131               j<columnStart[iColumn]+columnLength[iColumn];j++) {
     2132            int iRow = row[j];
     2133            double lower = rowLower[iRow];
     2134            double upper = rowUpper[iRow];
     2135            double value = rowActivity[iRow];
     2136            if (value>upper)
     2137              oldSum += value-upper;
     2138            else if (value<lower)
     2139              oldSum += lower-value;
     2140            value += element[j];
     2141            if (value>upper)
     2142              newSum += value-upper;
     2143            else if (value<lower)
     2144              newSum += lower-value;
     2145          }
     2146          improvementUp = oldSum-newSum;
     2147        }
     2148        double improvementDown=0.0;
     2149        if (columnLower[iColumn]<=solValue-1.0) {
     2150          // can go down
     2151          double oldSum=0.0;
     2152          double newSum=0.0;
     2153          for (CoinBigIndex j=columnStart[iColumn];
     2154               j<columnStart[iColumn]+columnLength[iColumn];j++) {
     2155            int iRow = row[j];
     2156            double lower = rowLower[iRow];
     2157            double upper = rowUpper[iRow];
     2158            double value = rowActivity[iRow];
     2159            if (value>upper)
     2160              oldSum += value-upper;
     2161            else if (value<lower)
     2162              oldSum += lower-value;
     2163            value -= element[j];
     2164            if (value>upper)
     2165              newSum += value-upper;
     2166            else if (value<lower)
     2167              newSum += lower-value;
     2168          }
     2169          improvementDown = oldSum-newSum;
     2170        }
     2171        double theta;
     2172        if (improvementUp>=improvementDown) {
     2173          theta=1.0;
     2174        } else {
     2175          improvementUp=improvementDown;
     2176          theta=-1.0;
     2177        }
     2178        if (improvementUp>1.0e-8&&fabs(theta)>1.0e-8) {
     2179          // Could move
     2180          double oldSum=0.0;
     2181          double newSum=0.0;
     2182          solution[iColumn] += theta;
     2183          for (CoinBigIndex j=columnStart[iColumn];
     2184               j<columnStart[iColumn]+columnLength[iColumn];j++) {
     2185            int iRow = row[j];
     2186            double lower = rowLower[iRow];
     2187            double upper = rowUpper[iRow];
     2188            double value = rowActivity[iRow];
     2189            if (value>upper)
     2190              oldSum += value-upper;
     2191            else if (value<lower)
     2192              oldSum += lower-value;
     2193            value += theta*element[j];
     2194            rowActivity[iRow]=value;
     2195            if (value>upper)
     2196              newSum += value-upper;
     2197            else if (value<lower)
     2198              newSum += lower-value;
     2199          }
     2200          assert (newSum<=oldSum);
     2201          sumInfeasibility += newSum-oldSum;
     2202        }
     2203      }
     2204#else
     2205      int bestColumn=-1;
     2206      double bestImprovement=primalTolerance;
     2207      double theta=0.0;
     2208      for (i=0;i<numberIntegers;i++) {
     2209        int iColumn = integerVariable[i];
     2210        double solValue = solution[iColumn];
     2211        assert (fabs(solValue-floor(solValue+0.5))<1.0e-8);
     2212        double improvementUp=0.0;
     2213        if (columnUpper[iColumn]>=solValue+1.0) {
     2214          // can go up
     2215          double oldSum=0.0;
     2216          double newSum=0.0;
     2217          for (CoinBigIndex j=columnStart[iColumn];
     2218               j<columnStart[iColumn]+columnLength[iColumn];j++) {
     2219            int iRow = row[j];
     2220            double lower = rowLower[iRow];
     2221            double upper = rowUpper[iRow];
     2222            double value = rowActivity[iRow];
     2223            if (value>upper)
     2224              oldSum += value-upper;
     2225            else if (value<lower)
     2226              oldSum += lower-value;
     2227            value += element[j];
     2228            if (value>upper)
     2229              newSum += value-upper;
     2230            else if (value<lower)
     2231              newSum += lower-value;
     2232          }
     2233          improvementUp = oldSum-newSum;
     2234        }
     2235        double improvementDown=0.0;
     2236        if (columnLower[iColumn]<=solValue-1.0) {
     2237          // can go down
     2238          double oldSum=0.0;
     2239          double newSum=0.0;
     2240          for (CoinBigIndex j=columnStart[iColumn];
     2241               j<columnStart[iColumn]+columnLength[iColumn];j++) {
     2242            int iRow = row[j];
     2243            double lower = rowLower[iRow];
     2244            double upper = rowUpper[iRow];
     2245            double value = rowActivity[iRow];
     2246            if (value>upper)
     2247              oldSum += value-upper;
     2248            else if (value<lower)
     2249              oldSum += lower-value;
     2250            value -= element[j];
     2251            if (value>upper)
     2252              newSum += value-upper;
     2253            else if (value<lower)
     2254              newSum += lower-value;
     2255          }
     2256          improvementDown = oldSum-newSum;
     2257        }
     2258        double improvement = CoinMax(improvementUp,improvementDown);
     2259        if (improvement>bestImprovement) {
     2260          bestImprovement=improvement;
     2261          bestColumn = iColumn;
     2262          if (improvementUp>improvementDown)
     2263            theta=1.0;
     2264          else
     2265            theta=-1.0;
     2266        }
     2267      }
     2268      if (bestColumn>=0) {
     2269        // Could move
     2270        int iColumn = bestColumn;
     2271        double oldSum=0.0;
     2272        double newSum=0.0;
     2273        solution[iColumn] += theta;
     2274        for (CoinBigIndex j=columnStart[iColumn];
     2275             j<columnStart[iColumn]+columnLength[iColumn];j++) {
     2276          int iRow = row[j];
     2277          double lower = rowLower[iRow];
     2278          double upper = rowUpper[iRow];
     2279          double value = rowActivity[iRow];
     2280          if (value>upper)
     2281            oldSum += value-upper;
     2282          else if (value<lower)
     2283            oldSum += lower-value;
     2284          value += theta*element[j];
     2285          rowActivity[iRow]=value;
     2286          if (value>upper)
     2287            newSum += value-upper;
     2288          else if (value<lower)
     2289            newSum += lower-value;
     2290        }
     2291        assert (newSum<=oldSum);
     2292        sumInfeasibility += newSum-oldSum;
     2293      }
     2294#endif
     2295      if(oldSum <= sumInfeasibility + primalTolerance)
     2296        break; // no good
     2297    }
     2298  }
     2299  //delete [] saveSolution;
     2300#endif
    19772301  delete [] rowActivity;
    19782302  return (largestInfeasibility>primalTolerance) ? 0 : 1;
  • trunk/Cbc/src/CbcHeuristicFPump.hpp

    r1090 r1100  
    55
    66#include "CbcHeuristic.hpp"
    7 #ifdef COIN_HAS_CLP
    8 #include "OsiClpSolverInterface.hpp"
    9 #endif
    107
    118/** Rounding class
  • trunk/Cbc/src/CbcHeuristicLocal.cpp

    r961 r1100  
    593593  memset(used_,0,numberColumns);
    594594}
    595 
     595// Default Constructor
     596CbcHeuristicNaive::CbcHeuristicNaive()
     597  :CbcHeuristic()
     598{
     599  large_=1.0e6;
     600}
     601
     602// Constructor with model - assumed before cuts
     603
     604CbcHeuristicNaive::CbcHeuristicNaive(CbcModel & model)
     605  :CbcHeuristic(model)
     606{
     607  large_=1.0e6;
     608}
     609
     610// Destructor
     611CbcHeuristicNaive::~CbcHeuristicNaive ()
     612{
     613}
     614
     615// Clone
     616CbcHeuristic *
     617CbcHeuristicNaive::clone() const
     618{
     619  return new CbcHeuristicNaive(*this);
     620}
     621// Create C++ lines to get to current state
     622void
     623CbcHeuristicNaive::generateCpp( FILE * fp)
     624{
     625  CbcHeuristicNaive other;
     626  fprintf(fp,"0#include \"CbcHeuristicNaive.hpp\"\n");
     627  fprintf(fp,"3  CbcHeuristicNaive naive(*cbcModel);\n");
     628  CbcHeuristic::generateCpp(fp,"naive");
     629  if (large_!=other.large_)
     630    fprintf(fp,"3  naive.setLarge(%g);\n",large_);
     631  else
     632    fprintf(fp,"4  naive.setLarge(%g);\n",large_);
     633  fprintf(fp,"3  cbcModel->addHeuristic(&naive);\n");
     634}
     635
     636// Copy constructor
     637CbcHeuristicNaive::CbcHeuristicNaive(const CbcHeuristicNaive & rhs)
     638:
     639  CbcHeuristic(rhs),
     640  large_(rhs.large_)
     641{
     642}
     643
     644// Assignment operator
     645CbcHeuristicNaive &
     646CbcHeuristicNaive::operator=( const CbcHeuristicNaive& rhs)
     647{
     648  if (this!=&rhs) {
     649    CbcHeuristic::operator=(rhs);
     650    large_ = rhs.large_;
     651  }
     652  return *this;
     653}
     654
     655// Resets stuff if model changes
     656void
     657CbcHeuristicNaive::resetModel(CbcModel * model)
     658{
     659  CbcHeuristic::resetModel(model);
     660}
     661int
     662CbcHeuristicNaive::solution(double & solutionValue,
     663                         double * betterSolution)
     664{
     665  numCouldRun_++;
     666  // See if to do
     667  bool atRoot = model_->getNodeCount()==0;
     668  int passNumber = model_->getCurrentPassNumber();
     669  if (!when()||(when()==1&&model_->phase()!=1)||!atRoot||passNumber!=1)
     670    return 0; // switched off
     671  // Don't do if it was this heuristic which found solution!
     672  if (this==model_->lastHeuristic())
     673    return 0;
     674  numRuns_++;
     675  double cutoff;
     676  model_->solver()->getDblParam(OsiDualObjectiveLimit,cutoff);
     677  double direction = model_->solver()->getObjSense();
     678  cutoff *= direction;
     679  cutoff = CoinMin(cutoff,solutionValue);
     680  OsiSolverInterface * solver = model_->continuousSolver();
     681  if (!solver)
     682    solver = model_->solver();
     683  const double * colLower = solver->getColLower();
     684  const double * colUpper = solver->getColUpper();
     685  const double * objective = solver->getObjCoefficients();
     686
     687  int numberColumns = model_->getNumCols();
     688  int numberIntegers = model_->numberIntegers();
     689  const int * integerVariable = model_->integerVariable();
    596690 
     691  int i;
     692  bool solutionFound=false;
     693  CoinWarmStartBasis saveBasis;
     694  CoinWarmStartBasis * basis =
     695    dynamic_cast<CoinWarmStartBasis *>(solver->getWarmStart()) ;
     696  if (basis) {
     697    saveBasis = * basis;
     698    delete basis;
     699  }
     700  // First just fix all integers as close to zero as possible
     701  OsiSolverInterface * newSolver = solver->clone();
     702  for (i=0;i<numberIntegers;i++) {
     703    int iColumn=integerVariable[i];
     704    double lower = colLower[iColumn];
     705    double upper = colUpper[iColumn];
     706    double value;
     707    if (lower>0.0)
     708      value=lower;
     709    else if (upper<0.0)
     710      value=upper;
     711    else
     712      value=0.0;
     713    newSolver->setColLower(iColumn,value);
     714    newSolver->setColUpper(iColumn,value);
     715  }
     716  newSolver->initialSolve();
     717  if (newSolver->isProvenOptimal()) {
     718    double solValue = newSolver->getObjValue()*direction ;
     719    if (solValue<cutoff) {
     720      // we have a solution
     721      solutionFound=true;
     722      solutionValue=solValue;
     723      memcpy(betterSolution,newSolver->getColSolution(),
     724             numberColumns*sizeof(double));
     725      printf("Naive fixing close to zero gave solution of %g\n",solutionValue);
     726      cutoff = solValue - model_->getCutoffIncrement();
     727    }
     728  }
     729  // Now fix all integers as close to zero if zero or large cost
     730  int nFix=0;
     731  for (i=0;i<numberIntegers;i++) {
     732    int iColumn=integerVariable[i];
     733    double lower = colLower[iColumn];
     734    double upper = colUpper[iColumn];
     735    double value;
     736    if (fabs(objective[i])>0.0&&fabs(objective[i])<large_) {
     737      nFix++;
     738      if (lower>0.0)
     739        value=lower;
     740      else if (upper<0.0)
     741        value=upper;
     742      else
     743        value=0.0;
     744      newSolver->setColLower(iColumn,value);
     745      newSolver->setColUpper(iColumn,value);
     746    }
     747  }
     748  const double * solution = solver->getColSolution();
     749  if (nFix) {
     750    newSolver->setWarmStart(&saveBasis);
     751    newSolver->setColSolution(solution);
     752    newSolver->initialSolve();
     753    if (newSolver->isProvenOptimal()) {
     754      double solValue = newSolver->getObjValue()*direction ;
     755      if (solValue<cutoff) {
     756        // try branch and bound
     757        double * newSolution = new double [numberColumns];
     758        printf("%d fixed after fixing costs\n",nFix);
     759        int returnCode = smallBranchAndBound(newSolver,
     760                                             numberNodes_,newSolution,
     761                                             solutionValue,
     762                                             solutionValue,"CbcHeuristicNaive1");
     763        if (returnCode<0)
     764          returnCode=0; // returned on size
     765        if ((returnCode&2)!=0) {
     766          // could add cut
     767          returnCode &= ~2;
     768        }
     769        if (returnCode==1) {
     770          // solution
     771          solutionFound=true;
     772          memcpy(betterSolution,newSolution,
     773                 numberColumns*sizeof(double));
     774          printf("Naive fixing zeros gave solution of %g\n",solutionValue);
     775          cutoff = solutionValue - model_->getCutoffIncrement();
     776        }
     777        delete [] newSolution;
     778      }
     779    }
     780  }
     781#if 1
     782  newSolver->setObjSense(-direction); // maximize
     783  newSolver->setWarmStart(&saveBasis);
     784  newSolver->setColSolution(solution);
     785  for (int iColumn=0;iColumn<numberColumns;iColumn++) {
     786    double value = solution[iColumn];
     787    double lower = colLower[iColumn];
     788    double upper = colUpper[iColumn];
     789    double newLower;
     790    double newUpper;
     791    if (newSolver->isInteger(iColumn)) {
     792      newLower = CoinMax(lower,floor(value)-2.0);
     793      newUpper = CoinMin(upper,ceil(value)+2.0);
     794    } else {
     795      newLower = CoinMax(lower,value-1.0e5);
     796      newUpper = CoinMin(upper,value+1.0e-5);
     797    }
     798    newSolver->setColLower(iColumn,newLower);
     799    newSolver->setColUpper(iColumn,newUpper);
     800  }
     801  newSolver->initialSolve();
     802  if (newSolver->isProvenOptimal()) {
     803    double solValue = newSolver->getObjValue()*direction ;
     804    if (solValue<cutoff) {
     805      nFix=0;
     806      newSolver->setObjSense(direction); // correct direction
     807      const double * thisSolution = newSolver->getColSolution();
     808      for (int iColumn=0;iColumn<numberColumns;iColumn++) {
     809        double value = solution[iColumn];
     810        double lower = colLower[iColumn];
     811        double upper = colUpper[iColumn];
     812        double newLower=lower;
     813        double newUpper=upper;
     814        if (newSolver->isInteger(iColumn)) {
     815          if (value<lower+1.0e-6) {
     816            nFix++;
     817            newUpper=lower;
     818          } else if (value>upper-1.0e-6) {
     819            nFix++;
     820            newLower=upper;
     821          } else {
     822            newLower = CoinMax(lower,floor(value)-2.0);
     823            newUpper = CoinMin(upper,ceil(value)+2.0);
     824          }
     825        }
     826        newSolver->setColLower(iColumn,newLower);
     827        newSolver->setColUpper(iColumn,newUpper);
     828      }
     829      // try branch and bound
     830      double * newSolution = new double [numberColumns];
     831      printf("%d fixed after maximizing\n",nFix);
     832      int returnCode = smallBranchAndBound(newSolver,
     833                                           numberNodes_,newSolution,
     834                                           solutionValue,
     835                                           solutionValue,"CbcHeuristicNaive1");
     836      if (returnCode<0)
     837        returnCode=0; // returned on size
     838      if ((returnCode&2)!=0) {
     839        // could add cut
     840        returnCode &= ~2;
     841      }
     842      if (returnCode==1) {
     843        // solution
     844        solutionFound=true;
     845        memcpy(betterSolution,newSolution,
     846               numberColumns*sizeof(double));
     847        printf("Naive maximizing gave solution of %g\n",solutionValue);
     848        cutoff = solutionValue - model_->getCutoffIncrement();
     849      }
     850      delete [] newSolution;
     851    }
     852  }
     853#endif
     854  delete newSolver;
     855  return solutionFound ? 1 : 0;
     856}
     857// update model
     858void CbcHeuristicNaive::setModel(CbcModel * model)
     859{
     860  model_ = model;
     861}
     862
     863 
  • trunk/Cbc/src/CbcHeuristicLocal.hpp

    r765 r1100  
    8181
    8282
     83/** Naive class
     84    a) Fix all ints as close to zero as possible
     85    b) Fix all ints with nonzero costs and < large to zero
     86    c) Put bounds round continuous and UIs and maximize
     87 */
     88
     89class CbcHeuristicNaive : public CbcHeuristic {
     90public:
     91
     92  // Default Constructor
     93  CbcHeuristicNaive ();
     94
     95  /* Constructor with model - assumed before cuts
     96     Initial version does not do Lps
     97  */
     98  CbcHeuristicNaive (CbcModel & model);
     99 
     100  // Copy constructor
     101  CbcHeuristicNaive ( const CbcHeuristicNaive &);
     102   
     103  // Destructor
     104  ~CbcHeuristicNaive ();
     105 
     106  /// Clone
     107  virtual CbcHeuristic * clone() const;
     108
     109  /// Assignment operator
     110  CbcHeuristicNaive & operator=(const CbcHeuristicNaive& rhs);
     111
     112  /// Create C++ lines to get to current state
     113  virtual void generateCpp( FILE * fp) ;
     114
     115  /// Resets stuff if model changes
     116  virtual void resetModel(CbcModel * model);
     117
     118  /// update model (This is needed if cliques update matrix etc)
     119  virtual void setModel(CbcModel * model);
     120 
     121  using CbcHeuristic::solution ;
     122  /** returns 0 if no solution, 1 if valid solution.
     123      Sets solution values if good, sets objective value (only if good)
     124  */
     125  virtual int solution(double & objectiveValue,
     126                       double * newSolution);
     127
     128  /// Sets large cost value
     129  inline void setLargeValue(double value)
     130  { large_=value;}
     131  /// Gets large cost value
     132  inline double largeValue() const
     133  { return large_;}
     134
     135protected:
     136  /// Data
     137  /// Large value
     138  double large_;
     139};
     140
     141
    83142#endif
  • trunk/Cbc/src/CbcHeuristicRINS.cpp

    r1013 r1100  
    671671        }
    672672      }
    673       printf("%d fixed, %d same as cont/int, %d same as int - %d bounded %d in cut\n",
    674              nFix,nCouldFix,nCouldFix2,nBound,nEl);
     673      char generalPrint[200];
     674      sprintf(generalPrint,
     675              "%d fixed, %d same as cont/int, %d same as int - %d bounded %d in cut\n",
     676              nFix,nCouldFix,nCouldFix2,nBound,nEl);
     677      model_->messageHandler()->message(CBC_FPUMP2,model_->messages())
     678        << generalPrint
     679        <<CoinMessageEol;
    675680      if (nFix>numberIntegers/10) {
    676681#if 0
  • trunk/Cbc/src/CbcModel.cpp

    r1089 r1100  
    469469    int numberInteger=0;
    470470    int numberIntegerObj=0;
     471    int numberGeneralIntegerObj=0;
     472    int numberIntegerWeight=0;
    471473    int numberContinuousObj=0;
    472474    double cost=COIN_DBL_MAX;
     
    492494            else if (cost!=objValue)
    493495              cost=-COIN_DBL_MAX;
     496            int gap = (int) (upper[iColumn]-lower[iColumn]);
     497            if (gap>1) {
     498              numberGeneralIntegerObj++;
     499              numberIntegerWeight+=gap;
     500            }
    494501          }
    495502        }
     
    497504    }
    498505    int iType=0;
    499     if (!numberContinuousObj&&numberIntegerObj<=5&&
     506    if (!numberContinuousObj&&numberIntegerObj<=5&&numberIntegerWeight<=100&&
    500507        numberIntegerObj*3<numberObjects_&&!parentModel_&&solver_->getNumRows()>100)
    501508      iType=3;
    502509    else if (!numberContinuousObj&&numberIntegerObj<=100&&
    503         numberIntegerObj*5<numberObjects_&&!parentModel_&&
     510        numberIntegerObj*5<numberObjects_&&numberIntegerWeight<=100&&
     511             !parentModel_&&
    504512             solver_->getNumRows()>100&&cost!=-COIN_DBL_MAX)
    505513      iType=2;
     514    else if (!numberContinuousObj&&numberIntegerObj<=100&&
     515        numberIntegerObj*5<numberObjects_&&
     516             !parentModel_&&
     517             solver_->getNumRows()>100&&cost!=-COIN_DBL_MAX)
     518      iType=8;
    506519    //else if (!numberContinuousObj&&
    507520    //numberIntegerObj*20<numberObjects_&&!parentModel_&&
     
    509522    //iType=8;
    510523    int iTest =getMaximumNodes();
     524#if 0
     525    // Give priority to costed in probing if few
     526    if (!numberContinuousObj&&numberIntegerObj<=100&&
     527        numberIntegerObj*5<numberObjects_)
     528        specialOptions_ |= 4096;
     529#endif
    511530    if (iTest>=987654320&&iTest<987654330&&numberObjects_&&!parentModel_) {
    512531      iType = iTest-987654320;
     
    18261845  if (eventHappened_)
    18271846    feasible=false;
    1828   if(fastNodeDepth_>=0&&!parentModel_) {
     1847  if(fastNodeDepth_>=0&&/*!parentModel_*/(specialOptions_&2048)==0) {
    18291848    // add in a general depth object doClp
    18301849    int type = (fastNodeDepth_ <=100) ? fastNodeDepth_ : -(fastNodeDepth_-100);
     
    18371856    // fake number of objects
    18381857    numberObjects_--;
     1858#ifdef CBC_DETERMINISTIC_THREAD
     1859    // But make sure position is correct
     1860    OsiObject * obj2 = object_[numberObjects_];
     1861    obj = dynamic_cast<CbcObject *> (obj2);
     1862    assert (obj);
     1863    obj->setPosition(numberObjects_);
     1864#endif
    18391865  }
    18401866#ifdef COIN_HAS_CLP
     
    36753701          CbcSimpleIntegerDynamicPseudoCost * obj2 =
    36763702            dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(saveObjects[iObject]) ;
    3677           assert (obj->same(obj2));
     3703          if (obj)
     3704            assert (obj->same(obj2));
    36783705        }
    36793706#endif
     
    71667193*/
    71677194        int numberBefore =
    7168           numberRowCutsBefore+numberColumnCutsBefore+lastNumberCuts ;
     7195          numberRowCutsBefore+lastNumberCuts ;
    71697196        int numberAfter =
    7170           numberRowCutsAfter+numberColumnCutsAfter+lastNumberCuts ;
     7197          numberRowCutsAfter+lastNumberCuts ;
    71717198        // possibly extend whichGenerator
    71727199        resizeWhichGenerator(numberBefore, numberAfter);
     
    72137240        }
    72147241        for (j = numberColumnCutsBefore;j<numberColumnCutsAfter;j++) {
    7215           whichGenerator_[numberBefore++] = i ;
     7242          //whichGenerator_[numberBefore++] = i ;
    72167243          const OsiColCut * thisCut = theseCuts.colCutPtr(j) ;
    72177244          if (thisCut->globallyValid()) {
     
    81698196        numberActiveGenerators++;
    81708197#ifdef JUST_ACTIVE
    8171       double value = count[i] + 5.0*generator_[i]->numberColumnCuts() ;
     8198      double value = count[i] ;
    81728199#else
    8173       double value = generator_[i]->numberCutsInTotal() + 5.0*generator_[i]->numberColumnCuts() ;
     8200      double value = generator_[i]->numberCutsInTotal() ;
    81748201#endif
    81758202#if MODEL7
     
    82318258              howOften = 1000000+SCANCUTS; // wait until next time
    82328259#endif
    8233           } else if (thisCuts<smallProblem) {
     8260          } else if (thisCuts+generator_[i]->numberColumnCuts()<smallProblem) {
    82348261            if (howOften!=1&&!probingWasOnBut) {
    82358262              if (generator_[i]->whatDepth()<0||howOften!=-1) {
     
    82948321          << generator_[i]->numberCutsInTotal()
    82958322          <<generator_[i]->numberColumnCuts()
    8296           <<generator_[i]->numberCutsActive();
     8323          <<generator_[i]->numberCutsActive()
     8324          +generator_[i]->numberColumnCuts();
    82978325        handler_->printing(!numberNodes_&&generator_[i]->timing())
    82988326          <<generator_[i]->timeInCutGenerator();
     
    94519479    CbcObject * obj =
    94529480      dynamic_cast <CbcObject *>(object_[i]) ;
    9453     if (obj)
     9481    if (obj) {
    94549482      obj->setModel(this);
     9483#ifdef CBC_DETERMINISTIC_THREAD
     9484      obj->setPosition(i);
     9485#endif
     9486    }
    94559487  }
    94569488  for (i=0;i<numberCutGenerators_;i++)
     
    1000410036      object_[i]->feasibleRegion(solver_,&usefulInfo);
    1000510037      // If relaxed then leave bounds on basic variables
    10006     if (fixVariables==-1) {
     10038    if (fixVariables==-1&&(specialOptions_&16)==0) {
    1000710039      CoinWarmStartBasis * basis = dynamic_cast<CoinWarmStartBasis*>(saveSolver->getWarmStart()) ;
    1000810040      assert(basis != NULL);
     
    1249512527      if (totalNodes*40<totalIterations)
    1249612528        doClp=false;
    12497       if (oldNode&&fastNodeDepth_>=0&&oldNode->depth()>=testDepth&&!parentModel_
     12529      if (oldNode&&fastNodeDepth_>=0&&oldNode->depth()>=testDepth&&/*!parentModel_*/(specialOptions_&2048)==0
    1249812530          &&doClp&&!cuts.sizeRowCuts()) {
    1249912531        OsiClpSolverInterface * clpSolver
     
    1448114513  double cutoff = getCutoff();
    1448214514  int nAffected=0;
    14483   // Pointers back to objects
    14484   int numberColumns = solver_->getNumCols();
    14485   int * back = new int[numberColumns];
    14486   for (i=0;i<numberColumns;i++)
    14487     back[i]=-1;
    14488   for (i=0;i<numberObjects_;i++) {
    14489     int iColumn = object_[i]->columnNumber();
    14490     assert (iColumn>=0);
    14491     back[iColumn]=i;
    14492   }
    1449314515  while (!tree_->empty()) {
    1449414516    for (iModel=0;iModel<numberModels;iModel++) {
     
    1451514537      //assert (cbcobj);
    1451614538      if (cbcobj) {
     14539#ifdef CBC_DETERMINISTIC_THREAD
    1451714540        CbcObject * object = cbcobj->object();
    1451814541        assert (object);
    14519         // could use variable_??
    14520         int columnNumber = object->columnNumber();
    14521         assert (columnNumber>=0);
    14522         columnNumber = back[columnNumber];
    14523         assert (columnNumber>=0);
    14524         CbcObject * objectNew = dynamic_cast<CbcObject *> (otherModel->object_[columnNumber]);
     14542        int position = object->position();
     14543        assert (position>=0);
     14544        assert (object_[position]==object);
     14545        CbcObject * objectNew =
     14546          dynamic_cast<CbcObject *> (otherModel->object_[position]);
    1452514547        cbcobj->setOriginalObject(objectNew);
     14548#else
     14549        abort(); // should not be here
     14550#endif
    1452614551      }
    1452714552      otherModel->tree_->push(node);
     
    1453114556      break;
    1453214557  }
    14533   delete [] back;
    1453414558  return nAffected;
    1453514559}
     
    1482714851    while (!tree_->empty()) {
    1482814852      CbcNode * node = tree_->bestNode(COIN_DBL_MAX) ;
    14829       if (node->objectiveValue()<cutoff)
     14853      if (node->objectiveValue()<cutoff) {
     14854        CbcNodeInfo * nodeInfo = node->nodeInfo();
     14855        assert (nodeInfo);
     14856        // Make node join correctly
     14857        OsiBranchingObject * bobj = node->modifiableBranchingObject();
     14858        CbcBranchingObject * cbcobj = dynamic_cast<CbcBranchingObject *> (bobj);
     14859        if (cbcobj) {
     14860#ifdef CBC_DETERMINISTIC_THREAD
     14861          CbcObject * object = cbcobj->object();
     14862          assert (object);
     14863          int position = object->position();
     14864          assert (position>=0);
     14865          assert (object_[position]==object);
     14866          CbcObject * objectNew =
     14867            dynamic_cast<CbcObject *> (baseModel->object_[position]);
     14868          cbcobj->setOriginalObject(objectNew);
     14869#else
     14870          abort(); // should not be here
     14871#endif
     14872        }
    1483014873        baseModel->tree_->push(node);
    14831       else
     14874      } else {
    1483214875        delete node;
     14876      }
    1483314877    }
    1483414878    for (i=0;i<stuff->nDeleteNode;i++) {
  • trunk/Cbc/src/CbcSolver.cpp

    r1088 r1100  
    512512  parameters_[whichParam(PIVOTANDFIX,numberParameters_,parameters_)].setCurrentOption("off");
    513513  parameters_[whichParam(RANDROUND,numberParameters_,parameters_)].setCurrentOption("off");
     514  parameters_[whichParam(NAIVE,numberParameters_,parameters_)].setCurrentOption("off");
    514515  parameters_[whichParam(RINS,numberParameters_,parameters_)].setCurrentOption("off");
    515516  parameters_[whichParam(DINS,numberParameters_,parameters_)].setCurrentOption("off");
     
    32153216  parameters[whichParam(PIVOTANDFIX,numberParameters,parameters)].setCurrentOption("off");
    32163217  parameters[whichParam(RANDROUND,numberParameters,parameters)].setCurrentOption("off");
     3218  parameters[whichParam(NAIVE,numberParameters,parameters)].setCurrentOption("off");
    32173219  parameters[whichParam(RINS,numberParameters,parameters)].setCurrentOption("off");
    32183220  parameters[whichParam(DINS,numberParameters,parameters)].setCurrentOption("off");
     
    32493251  int useDINS = parameters_[whichParam(DINS,numberParameters_,parameters_)].currentOptionAsInteger();
    32503252  int useDIVING2 = parameters_[whichParam(DIVINGS,numberParameters_,parameters_)].currentOptionAsInteger();
     3253  int useNaive = parameters_[whichParam(NAIVE,numberParameters_,parameters_)].currentOptionAsInteger();
    32513254  // FPump done first as it only works if no solution
    32523255  int kType = (type<3) ? type : 1;
     
    33853388    anyToDo=true;
    33863389  }
    3387   if (useRINS>=kType) {
    3388     CbcHeuristicRINS heuristic5(*model);
    3389     heuristic5.setHeuristicName("RINS");
    3390     if (useRINS==1) {
    3391       heuristic5.setFractionSmall(0.5);
    3392       heuristic5.setDecayFactor(5.0);
    3393     } else {
    3394       heuristic5.setFractionSmall(0.6);
    3395       heuristic5.setDecayFactor(1.5);
    3396     }
    3397     model->addHeuristic(&heuristic5) ;
     3390  if (useNaive>=kType) {
     3391    CbcHeuristicNaive heuristic5b(*model);
     3392    heuristic5b.setHeuristicName("Naive");
     3393    heuristic5b.setFractionSmall(0.4);
     3394    heuristic5b.setNumberNodes(50);
     3395    model->addHeuristic(&heuristic5b) ;
    33983396    anyToDo=true;
    33993397  }
     
    34083406    heuristic5a.setNumberNodes(1000);
    34093407    model->addHeuristic(&heuristic5a) ;
     3408    anyToDo=true;
     3409  }
     3410  if (useRINS>=kType) {
     3411    CbcHeuristicRINS heuristic5(*model);
     3412    heuristic5.setHeuristicName("RINS");
     3413    if (useRINS==1) {
     3414      heuristic5.setFractionSmall(0.5);
     3415      heuristic5.setDecayFactor(5.0);
     3416    } else {
     3417      heuristic5.setFractionSmall(0.6);
     3418      heuristic5.setDecayFactor(1.5);
     3419    }
     3420    model->addHeuristic(&heuristic5) ;
    34103421    anyToDo=true;
    34113422  }
     
    48304841            case RANDROUND:
    48314842            case LOCALTREE:
     4843            case NAIVE:
    48324844              defaultSettings=false; // user knows what she is doing
    48334845              break;
Note: See TracChangeset for help on using the changeset viewer.