Changeset 11


Ignore:
Timestamp:
Nov 2, 2004 4:52:27 PM (17 years ago)
Author:
forrest
Message:

Trying some odd branching strategies

Location:
trunk
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • trunk/CbcBranchActual.cpp

    r2 r11  
    18451845  return betterWay;
    18461846}
     1847// Default Constructor
     1848CbcFollowOn::CbcFollowOn ()
     1849  : CbcObject(),
     1850    rhs_(NULL)
     1851{
     1852}
     1853
     1854// Useful constructor
     1855CbcFollowOn::CbcFollowOn (CbcModel * model)
     1856  : CbcObject(model)
     1857{
     1858  assert (model);
     1859  OsiSolverInterface * solver = model_->solver();
     1860  matrix_ = *solver->getMatrixByCol();
     1861  matrix_.removeGaps();
     1862  matrixByRow_ = *solver->getMatrixByRow();
     1863  int numberRows = matrix_.getNumRows();
     1864 
     1865  rhs_ = new int[numberRows];
     1866  int i;
     1867  const double * rowLower = solver->getRowLower();
     1868  const double * rowUpper = solver->getRowUpper();
     1869  // Row copy
     1870  const double * elementByRow = matrixByRow_.getElements();
     1871  const int * column = matrixByRow_.getIndices();
     1872  const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
     1873  const int * rowLength = matrixByRow_.getVectorLengths();
     1874  for (i=0;i<numberRows;i++) {
     1875    rhs_[i]=0;
     1876    double value = rowLower[i];
     1877    if (value==rowUpper[i]) {
     1878      if (floor(value)==value&&value>=1.0&&value<10.0) {
     1879        // check elements
     1880        bool good=true;
     1881        for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
     1882          int iColumn = column[j];
     1883          if (!solver->isBinary(iColumn))
     1884            good=false;
     1885          double elValue = elementByRow[j];
     1886          if (floor(elValue)!=elValue||value<1.0)
     1887            good=false;
     1888        }
     1889        if (good)
     1890          rhs_[i]=(int) value;
     1891      }
     1892    }
     1893  }
     1894}
     1895
     1896// Copy constructor
     1897CbcFollowOn::CbcFollowOn ( const CbcFollowOn & rhs)
     1898  :CbcObject(rhs),
     1899   matrix_(rhs.matrix_),
     1900   matrixByRow_(rhs.matrixByRow_)
     1901{
     1902  int numberRows = matrix_.getNumRows();
     1903  rhs_= CoinCopyOfArray(rhs.rhs_,numberRows);
     1904}
     1905
     1906// Clone
     1907CbcObject *
     1908CbcFollowOn::clone() const
     1909{
     1910  return new CbcFollowOn(*this);
     1911}
     1912
     1913// Assignment operator
     1914CbcFollowOn &
     1915CbcFollowOn::operator=( const CbcFollowOn& rhs)
     1916{
     1917  if (this!=&rhs) {
     1918    CbcObject::operator=(rhs);
     1919    delete [] rhs_;
     1920    matrix_ = rhs.matrix_;
     1921    matrixByRow_ = rhs.matrixByRow_;
     1922    int numberRows = matrix_.getNumRows();
     1923    rhs_= CoinCopyOfArray(rhs.rhs_,numberRows);
     1924  }
     1925  return *this;
     1926}
     1927
     1928// Destructor
     1929CbcFollowOn::~CbcFollowOn ()
     1930{
     1931  delete [] rhs_;
     1932}
     1933// As some computation is needed in more than one place - returns row
     1934int
     1935CbcFollowOn::gutsOfFollowOn(int & otherRow) const
     1936{
     1937  int whichRow=-1;
     1938  otherRow=-1;
     1939  int numberRows = matrix_.getNumRows();
     1940 
     1941  int i;
     1942  // For sorting
     1943  int * sort = new int [numberRows];
     1944  int * isort = new int [numberRows];
     1945  // Column copy
     1946  //const double * element = matrix_.getElements();
     1947  const int * row = matrix_.getIndices();
     1948  const CoinBigIndex * columnStart = matrix_.getVectorStarts();
     1949  const int * columnLength = matrix_.getVectorLengths();
     1950  // Row copy
     1951  const double * elementByRow = matrixByRow_.getElements();
     1952  const int * column = matrixByRow_.getIndices();
     1953  const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
     1954  const int * rowLength = matrixByRow_.getVectorLengths();
     1955  OsiSolverInterface * solver = model_->solver();
     1956  const double * columnLower = solver->getColLower();
     1957  const double * columnUpper = solver->getColUpper();
     1958  const double * solution = solver->getColSolution();
     1959  double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance);
     1960  int nSort=0;
     1961  for (i=0;i<numberRows;i++) {
     1962    if (rhs_[i]) {
     1963      // check elements
     1964      double smallest=1.0e10;
     1965      double largest=0.0;
     1966      int rhsValue=rhs_[i];
     1967      int number1=0;
     1968      int numberUnsatisfied=0;
     1969      for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
     1970        int iColumn = column[j];
     1971        double value = elementByRow[j];
     1972        double solValue = solution[iColumn];
     1973        if (columnLower[iColumn]!=columnUpper[iColumn]) {
     1974          smallest = CoinMin(smallest,value);
     1975          largest = CoinMax(largest,value);
     1976          if (value==1.0)
     1977            number1++;
     1978          if (solValue<1.0-integerTolerance&&solValue>integerTolerance)
     1979            numberUnsatisfied++;
     1980        } else {
     1981          rhsValue -= (int)(value*floor(solValue+0.5));
     1982        }
     1983      }
     1984      if (numberUnsatisfied>1) {
     1985        if (smallest<largest) {
     1986          // probably no good but check a few things
     1987          assert (largest<=rhsValue);
     1988          if (number1==1&&largest==rhsValue)
     1989            printf("could fix\n");
     1990        } else if (largest==rhsValue) {
     1991          sort[nSort]=i;
     1992          isort[nSort++]=-numberUnsatisfied;
     1993        }
     1994      }
     1995    }
     1996  }
     1997  if (nSort>1) {
     1998    CoinSort_2(isort,isort+nSort,sort);
     1999    CoinZeroN(isort,numberRows);
     2000    int * which = new int[numberRows];
     2001    for (int k=0;k<nSort-1;k++) {
     2002      i=sort[k];
     2003      int numberUnsatisfied = 0;
     2004      int n=0;
     2005      int j;
     2006      for (j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
     2007        int iColumn = column[j];
     2008        if (columnLower[iColumn]!=columnUpper[iColumn]) {
     2009          double solValue = solution[iColumn];
     2010          if (solValue<1.0-integerTolerance&&solValue>integerTolerance) {
     2011            numberUnsatisfied++;
     2012            for (int jj=columnStart[iColumn];jj<columnStart[iColumn]+columnLength[iColumn];jj++) {
     2013              int iRow = row[jj];
     2014              if (rhs_[iRow]) {
     2015                if (isort[iRow]) {
     2016                  isort[iRow]++;
     2017                } else {
     2018                  isort[iRow]=1;
     2019                  which[n++]=iRow;
     2020                }
     2021              }
     2022            }
     2023          }
     2024        }
     2025      }
     2026      assert (numberUnsatisfied==isort[i]);
     2027      // find one nearest half
     2028      int iBest=-1;
     2029      int target = (numberUnsatisfied+1)>>1;
     2030      int best=numberUnsatisfied;
     2031      for (j=0;j<n;j++) {
     2032        int iRow = which[j];
     2033        int value = isort[iRow];
     2034        isort[iRow]=0;
     2035        if (abs(value-target)<best&&value!=numberUnsatisfied) {
     2036          best=abs(value-target);
     2037          iBest=iRow;
     2038        }
     2039      }
     2040      if (iBest>=0) {
     2041        whichRow=i;
     2042        otherRow=iBest;
     2043        break;
     2044      }
     2045    }
     2046    delete [] which;
     2047  }
     2048  delete [] sort;
     2049  delete [] isort;
     2050  return whichRow;
     2051}
     2052
     2053// Infeasibility - large is 0.5
     2054double
     2055CbcFollowOn::infeasibility(int & preferredWay) const
     2056{
     2057  int otherRow=0;
     2058  int whichRow = gutsOfFollowOn(otherRow);
     2059  preferredWay=-1;
     2060  if (whichRow<0)
     2061    return 0.0;
     2062  else
     2063  return 2.0* model_->getDblParam(CbcModel::CbcIntegerTolerance);
     2064}
     2065
     2066// This looks at solution and sets bounds to contain solution
     2067void
     2068CbcFollowOn::feasibleRegion()
     2069{
     2070}
     2071
     2072
     2073// Creates a branching object
     2074CbcBranchingObject *
     2075CbcFollowOn::createBranch(int way) const
     2076{
     2077  int otherRow=0;
     2078  int whichRow = gutsOfFollowOn(otherRow);
     2079  assert(way==-1);
     2080  assert (whichRow>=0);
     2081  int numberColumns = matrix_.getNumCols();
     2082 
     2083  // Column copy
     2084  //const double * element = matrix_.getElements();
     2085  const int * row = matrix_.getIndices();
     2086  const CoinBigIndex * columnStart = matrix_.getVectorStarts();
     2087  const int * columnLength = matrix_.getVectorLengths();
     2088  // Row copy
     2089  //const double * elementByRow = matrixByRow_.getElements();
     2090  const int * column = matrixByRow_.getIndices();
     2091  const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
     2092  const int * rowLength = matrixByRow_.getVectorLengths();
     2093  OsiSolverInterface * solver = model_->solver();
     2094  const double * columnLower = solver->getColLower();
     2095  const double * columnUpper = solver->getColUpper();
     2096  //const double * solution = solver->getColSolution();
     2097  int nUp=0;
     2098  int nDown=0;
     2099  int * upList = new int[numberColumns];
     2100  int * downList = new int[numberColumns];
     2101  int j;
     2102  for (j=rowStart[whichRow];j<rowStart[whichRow]+rowLength[whichRow];j++) {
     2103    int iColumn = column[j];
     2104    if (columnLower[iColumn]!=columnUpper[iColumn]) {
     2105      bool up=true;
     2106      for (int jj=columnStart[iColumn];jj<columnStart[iColumn]+columnLength[iColumn];jj++) {
     2107        int iRow = row[jj];
     2108        if (iRow==otherRow) {
     2109          up=false;
     2110          break;
     2111        }
     2112      }
     2113      if (up)
     2114        upList[nUp++]=iColumn;
     2115      else
     2116        downList[nDown++]=iColumn;
     2117    }
     2118  }
     2119  //printf("way %d\n",way);
     2120  // create object
     2121  CbcBranchingObject * branch
     2122     = new CbcFixingBranchingObject(model_,way,
     2123                                         nDown,downList,nUp,upList);
     2124  delete [] upList;
     2125  delete [] downList;
     2126  return branch;
     2127}
     2128// Default Constructor
     2129CbcFixingBranchingObject::CbcFixingBranchingObject()
     2130  :CbcBranchingObject()
     2131{
     2132  numberDown_=0;
     2133  numberUp_=0;
     2134  downList_=NULL;
     2135  upList_=NULL;
     2136}
     2137
     2138// Useful constructor
     2139CbcFixingBranchingObject::CbcFixingBranchingObject (CbcModel * model,
     2140                                                    int way ,
     2141                                                    int numberOnDownSide, const int * down,
     2142                                                    int numberOnUpSide, const int * up)
     2143  :CbcBranchingObject(model,0,way,0.5)
     2144{
     2145  numberDown_=numberOnDownSide;
     2146  numberUp_=numberOnUpSide;
     2147  downList_ = CoinCopyOfArray(down,numberDown_);
     2148  upList_ = CoinCopyOfArray(up,numberUp_);
     2149}
     2150
     2151// Copy constructor
     2152CbcFixingBranchingObject::CbcFixingBranchingObject ( const CbcFixingBranchingObject & rhs) :CbcBranchingObject(rhs)
     2153{
     2154  numberDown_=rhs.numberDown_;
     2155  numberUp_=rhs.numberUp_;
     2156  downList_ = CoinCopyOfArray(rhs.downList_,numberDown_);
     2157  upList_ = CoinCopyOfArray(rhs.upList_,numberUp_);
     2158}
     2159
     2160// Assignment operator
     2161CbcFixingBranchingObject &
     2162CbcFixingBranchingObject::operator=( const CbcFixingBranchingObject& rhs)
     2163{
     2164  if (this != &rhs) {
     2165    CbcBranchingObject::operator=(rhs);
     2166    delete [] downList_;
     2167    delete [] upList_;
     2168    numberDown_=rhs.numberDown_;
     2169    numberUp_=rhs.numberUp_;
     2170    downList_ = CoinCopyOfArray(rhs.downList_,numberDown_);
     2171    upList_ = CoinCopyOfArray(rhs.upList_,numberUp_);
     2172  }
     2173  return *this;
     2174}
     2175CbcBranchingObject *
     2176CbcFixingBranchingObject::clone() const
     2177{
     2178  return (new CbcFixingBranchingObject(*this));
     2179}
     2180
     2181
     2182// Destructor
     2183CbcFixingBranchingObject::~CbcFixingBranchingObject ()
     2184{
     2185  delete [] downList_;
     2186  delete [] upList_;
     2187}
     2188double
     2189CbcFixingBranchingObject::branch(bool normalBranch)
     2190{
     2191  if (model_->messageHandler()->logLevel()>2&&normalBranch)
     2192    print(normalBranch);
     2193  numberBranchesLeft_--;
     2194  OsiSolverInterface * solver = model_->solver();
     2195  const double * columnLower = solver->getColLower();
     2196  int i;
     2197  // *** for way - up means fix all those in up section
     2198  if (way_<0) {
     2199#ifdef FULL_PRINT
     2200    printf("Down Fix ");
     2201#endif
     2202    for (i=0;i<numberDown_;i++) {
     2203      int iColumn = downList_[i];
     2204      model_->solver()->setColUpper(iColumn,columnLower[iColumn]);
     2205#ifdef FULL_PRINT
     2206      printf("Setting bound on %d to lower bound\n",iColumn);
     2207#endif
     2208    }
     2209    way_=1;       // Swap direction
     2210  } else {
     2211#ifdef FULL_PRINT
     2212    printf("Up Fix ");
     2213#endif
     2214    for (i=0;i<numberUp_;i++) {
     2215      int iColumn = upList_[i];
     2216      model_->solver()->setColUpper(iColumn,columnLower[iColumn]);
     2217#ifdef FULL_PRINT
     2218      printf("Setting bound on %d to lower bound\n",iColumn);
     2219#endif
     2220    }
     2221    way_=-1;      // Swap direction
     2222  }
     2223#ifdef FULL_PRINT
     2224  printf("\n");
     2225#endif
     2226  return 0.0;
     2227}
     2228void
     2229CbcFixingBranchingObject::print(bool normalBranch)
     2230{
     2231  int i;
     2232  // *** for way - up means fix all those in up section
     2233  if (way_<0) {
     2234    printf("Down Fix ");
     2235    for (i=0;i<numberDown_;i++) {
     2236      int iColumn = downList_[i];
     2237      printf("%d ",iColumn);
     2238    }
     2239  } else {
     2240    printf("Up Fix ");
     2241    for (i=0;i<numberUp_;i++) {
     2242      int iColumn = upList_[i];
     2243      printf("%d ",iColumn);
     2244    }
     2245  }
     2246  printf("\n");
     2247}
  • trunk/CbcBranchCut.cpp

    r6 r11  
    288288  Equivalent to an unspecified binary variable.
    289289*/
    290 CbcBranchOnReducedCost::CbcBranchOnReducedCost ()
     290CbcBranchToFixLots::CbcBranchToFixLots ()
    291291  : CbcBranchCut(),
    292292    djTolerance_(COIN_DBL_MAX),
     
    294294    mark_(NULL),
    295295    depth_(-1),
     296    numberClean_(0),
    296297    alwaysCreate_(false)
    297298{
     
    300301/* Useful constructor - passed reduced cost tolerance and fraction we would like fixed.
    301302   Also depth level to do at.
     303   Also passed number of 1 rows which when clean triggers fix
     304   Always does if all 1 rows cleaned up and number>0 or if fraction columns reached
    302305   Also whether to create branch if can't reach fraction.
    303306*/
    304 CbcBranchOnReducedCost::CbcBranchOnReducedCost (CbcModel * model, double djTolerance,
    305                                                 double fractionFixed, int depth,
    306                                                 const char * mark, bool alwaysCreate)
     307CbcBranchToFixLots::CbcBranchToFixLots (CbcModel * model, double djTolerance,
     308                                        double fractionFixed, int depth,
     309                                        int numberClean,
     310                                        const char * mark, bool alwaysCreate)
    307311  : CbcBranchCut(model)
    308312{
     
    315319  }
    316320  depth_ = depth;
     321  assert (model);
     322  OsiSolverInterface * solver = model_->solver();
     323  matrixByRow_ = *solver->getMatrixByRow();
     324  numberClean_ = numberClean;
    317325  alwaysCreate_ = alwaysCreate;
    318326}
    319327// Copy constructor
    320 CbcBranchOnReducedCost::CbcBranchOnReducedCost ( const CbcBranchOnReducedCost & rhs)
     328CbcBranchToFixLots::CbcBranchToFixLots ( const CbcBranchToFixLots & rhs)
    321329  :CbcBranchCut(rhs)
    322330{
     
    325333  int numberColumns = model_->getNumCols();
    326334  mark_ = CoinCopyOfArray(rhs.mark_,numberColumns);
     335  matrixByRow_=rhs.matrixByRow_;
    327336  depth_ = rhs.depth_;
     337  numberClean_ = rhs.numberClean_;
    328338  alwaysCreate_ = rhs.alwaysCreate_;
    329339}
     
    331341// Clone
    332342CbcObject *
    333 CbcBranchOnReducedCost::clone() const
    334 {
    335   return new CbcBranchOnReducedCost(*this);
     343CbcBranchToFixLots::clone() const
     344{
     345  return new CbcBranchToFixLots(*this);
    336346}
    337347
    338348// Assignment operator
    339 CbcBranchOnReducedCost &
    340 CbcBranchOnReducedCost::operator=( const CbcBranchOnReducedCost& rhs)
     349CbcBranchToFixLots &
     350CbcBranchToFixLots::operator=( const CbcBranchToFixLots& rhs)
    341351{
    342352  if (this!=&rhs) {
     
    346356    int numberColumns = model_->getNumCols();
    347357    mark_ = CoinCopyOfArray(rhs.mark_,numberColumns);
     358    matrixByRow_=rhs.matrixByRow_;
    348359    depth_ = rhs.depth_;
     360    numberClean_ = rhs.numberClean_;
    349361    alwaysCreate_ = rhs.alwaysCreate_;
    350362  }
     
    353365
    354366// Destructor
    355 CbcBranchOnReducedCost::~CbcBranchOnReducedCost ()
     367CbcBranchToFixLots::~CbcBranchToFixLots ()
    356368{
    357369  delete [] mark_;
     
    359371// Creates a branching object
    360372CbcBranchingObject *
    361 CbcBranchOnReducedCost::createBranch(int way) const
     373CbcBranchToFixLots::createBranch(int way) const
    362374{
    363375  // by default way must be -1
     
    371383  int numberIntegers = model_->numberIntegers();
    372384  const int * integerVariable = model_->integerVariable();
    373   int nSort=0;
    374   int nFixed=0;
    375   int * sort = new int[numberIntegers];
    376   double * dsort = new double[numberIntegers];
    377   double tolerance =
     385  double integerTolerance =
    378386    model_->getDblParam(CbcModel::CbcIntegerTolerance);
    379387  // make smaller ?
    380   tolerance = CoinMin(1.0e-8,tolerance);
    381   for (i=0;i<numberIntegers;i++) {
    382     int iColumn = integerVariable[i];
    383     if (upper[iColumn]>lower[iColumn]) {
    384       if (!mark_||!mark_[iColumn]) {
    385         if(solution[iColumn]<lower[iColumn]+tolerance) {
    386           if (dj[iColumn]>djTolerance_) {
    387             dsort[nSort]=-dj[iColumn];
    388             sort[nSort++]=iColumn;
    389           }
    390         } else if (solution[iColumn]>upper[iColumn]-tolerance) {
    391           if (dj[iColumn]<-djTolerance_) {
    392             dsort[nSort]=dj[iColumn];
    393             sort[nSort++]=iColumn;
     388  double tolerance = CoinMin(1.0e-8,integerTolerance);
     389  // How many fixed are we aiming at
     390  int wantedFixed = (int) ((double)numberIntegers*fractionFixed_);
     391  int nSort=0;
     392  int numberFixed=0;
     393  int numberColumns = solver->getNumCols();
     394  int * sort = new int[numberColumns];
     395  double * dsort = new double[numberColumns];
     396  int type = shallWe();
     397  assert (type);
     398  // Take clean first
     399  if (type==1) {
     400    for (i=0;i<numberIntegers;i++) {
     401      int iColumn = integerVariable[i];
     402      if (upper[iColumn]>lower[iColumn]) {
     403        if (!mark_||!mark_[iColumn]) {
     404          if(solution[iColumn]<lower[iColumn]+tolerance) {
     405            if (dj[iColumn]>djTolerance_) {
     406              dsort[nSort]=-dj[iColumn];
     407              sort[nSort++]=iColumn;
     408            }
     409          } else if (solution[iColumn]>upper[iColumn]-tolerance) {
     410            if (dj[iColumn]<-djTolerance_) {
     411              dsort[nSort]=dj[iColumn];
     412              sort[nSort++]=iColumn;
     413            }
    394414          }
    395415        }
    396       }
    397     } else {
    398       nFixed++;
    399     }
    400   }
    401   // sort
    402   CoinSort_2(dsort,dsort+nSort,sort);
    403   // How many fixed are we aiming at
    404   int wantedFixed = (int) ((double)numberIntegers*fractionFixed_);
    405   nSort= CoinMin(nSort,wantedFixed-nFixed);
     416      } else {
     417        numberFixed++;
     418      }
     419    }
     420    // sort
     421    CoinSort_2(dsort,dsort+nSort,sort);
     422    nSort= CoinMin(nSort,wantedFixed-numberFixed);
     423  } else {
     424    int i;
     425    //const double * rowLower = solver->getRowLower();
     426    const double * rowUpper = solver->getRowUpper();
     427    // Row copy
     428    const double * elementByRow = matrixByRow_.getElements();
     429    const int * column = matrixByRow_.getIndices();
     430    const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
     431    const int * rowLength = matrixByRow_.getVectorLengths();
     432    const double * columnLower = solver->getColLower();
     433    const double * columnUpper = solver->getColUpper();
     434    const double * solution = solver->getColSolution();
     435    int numberColumns = solver->getNumCols();
     436    int numberRows = solver->getNumRows();
     437    for (i=0;i<numberColumns;i++) {
     438      sort[i]=i;
     439      if (columnLower[i]!=columnUpper[i]){
     440        dsort[i]=1.0e100;
     441      } else {
     442        dsort[i]=1.0e50;
     443        numberFixed++;
     444      }
     445    }
     446    for (i=0;i<numberRows;i++) {
     447      double rhsValue = rowUpper[i];
     448      bool oneRow=true;
     449      // check elements
     450      int numberUnsatisfied=0;
     451      for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
     452        int iColumn = column[j];
     453        double value = elementByRow[j];
     454        double solValue = solution[iColumn];
     455        if (columnLower[iColumn]!=columnUpper[iColumn]) {
     456          if (solValue<1.0-integerTolerance&&solValue>integerTolerance)
     457            numberUnsatisfied++;
     458          if (value!=1.0) {
     459            oneRow=false;
     460            break;
     461          }
     462        } else {
     463          rhsValue -= value*floor(solValue+0.5);
     464        }
     465      }
     466      if (oneRow&&rhsValue<=1.0+tolerance) {
     467        if (!numberUnsatisfied) {
     468          for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
     469            int iColumn = column[j];
     470            if (dsort[iColumn]>1.0e50){
     471              dsort[iColumn]=0;
     472              nSort++;
     473            }
     474          }
     475        }
     476      }
     477    }
     478    // sort
     479    CoinSort_2(dsort,dsort+numberColumns,sort);
     480  }
    406481  OsiRowCut down;
    407482  down.setLb(-COIN_DBL_MAX);
     
    412487      rhs += lower[iColumn];
    413488      dsort[i]=1.0;
     489      assert (!lower[iColumn]);
    414490    } else {
     491      assert (solution[iColumn]>upper[iColumn]-tolerance);
    415492      rhs -= upper[iColumn];
    416493      dsort[i]=-1.0;
     494      //printf("%d at ub of %g\n",iColumn,upper[iColumn]);
    417495    }
    418496  }
     
    430508  return newObject;
    431509}
     510/* Does a lot of the work,
     511   Returns 0 if no good, 1 if dj, 2 if clean, 3 if both
     512*/
     513int
     514CbcBranchToFixLots::shallWe() const
     515{
     516  int returnCode=0;
     517  OsiSolverInterface * solver = model_->solver();
     518  const double * solution = model_->currentSolution();
     519  const double * lower = solver->getColLower();
     520  const double * upper = solver->getColUpper();
     521  const double * dj = solver->getReducedCost();
     522  int i;
     523  int numberIntegers = model_->numberIntegers();
     524  const int * integerVariable = model_->integerVariable();
     525  double integerTolerance =
     526    model_->getDblParam(CbcModel::CbcIntegerTolerance);
     527  // make smaller ?
     528  double tolerance = CoinMin(1.0e-8,integerTolerance);
     529  // How many fixed are we aiming at
     530  int wantedFixed = (int) ((double)numberIntegers*fractionFixed_);
     531  if (djTolerance_<1.0e10) {
     532    int nSort=0;
     533    int numberFixed=0;
     534    for (i=0;i<numberIntegers;i++) {
     535      int iColumn = integerVariable[i];
     536      if (upper[iColumn]>lower[iColumn]) {
     537        if (!mark_||!mark_[iColumn]) {
     538          if(solution[iColumn]<lower[iColumn]+tolerance) {
     539            if (dj[iColumn]>djTolerance_) {
     540              nSort++;
     541            }
     542          } else if (solution[iColumn]>upper[iColumn]-tolerance) {
     543            if (dj[iColumn]<-djTolerance_) {
     544              nSort++;
     545            }
     546          }
     547        }
     548      } else {
     549        numberFixed++;
     550      }
     551    }
     552    if (numberFixed+nSort<wantedFixed&&!alwaysCreate_) {
     553      returnCode = 0;
     554    } else if (numberFixed<wantedFixed) {
     555      returnCode = 1;
     556    } else {
     557      returnCode = 0;
     558    }
     559  }
     560  if (numberClean_) {
     561    // see how many rows clean
     562    int i;
     563    //const double * rowLower = solver->getRowLower();
     564    const double * rowUpper = solver->getRowUpper();
     565    // Row copy
     566    const double * elementByRow = matrixByRow_.getElements();
     567    const int * column = matrixByRow_.getIndices();
     568    const CoinBigIndex * rowStart = matrixByRow_.getVectorStarts();
     569    const int * rowLength = matrixByRow_.getVectorLengths();
     570    const double * columnLower = solver->getColLower();
     571    const double * columnUpper = solver->getColUpper();
     572    const double * solution = solver->getColSolution();
     573    int numberClean=0;
     574    bool someToDoYet=false;
     575    int numberColumns = solver->getNumCols();
     576    int numberRows = solver->getNumRows();
     577    char * mark = new char[numberColumns];
     578    int numberFixed=0;
     579    for (i=0;i<numberColumns;i++) {
     580      if (columnLower[i]!=columnUpper[i]){
     581        mark[i]=0;
     582      } else {
     583        mark[i]=1;
     584        numberFixed++;
     585      }
     586    }
     587    int numberNewFixed=0;
     588    for (i=0;i<numberRows;i++) {
     589      double rhsValue = rowUpper[i];
     590      bool oneRow=true;
     591      // check elements
     592      int numberUnsatisfied=0;
     593      for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
     594        int iColumn = column[j];
     595        double value = elementByRow[j];
     596        double solValue = solution[iColumn];
     597        if (columnLower[iColumn]!=columnUpper[iColumn]) {
     598          if (solValue<1.0-integerTolerance&&solValue>integerTolerance)
     599            numberUnsatisfied++;
     600          if (value!=1.0) {
     601            oneRow=false;
     602            break;
     603          }
     604        } else {
     605          rhsValue -= value*floor(solValue+0.5);
     606        }
     607      }
     608      if (oneRow&&rhsValue<=1.0+tolerance) {
     609        if (numberUnsatisfied) {
     610          someToDoYet=true;
     611        } else {
     612          numberClean++;
     613          for (int j=rowStart[i];j<rowStart[i]+rowLength[i];j++) {
     614            int iColumn = column[j];
     615            if (columnLower[iColumn]!=columnUpper[iColumn]&&!mark[iColumn]){
     616              mark[iColumn]=1;
     617              numberNewFixed++;
     618            }
     619          }
     620        }
     621      }
     622    }
     623    delete [] mark;
     624    //printf("%d clean, %d old fixed, %d new fixed\n",
     625    //   numberClean,numberFixed,numberNewFixed);
     626    if (someToDoYet&&numberClean<numberClean_
     627        &&numberNewFixed+numberFixed<wantedFixed) {
     628    } else if (numberFixed<wantedFixed) {
     629      returnCode |= 2;
     630    } else {
     631    }
     632  }
     633  return returnCode;
     634}
    432635// Infeasibility - large is 0.5
    433636double
    434 CbcBranchOnReducedCost::infeasibility(int & preferredWay) const
     637CbcBranchToFixLots::infeasibility(int & preferredWay) const
    435638{
    436639  preferredWay=-1;
     
    447650      return 0.0;
    448651  }
    449   OsiSolverInterface * solver = model_->solver();
    450   const double * solution = model_->currentSolution();
    451   const double * lower = solver->getColLower();
    452   const double * upper = solver->getColUpper();
    453   const double * dj = solver->getReducedCost();
    454   int i;
    455   int numberIntegers = model_->numberIntegers();
    456   const int * integerVariable = model_->integerVariable();
    457   int nSort=0;
    458   int nFixed=0;
    459   double tolerance =
    460     model_->getDblParam(CbcModel::CbcIntegerTolerance);
    461   // make smaller ?
    462   tolerance = CoinMin(1.0e-8,tolerance);
    463   for (i=0;i<numberIntegers;i++) {
    464     int iColumn = integerVariable[i];
    465     if (upper[iColumn]>lower[iColumn]) {
    466       if (!mark_||!mark_[iColumn]) {
    467         if(solution[iColumn]<lower[iColumn]+tolerance) {
    468           if (dj[iColumn]>djTolerance_) {
    469             nSort++;
    470           }
    471         } else if (solution[iColumn]>upper[iColumn]-tolerance) {
    472           if (dj[iColumn]<-djTolerance_) {
    473             nSort++;
    474           }
    475         }
    476       }
    477     } else {
    478       nFixed++;
    479     }
    480   }
    481   // How many fixed are we aiming at
    482   int wantedFixed = (int) ((double)numberIntegers*fractionFixed_);
    483   if (nFixed+nSort<wantedFixed&&!alwaysCreate_) {
     652  if (!shallWe())
    484653    return 0.0;
    485   } else if (nFixed<wantedFixed) {
    486     return 1.0e20; // force ?
    487   } else {
    488     return 0.0;
    489   }
    490 }
     654  else
     655    return 1.0e20;
     656}
  • trunk/CbcModel.cpp

    r7 r11  
    22162216    onOptimalPath = (debugger->onOptimalPath(*solver_)) ;
    22172217# endif
    2218   if (nextRowCut_) {
    2219     // branch was a cut - add it
    2220     /*
    2221       Get a basis by asking the solver for warm start information. Resize it
    2222       (retaining the basis) so it can accommodate the cuts.
    2223     */
    2224     delete basis_ ;
    2225     basis_ = dynamic_cast<CoinWarmStartBasis*>(solver_->getWarmStart()) ;
    2226     assert(basis_ != NULL); // make sure not volume
    2227     basis_->resize(numberRowsAtStart+1,numberColumns) ;
    2228     solver_->applyRowCuts(1,&nextRowCut_) ;
    2229     basis_->setArtifStatus(numberRowsAtStart,
    2230                            CoinWarmStartBasis::basic) ;
    2231     cuts.insert(*nextRowCut_);
    2232     nextRowCut_=NULL;
    2233     lastNumberCuts++;
    2234     printf("applying branch cut\n");
    2235   }
    22362218/*
    22372219  Resolve the problem. If we've lost feasibility, might as well bail out right
     
    23272309  needs its own copy of the primal solution. Removed the dec'l.
    23282310*/
     2311    int numberViolated=0;
    23292312    if (currentPassNumber_ == 1 && howOftenGlobalScan_ > 0 &&
    23302313        (numberNodes_%howOftenGlobalScan_) == 0)
    23312314    { int numberCuts = globalCuts_.sizeColCuts() ;
    23322315      int i;
    2333       int numberViolated=0;
    23342316      for ( i = 0 ; i < numberCuts ; i++)
    23352317      { const OsiColCut *thisCut = globalCuts_.colCutPtr(i) ;
     
    23632345  to take full advantage.
    23642346*/
     2347    if (nextRowCut_) {
     2348      // branch was a cut - add it
     2349      theseCuts.insert(*nextRowCut_);
     2350      //nextRowCut_->print();
     2351      const OsiRowCut * cut=nextRowCut_;
     2352      const double * solution = solver_->getColSolution();
     2353      double lb = cut->lb();
     2354      double ub = cut->ub();
     2355      int n=cut->row().getNumElements();
     2356      const int * column = cut->row().getIndices();
     2357      const double * element = cut->row().getElements();
     2358      double sum=0.0;
     2359      for (int i=0;i<n;i++) {
     2360        int iColumn = column[i];
     2361        double value = element[i];
     2362        //if (solution[iColumn]>1.0e-7)
     2363        //printf("value of %d is %g\n",iColumn,solution[iColumn]);
     2364        sum += value * solution[iColumn];
     2365      }
     2366      delete nextRowCut_;
     2367      nextRowCut_=NULL;
     2368      printf("applying branch cut, sum is %g, bounds %g %g\n",sum,lb,ub);
     2369      // set whichgenerator (also serves as marker to say don't delete0
     2370      whichGenerator[numberViolated++]=-2;
     2371    }
    23652372    double * newSolution = new double [numberColumns] ;
    23662373    double heuristicValue = getCutoff() ;
     
    29252932    for (i = 0 ; i < numberNewCuts ; i++)
    29262933    { status = ws->getArtifStatus(i+firstNewCut) ;
    2927       if (status == CoinWarmStartBasis::basic)
     2934      if (status == CoinWarmStartBasis::basic&&whichGenerator[i]!=-2)
    29282935      { solverCutIndices[numberNewToDelete+numberOldToDelete] = i+firstNewCut ;
    29292936        newCutIndices[numberNewToDelete++] = i ; }
     
    41874194  status_ = 0;
    41884195  // solve LP
     4196  //solver_->writeMps("bad");
    41894197  bool feasible = resolve();
    41904198
  • trunk/CbcNode.cpp

    r6 r11  
    10501050  afterwards) and setting up for hot starts.
    10511051*/
    1052   if (numberStrong) {
     1052  if (numberStrong&&model->numberStrong()) {
    10531053   
    10541054    bool solveAll=false; // set true to say look at all even if some fixed (experiment)
  • trunk/include/CbcBranchActual.hpp

    r2 r11  
    55
    66#include "CbcBranchBase.hpp"
    7 
     7#include "CoinPackedMatrix.hpp"
    88
    99/// Define a clique class
     
    686686};
    687687
     688/** Define a follow on class.
     689    The idea of this is that in air-crew scheduling problems crew may fly in on flight A
     690    and out on flight B or on some other flight.  A useful branch is one which on one side
     691    fixes all which go out on flight B to 0, while the other branch fixes all those that do NOT
     692    go out on flight B to 0.
     693
     694    This branching rule should be in addition to normal rules and have a high priority.
     695*/
     696
     697
     698
     699class CbcFollowOn : public CbcObject {
     700
     701public:
     702
     703  // Default Constructor
     704  CbcFollowOn ();
     705
     706  /** Useful constructor
     707  */
     708  CbcFollowOn (CbcModel * model);
     709 
     710  // Copy constructor
     711  CbcFollowOn ( const CbcFollowOn &);
     712   
     713  /// Clone
     714  virtual CbcObject * clone() const;
     715
     716  // Assignment operator
     717  CbcFollowOn & operator=( const CbcFollowOn& rhs);
     718
     719  // Destructor
     720  ~CbcFollowOn ();
     721 
     722  /// Infeasibility - large is 0.5
     723  virtual double infeasibility(int & preferredWay) const;
     724
     725  /// This looks at solution and sets bounds to contain solution
     726  virtual void feasibleRegion();
     727  /// Creates a branching object
     728  virtual CbcBranchingObject * createBranch(int way) const;
     729  /// As some computation is needed in more than one place - returns row
     730  int gutsOfFollowOn(int & otherRow) const;
     731
     732protected:
     733  /// data
     734  /// Matrix
     735  CoinPackedMatrix matrix_;
     736  /// Matrix by row
     737  CoinPackedMatrix matrixByRow_;
     738  /// Possible rhs (if 0 then not possible)
     739  int * rhs_;
     740};
     741/** General Branching Object class.
     742    Each way fixes some variables to lower bound
     743 */
     744class CbcFixingBranchingObject : public CbcBranchingObject {
     745
     746public:
     747
     748  // Default Constructor
     749  CbcFixingBranchingObject ();
     750
     751  // Useful constructor
     752  CbcFixingBranchingObject (CbcModel * model,
     753                            int way,
     754                            int numberOnDownSide, const int * down,
     755                            int numberOnUpSide, const int * up);
     756 
     757  // Copy constructor
     758  CbcFixingBranchingObject ( const CbcFixingBranchingObject &);
     759   
     760  // Assignment operator
     761  CbcFixingBranchingObject & operator=( const CbcFixingBranchingObject& rhs);
     762
     763  /// Clone
     764  virtual CbcBranchingObject * clone() const;
     765
     766  // Destructor
     767  virtual ~CbcFixingBranchingObject ();
     768 
     769  /// Does next branch and updates state
     770  virtual double branch(bool normalBranch=false);
     771
     772  /** \brief Print something about branch - only if log level high
     773  */
     774  virtual void print(bool normalBranch);
     775private:
     776  /// data
     777  /// Number on down list
     778  int numberDown_;
     779  /// Number on up list
     780  int numberUp_;
     781  /// downList - variables to fix to lb on down branch
     782  int * downList_;
     783  /// upList - variables to fix to lb on up branch
     784  int * upList_;
     785};
    688786#endif
  • trunk/include/CbcBranchCut.hpp

    r6 r11  
    66#include "CbcBranchBase.hpp"
    77#include "OsiRowCut.hpp"
     8#include "CoinPackedMatrix.hpp"
    89
    910/** Define a cut branching class.
     
    149150
    150151/** Define a branch class that branches so that one way variables are fixed
    151     while the other way cuts off that solution
     152    while the other way cuts off that solution.
     153    a) On reduced cost
     154    b) When enough ==1 or <=1 rows have been satisfied (not fixed - satisfied)
    152155*/
    153156
    154157
    155 class CbcBranchOnReducedCost : public CbcBranchCut {
     158class CbcBranchToFixLots : public CbcBranchCut {
    156159
    157160public:
    158161
    159162  // Default Constructor
    160   CbcBranchOnReducedCost ();
     163  CbcBranchToFixLots ();
    161164
    162165  /** Useful constructor - passed reduced cost tolerance and fraction we would like fixed.
    163166      Also depth level to do at.
     167      Also passed number of 1 rows which when clean triggers fix
     168      Always does if all 1 rows cleaned up and number>0 or if fraction columns reached
    164169      Also whether to create branch if can't reach fraction.
    165170  */
    166   CbcBranchOnReducedCost (CbcModel * model, double djTolerance,
    167                           double fractionFixed, int depth,
    168                           const char * mark=NULL,
    169                           bool alwaysCreate=false);
     171  CbcBranchToFixLots (CbcModel * model, double djTolerance,
     172                      double fractionFixed, int depth,
     173                      int numberClean=0,
     174                      const char * mark=NULL,
     175                      bool alwaysCreate=false);
    170176 
    171177  // Copy constructor
    172   CbcBranchOnReducedCost ( const CbcBranchOnReducedCost &);
     178  CbcBranchToFixLots ( const CbcBranchToFixLots &);
    173179   
    174180  /// Clone
     
    176182
    177183  // Assignment operator
    178   CbcBranchOnReducedCost & operator=( const CbcBranchOnReducedCost& rhs);
     184  CbcBranchToFixLots & operator=( const CbcBranchToFixLots& rhs);
    179185
    180186  // Destructor
    181   ~CbcBranchOnReducedCost ();
    182  
     187  ~CbcBranchToFixLots ();
     188
     189  /** Does a lot of the work,
     190      Returns 0 if no good, 1 if dj, 2 if clean, 3 if both
     191  */
     192  int shallWe() const;
    183193  /// Infeasibility - large is 0.5
    184194  virtual double infeasibility(int & preferredWay) const;
     
    197207  /// Never fix ones marked here
    198208  char * mark_;
    199   // Do if depth multiple of this
     209  /// Matrix by row
     210  CoinPackedMatrix matrixByRow_;
     211  /// Do if depth multiple of this
    200212  int depth_;
     213  /// number of ==1 rows which need to be clean
     214  int numberClean_;
    201215  /// If true then always create branch
    202216  bool alwaysCreate_;
Note: See TracChangeset for help on using the changeset viewer.