Changeset 135 for trunk/CbcNode.cpp


Ignore:
Timestamp:
May 19, 2005 11:24:16 AM (15 years ago)
Author:
forrest
Message:

starting dynamic pseudo costs

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/CbcNode.cpp

    r130 r135  
    88//#define CBC_DEBUG 1
    99//#define CHECK_CUT_COUNTS
     10//#define CHECK_NODE
    1011#include <cassert>
    1112#include <cfloat>
     
    1718#include "CbcNode.hpp"
    1819#include "CbcBranchActual.hpp"
     20#include "CbcBranchDynamic.hpp"
    1921#include "OsiRowCut.hpp"
    2022#include "OsiRowCutDebugger.hpp"
     
    874876  double * saveSolution = new double[numberColumns];
    875877  memcpy(saveSolution,solver->getColSolution(),numberColumns*sizeof(double));
    876  
     878  model->reserveCurrentSolution(saveSolution);
    877879  /*
    878880    Get a branching decision object. Use the default decision criteria unless
     
    883885    decision = new CbcBranchDefaultDecision();
    884886
    885   typedef struct {
    886     CbcBranchingObject * possibleBranch; // what a branch would do
    887     double upMovement; // cost going up (and initial away from feasible)
    888     double downMovement; // cost going down
    889     int numIntInfeasUp ; // without odd ones
    890     int numObjInfeasUp ; // just odd ones
    891     bool finishedUp; // true if solver finished
    892     int numItersUp ; // number of iterations in solver
    893     int numIntInfeasDown ; // without odd ones
    894     int numObjInfeasDown ; // just odd ones
    895     bool finishedDown; // true if solver finished
    896     int numItersDown; // number of iterations in solver
    897     int objectNumber; // Which object it is
    898     int fix; // 0 if no fix, 1 if we can fix up, -1 if we can fix down
    899   } Strong;
    900   Strong * choice = new Strong[maximumStrong];
     887  CbcStrongInfo * choice = new CbcStrongInfo[maximumStrong];
    901888  for (i=0;i<numberColumns;i++) {
    902889    saveLower[i] = lower[i];
     
    948935      int iSmallest = 0;
    949936      double mostAway = 1.0e-100;
    950       for (i = 0 ; i < maximumStrong ; i++) choice[i].possibleBranch = NULL ;
     937      for (i = 0 ; i < maximumStrong ; i++)
     938        choice[i].possibleBranch = NULL ;
    951939      numberStrong=0;
    952940      for (i=0;i<numberObjects;i++) {
     
    10691057          solver->resolve();
    10701058          memcpy(saveSolution,solver->getColSolution(),numberColumns*sizeof(double));
     1059          model->reserveCurrentSolution(saveSolution);
    10711060          if (!solver->isProvenOptimal()) {
    10721061            // infeasible
     
    11501139      if (osiclp&&(osiclp->specialOptions()&16)!=0&&osiclp->specialOptions()>0)
    11511140        allNormal=false;
     1141      if (osiclp&&!allNormal) {
     1142        // say do fast
     1143        int easy=1;
     1144        osiclp->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,&easy) ;
     1145      }
    11521146      if (osiclp&& allNormal) {
    11531147        clp = osiclp->getModelPtr();
     
    12651259                sol2[iColumn]=saveSolution[iColumn];
    12661260              }
    1267               //printf("strong %d col %d sol %g sol2 %g\n",i,iColumn,sol[iColumn],
    1268               //     sol2[iColumn]);
    1269               //if (fabs(sol[iColumn]-0.5)<0.499)
    1270               //x=false;
    1271               //if (fabs(sol2[iColumn]-0.5)<0.499)
    1272               //x2=false;
    12731261            }
    1274 #if 0
    1275             if( outputStuff[2*i]!=0&&outputStuff[2*i+1]!=0)
    1276               checkSol=false;
    1277             if (x&&checkSol) {
    1278               int iStatus = outputStuff[2*i];
    1279               double newObjectiveValue = objectiveValue+newUpper[i];
    1280               //printf("solution found - status %d obj %g\n",iStatus,newObjectiveValue);
    1281               if (!iStatus) {
    1282                 const double * lower = solver->getRowLower();
    1283                 const double * upper = solver->getRowUpper();
    1284                 int numberRows = solver->getNumRows();
    1285                 double * rhs = new double [numberRows];
    1286                 CoinZeroN(rhs,numberRows);
    1287                 {
    1288                   int numberColumns = solver->getNumCols();
    1289                   const double * columnLower = solver->getColLower();
    1290                   const double * columnUpper = solver->getColUpper();
    1291                   int numberRows = solver->getNumRows();
    1292                  
    1293                   const double * element = matrix->getElements();
    1294                   const int * row = matrix->getIndices();
    1295                   const CoinBigIndex * columnStart = matrix->getVectorStarts();
    1296                   const int * columnLength = matrix->getVectorLengths();
    1297                   CoinZeroN(rhs,numberRows);
    1298                   int iColumn;
    1299                   for (iColumn=0;iColumn<numberColumns;iColumn++) {
    1300                     double lower = columnLower[iColumn];
    1301                     double upper = columnUpper[iColumn];
    1302                     double solValue = sol[iColumn];
    1303                     assert (solValue>=lower-1.0e-4&&solValue<upper+1.0e-4);
    1304                     for (CoinBigIndex j = columnStart[iColumn];
    1305                          j<columnStart[iColumn]+columnLength[iColumn];j++) {
    1306                       int iRow = row[j];
    1307                       double value = element[j];
    1308                       rhs[iRow] += solValue*value;
    1309                       if (iRow==-19)
    1310                         printf("col %d has sol %g and el %g , rhs now %g\n",
    1311                                iColumn,solValue,element[j],rhs[19]);
    1312                     }
    1313                   }
    1314                 }
    1315                 for (int i=0;i<numberRows;i++) {
    1316                   assert (rhs[i]>lower[i]-1.0e-3);
    1317                   assert (rhs[i]<upper[i]+1.0e-3);
    1318                 }
    1319                 delete [] rhs;
    1320               }
    1321             }
    1322             if (x2&&checkSol) {
    1323               int iStatus = outputStuff[2*i+1];
    1324               double newObjectiveValue = objectiveValue+newLower[i];
    1325               //printf("solution found - status %d obj %g\n",iStatus,newObjectiveValue);
    1326               if (!iStatus) {
    1327                 const double * lower = solver->getRowLower();
    1328                 const double * upper = solver->getRowUpper();
    1329                 int numberRows = solver->getNumRows();
    1330                 double * rhs = new double [numberRows];
    1331                 CoinZeroN(rhs,numberRows);
    1332                 solver->getMatrixByCol()->times(sol2,rhs) ;
    1333                 for (int i=0;i<numberRows;i++) {
    1334                   assert (rhs[i]>lower[i]-1.0e-4);
    1335                   assert (rhs[i]<upper[i]+1.0e-4);
    1336                 }
    1337                 delete [] rhs;
    1338               }
    1339             }
    1340 #endif
    13411262          }
    13421263#endif
     
    15631484            // up feasible, down infeasible
    15641485            anyAction=-1;
     1486            //printf("Down infeasible for choice %d sequence %d\n",i,
     1487            // model->object(choice[i].objectNumber)->columnNumber());
    15651488            if (!solveAll) {
    15661489              choice[i].possibleBranch->way(1);
     
    15751498            // down feasible, up infeasible
    15761499            anyAction=-1;
     1500            //printf("Up infeasible for choice %d sequence %d\n",i,
     1501            // model->object(choice[i].objectNumber)->columnNumber());
    15771502            if (!solveAll) {
    15781503              choice[i].possibleBranch->way(-1);
     
    15851510            // neither side feasible
    15861511            anyAction=-2;
     1512            //printf("Both infeasible for choice %d sequence %d\n",i,
     1513            // model->object(choice[i].objectNumber)->columnNumber());
    15871514            break;
    15881515          }
     
    16481575          int numberLeft=0;
    16491576          for (i = 0 ; i < numberStrong ; i++) {
    1650             Strong thisChoice = choice[i];
     1577            CbcStrongInfo thisChoice = choice[i];
    16511578            choice[i].possibleBranch=NULL;
    16521579            const CbcObject * object = model->object(thisChoice.objectNumber);
     
    17161643        // all feasible - choose best bet
    17171644       
    1718 #if 0
    1719         for (i = 0 ; i < numberStrong ; i++)
    1720           { int iColumn =
    1721               model->integerVariable()[choice[i].possibleBranch->variable()] ;
    1722           model->messageHandler()->message(CBC_STRONG,model->messages())
    1723             << i << iColumn
    1724             <<choice[i].downMovement<<choice[i].numIntInfeasDown
    1725             <<choice[i].upMovement<<choice[i].numIntInfeasUp
    1726             <<choice[i].possibleBranch->value()
    1727             <<CoinMessageEol;
    1728           int betterWay = decision->betterBranch(choice[i].possibleBranch,
    1729                                                  branch_,
    1730                                                  choice[i].upMovement,
    1731                                                  choice[i].numIntInfeasUp ,
    1732                                                  choice[i].downMovement,
    1733                                                  choice[i].numIntInfeasDown );
    1734           if (betterWay) {
    1735             delete branch_;
    1736             // C) create branching object
    1737             branch_ = choice[i].possibleBranch;
    1738             choice[i].possibleBranch=NULL;
    1739             branch_->way(betterWay);
    1740           }
    1741           }
    1742 #else
    17431645        // New method does all at once so it can be more sophisticated
    17441646        // in deciding how to balance actions.
     
    17771679        delete [] numberInfeasibilitiesDown;
    17781680        delete [] objects;
    1779 #endif
     1681      }
     1682      if (osiclp&&!allNormal) {
     1683        // back to normal
     1684        osiclp->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,NULL) ;
    17801685      }
    17811686    }
     
    17921697  }
    17931698  // Set guessed solution value
     1699  objectiveValue_ = solver->getObjSense()*saveObjectiveValue;
    17941700  guessedObjectiveValue_ = objectiveValue_+estimatedDegradation;
    17951701/*
     
    18111717}
    18121718
     1719/*
     1720  Version for dynamic pseudo costs.
     1721
     1722  **** For now just return if anything odd
     1723  later allow even if odd
     1724
     1725  The routine scans through the object list of the model looking for objects
     1726  that indicate infeasibility. It tests each object using strong branching
     1727  and selects the one with the least objective degradation.  A corresponding
     1728  branching object is left attached to lastNode.
     1729  This version gives preference in evaluation to variables which
     1730  have not been evaluated many times.  It also uses numberStrong
     1731  to say give up if last few tries have not changed incumbent.
     1732  See Achterberg, Koch and Martin.
     1733
     1734  If strong branching is disabled, a candidate object is chosen essentially
     1735  at random (whatever object ends up in pos'n 0 of the candidate array).
     1736
     1737  If a branching candidate is found to be monotone, bounds are set to fix the
     1738  variable and the routine immediately returns (the caller is expected to
     1739  reoptimize).
     1740
     1741  If a branching candidate is found to result in infeasibility in both
     1742  directions, the routine immediately returns an indication of infeasibility.
     1743
     1744  Returns:  0   both branch directions are feasible
     1745           -1   branching variable is monotone
     1746           -2   infeasible
     1747           -3   Use another method
     1748
     1749           For now just fix on objective from strong branching.
     1750*/
     1751
     1752int CbcNode::chooseDynamicBranch (CbcModel *model, CbcNode *lastNode,int numberPassesLeft)
     1753
     1754{ if (lastNode)
     1755    depth_ = lastNode->depth_+1;
     1756  else
     1757    depth_ = 0;
     1758  delete branch_;
     1759  branch_=NULL;
     1760  OsiSolverInterface * solver = model->solver();
     1761  objectiveValue_ = solver->getObjSense()*solver->getObjValue();
     1762  const double * lower = solver->getColLower();
     1763  const double * upper = solver->getColUpper();
     1764  int anyAction=0;
     1765  int i;
     1766  int stateOfSearch = model->stateOfSearch();
     1767  int numberStrong=model->numberStrong();
     1768  // But make more likely to get out after some times
     1769  int changeStrategy=numberStrong;
     1770  double changeFactor=1.0;
     1771  // Use minimum of this and one stored in objects
     1772  //int numberBeforeTrust = model->numberBeforeTrust();
     1773  int numberObjects = model->numberObjects();
     1774  bool checkFeasibility = numberObjects>model->numberIntegers();
     1775  // For now return if not simple
     1776  if (checkFeasibility)
     1777    return -3;
     1778  // Return if doing hot start (in BAB sense)
     1779  int hotstartStrategy=model->getHotstartStrategy();
     1780  if (hotstartStrategy>0)
     1781    return -3;
     1782  int numberColumns = model->getNumCols();
     1783  double * saveUpper = new double[numberColumns];
     1784  double * saveLower = new double[numberColumns];
     1785
     1786  // Save solution in case heuristics need good solution later
     1787 
     1788  double * saveSolution = new double[numberColumns];
     1789  memcpy(saveSolution,solver->getColSolution(),numberColumns*sizeof(double));
     1790  model->reserveCurrentSolution(saveSolution);
     1791  /*
     1792    Get a branching decision object. Use the default dynamic decision criteria unless
     1793    the user has loaded a decision method into the model.
     1794  */
     1795  CbcBranchDecision *decision = model->branchingMethod();
     1796  if (!decision)
     1797    decision = new CbcBranchDynamicDecision();
     1798
     1799  for (i=0;i<numberColumns;i++) {
     1800    saveLower[i] = lower[i];
     1801    saveUpper[i] = upper[i];
     1802  }
     1803  // Get arrays to sort
     1804  double * sort = new double[numberObjects];
     1805  int * whichObject = new int[numberObjects];
     1806  CbcStrongInfo * fixObject = new CbcStrongInfo[numberObjects];
     1807  double estimatedDegradation=0.0;
     1808  // May go round twice if strong branching fixes all local candidates
     1809  bool finished=false;
     1810  while(!finished) {
     1811    finished=true;
     1812    decision->initialize(model);
     1813    // Some objects may compute an estimate of best solution from here
     1814    estimatedDegradation=0.0;
     1815    int numberToFix=0;
     1816    int numberIntegerInfeasibilities=0; // without odd ones
     1817    int numberToDo=0;
     1818   
     1819    // We may go round this loop twice (only if we think we have solution)
     1820    for (int iPass=0;iPass<2;iPass++) {
     1821     
     1822      // compute current state
     1823      int numberObjectInfeasibilities; // just odd ones
     1824      model->feasibleSolution(
     1825                              numberIntegerInfeasibilities,
     1826                              numberObjectInfeasibilities);
     1827     
     1828      // Some objects may compute an estimate of best solution from here
     1829      estimatedDegradation=0.0;
     1830      numberUnsatisfied_ = 0;
     1831      int bestPriority=INT_MAX;
     1832      /*
     1833        Scan for branching objects that indicate infeasibility. Choose candidates
     1834        using priority as the first criteria, then integer infeasibility.
     1835       
     1836        The algorithm is to fill the array with a set of good candidates (by
     1837        infeasibility) with priority bestPriority.  Finding a candidate with
     1838        priority better (less) than bestPriority flushes the choice array. (This
     1839        serves as initialization when the first candidate is found.)
     1840       
     1841      */
     1842      numberToDo=0;
     1843      for (i=0;i<numberObjects;i++) {
     1844        const CbcObject * object = model->object(i);
     1845        int preferredWay;
     1846        double infeasibility = object->infeasibility(preferredWay);
     1847        int priorityLevel = object->priority();
     1848        if (infeasibility) {
     1849          // Increase estimated degradation to solution
     1850          estimatedDegradation += CoinMin(object->upEstimate(),object->downEstimate());
     1851          numberUnsatisfied_++;
     1852          // Better priority? Flush choices.
     1853          if (priorityLevel<bestPriority) {
     1854            numberToDo=0;
     1855            bestPriority = priorityLevel;
     1856          } else if (priorityLevel>bestPriority) {
     1857            continue;
     1858          }
     1859          // Check for suitability based on infeasibility.
     1860          sort[numberToDo]=-infeasibility;
     1861          whichObject[numberToDo++]=i;
     1862        }
     1863      }
     1864      if (numberUnsatisfied_) {
     1865        // some infeasibilities - go to next steps
     1866        break;
     1867      } else if (!iPass) {
     1868        // looks like a solution - get paranoid
     1869        bool roundAgain=false;
     1870        // get basis
     1871        CoinWarmStartBasis * ws = dynamic_cast<CoinWarmStartBasis*>(solver->getWarmStart());
     1872        if (!ws)
     1873          break;
     1874        for (i=0;i<numberColumns;i++) {
     1875          double value = saveSolution[i];
     1876          if (value<lower[i]) {
     1877            saveSolution[i]=lower[i];
     1878            roundAgain=true;
     1879            ws->setStructStatus(i,CoinWarmStartBasis::atLowerBound);
     1880          } else if (value>upper[i]) {
     1881            saveSolution[i]=upper[i];
     1882            roundAgain=true;
     1883            ws->setStructStatus(i,CoinWarmStartBasis::atUpperBound);
     1884          }
     1885        }
     1886        if (roundAgain) {
     1887          // restore basis
     1888          solver->setWarmStart(ws);
     1889          solver->setColSolution(saveSolution);
     1890          delete ws;
     1891          solver->resolve();
     1892          memcpy(saveSolution,solver->getColSolution(),numberColumns*sizeof(double));
     1893          model->reserveCurrentSolution(saveSolution);
     1894          if (!solver->isProvenOptimal()) {
     1895            // infeasible
     1896            anyAction=-2;
     1897            break;
     1898          }
     1899        } else {
     1900          delete ws;
     1901          break;
     1902        }
     1903      }
     1904    }
     1905    if (anyAction==-2) {
     1906      break;
     1907    }
     1908    bool solveAll=false; // set true to say look at all even if some fixed (experiment)
     1909    solveAll=true;
     1910    // worth trying if too many times
     1911    // Save basis
     1912    CoinWarmStart * ws = solver->getWarmStart();
     1913    // save limit
     1914    int saveLimit;
     1915    solver->getIntParam(OsiMaxNumIterationHotStart,saveLimit);
     1916    if (!stateOfSearch&&saveLimit<100)
     1917      solver->setIntParam(OsiMaxNumIterationHotStart,100);
     1918   
     1919    // Sort
     1920    CoinSort_2(sort,sort+numberToDo,whichObject);
     1921    // Say which one will be best
     1922    int whichChoice=0;
     1923    int bestChoice=-1;
     1924    // If we have hit max time don't do strong branching
     1925    bool hitMaxTime = ( CoinCpuTime()-model->getDblParam(CbcModel::CbcStartSeconds) >
     1926                        model->getDblParam(CbcModel::CbcMaximumSeconds));
     1927    // also give up if we are looping round too much
     1928    if (hitMaxTime||numberPassesLeft<=0) {
     1929      int iObject = whichObject[0];
     1930      CbcObject * object = model->modifiableObject(iObject);
     1931      int preferredWay;
     1932      object->infeasibility(preferredWay);
     1933      branch_=object->createBranch(preferredWay);
     1934      branch_->way(preferredWay);
     1935      break;
     1936    } else {
     1937      // say do fast
     1938      int easy=1;
     1939      solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,&easy) ;
     1940      // Mark hot start
     1941      solver->markHotStart();
     1942      int iDo=0;
     1943      for ( iDo=0;iDo<numberToDo;iDo++) {
     1944        CbcStrongInfo choice;
     1945        int iObject = whichObject[iDo];
     1946        CbcObject * object = model->modifiableObject(iObject);
     1947        CbcSimpleIntegerDynamicPseudoCost * dynamicObject =
     1948          dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object) ;
     1949        int preferredWay;
     1950        object->infeasibility(preferredWay);
     1951        choice.possibleBranch=object->createBranch(preferredWay);
     1952        // Save which object it was
     1953        choice.objectNumber=iObject;
     1954        choice.numIntInfeasUp = numberUnsatisfied_;
     1955        choice.numIntInfeasDown = numberUnsatisfied_;
     1956        choice.fix=0; // say not fixed
     1957        // see if can skip strong branching
     1958        int canSkip = choice.possibleBranch->fillStrongInfo(choice);
     1959        // For now always do
     1960        canSkip=false;
     1961        if (model->messageHandler()->logLevel()>3)
     1962          dynamicObject->print(1,choice.possibleBranch->value());
     1963        if (!canSkip) {
     1964          double objectiveChange ;
     1965          double newObjectiveValue=1.0e100;
     1966          int j;
     1967          // status is 0 finished, 1 infeasible and other
     1968          int iStatus;
     1969          /*
     1970            Try the down direction first. (Specify the initial branching alternative as
     1971            down with a call to way(-1). Each subsequent call to branch() performs the
     1972            specified branch and advances the branch object state to the next branch
     1973            alternative.)
     1974          */
     1975          choice.possibleBranch->way(-1) ;
     1976          decision->saveBranchingObject( choice.possibleBranch);
     1977          choice.possibleBranch->branch() ;
     1978          solver->solveFromHotStart() ;
     1979          /*
     1980            We now have an estimate of objective degradation that we can use for strong
     1981            branching. If we're over the cutoff, the variable is monotone up.
     1982            If we actually made it to optimality, check for a solution, and if we have
     1983            a good one, call setBestSolution to process it. Note that this may reduce the
     1984            cutoff, so we check again to see if we can declare this variable monotone.
     1985          */
     1986          if (solver->isProvenOptimal())
     1987            iStatus=0; // optimal
     1988          else if (solver->isIterationLimitReached()
     1989                   &&!solver->isDualObjectiveLimitReached())
     1990            iStatus=2; // unknown
     1991          else
     1992            iStatus=1; // infeasible
     1993          newObjectiveValue = solver->getObjSense()*solver->getObjValue();
     1994          choice.numItersDown = solver->getIterationCount();
     1995          objectiveChange = newObjectiveValue  - objectiveValue_;
     1996          decision->updateInformation( solver,this);
     1997          if (!iStatus) {
     1998            choice.finishedDown = true ;
     1999            if (newObjectiveValue>=model->getCutoff()) {
     2000              objectiveChange = 1.0e100; // say infeasible
     2001            } else {
     2002              // See if integer solution
     2003              if (model->feasibleSolution(choice.numIntInfeasDown,
     2004                                          choice.numObjInfeasDown)) {
     2005                model->setBestSolution(CBC_STRONGSOL,
     2006                                       newObjectiveValue,
     2007                                       solver->getColSolution()) ;
     2008                if (newObjectiveValue >= model->getCutoff())    //  *new* cutoff
     2009                  objectiveChange = 1.0e100 ;
     2010              }
     2011            }
     2012          } else if (iStatus==1) {
     2013            objectiveChange = 1.0e100 ;
     2014          } else {
     2015            // Can't say much as we did not finish
     2016            choice.finishedDown = false ;
     2017          }
     2018          choice.downMovement = objectiveChange ;
     2019         
     2020          // restore bounds
     2021          for ( j=0;j<numberColumns;j++) {
     2022            if (saveLower[j] != lower[j])
     2023              solver->setColLower(j,saveLower[j]);
     2024            if (saveUpper[j] != upper[j])
     2025              solver->setColUpper(j,saveUpper[j]);
     2026          }
     2027          //printf("Down on %d, status is %d, obj %g its %d cost %g finished %d inf %d infobj %d\n",
     2028          //     choice.objectNumber,iStatus,newObjectiveValue,choice.numItersDown,
     2029          //     choice.downMovement,choice.finishedDown,choice.numIntInfeasDown,
     2030          //     choice.numObjInfeasDown);
     2031         
     2032          // repeat the whole exercise, forcing the variable up
     2033          decision->saveBranchingObject( choice.possibleBranch);
     2034          choice.possibleBranch->branch();
     2035          solver->solveFromHotStart() ;
     2036          /*
     2037            We now have an estimate of objective degradation that we can use for strong
     2038            branching. If we're over the cutoff, the variable is monotone up.
     2039            If we actually made it to optimality, check for a solution, and if we have
     2040            a good one, call setBestSolution to process it. Note that this may reduce the
     2041            cutoff, so we check again to see if we can declare this variable monotone.
     2042          */
     2043          if (solver->isProvenOptimal())
     2044            iStatus=0; // optimal
     2045          else if (solver->isIterationLimitReached()
     2046                   &&!solver->isDualObjectiveLimitReached())
     2047            iStatus=2; // unknown
     2048          else
     2049            iStatus=1; // infeasible
     2050          newObjectiveValue = solver->getObjSense()*solver->getObjValue();
     2051          choice.numItersUp = solver->getIterationCount();
     2052          objectiveChange = newObjectiveValue  - objectiveValue_;
     2053          decision->updateInformation( solver,this);
     2054          if (!iStatus) {
     2055            choice.finishedUp = true ;
     2056            if (newObjectiveValue>=model->getCutoff()) {
     2057              objectiveChange = 1.0e100; // say infeasible
     2058            } else {
     2059              // See if integer solution
     2060              if (model->feasibleSolution(choice.numIntInfeasUp,
     2061                                          choice.numObjInfeasUp)) {
     2062                model->setBestSolution(CBC_STRONGSOL,
     2063                                       newObjectiveValue,
     2064                                       solver->getColSolution()) ;
     2065                if (newObjectiveValue >= model->getCutoff())    //  *new* cutoff
     2066                  objectiveChange = 1.0e100 ;
     2067              }
     2068            }
     2069          } else if (iStatus==1) {
     2070            objectiveChange = 1.0e100 ;
     2071          } else {
     2072            // Can't say much as we did not finish
     2073            choice.finishedUp = false ;
     2074          }
     2075          choice.upMovement = objectiveChange ;
     2076         
     2077          // restore bounds
     2078          for ( j=0;j<numberColumns;j++) {
     2079            if (saveLower[j] != lower[j])
     2080              solver->setColLower(j,saveLower[j]);
     2081            if (saveUpper[j] != upper[j])
     2082              solver->setColUpper(j,saveUpper[j]);
     2083          }
     2084         
     2085          //printf("Up on %d, status is %d, obj %g its %d cost %g finished %d inf %d infobj %d\n",
     2086          //     choice.objectNumber,iStatus,newObjectiveValue,choice.numItersUp,
     2087          //     choice.upMovement,choice.finishedUp,choice.numIntInfeasUp,
     2088          //     choice.numObjInfeasUp);
     2089          hitMaxTime = ( CoinCpuTime()-model->getDblParam(CbcModel::CbcStartSeconds) >
     2090                         model->getDblParam(CbcModel::CbcMaximumSeconds));
     2091          if (hitMaxTime) {
     2092            break;
     2093          }
     2094        }
     2095        /*
     2096          End of evaluation for this candidate variable. Possibilities are:
     2097          * Both sides below cutoff; this variable is a candidate for branching.
     2098          * Both sides infeasible or above the objective cutoff: no further action
     2099          here. Break from the evaluation loop and assume the node will be purged
     2100          by the caller.
     2101          * One side below cutoff: Install the branch (i.e., fix the variable). Break
     2102          from the evaluation loop and assume the node will be reoptimised by the
     2103          caller.
     2104        */
     2105        if (choice.upMovement<1.0e100) {
     2106          if(choice.downMovement<1.0e100) {
     2107            // feasible - see which best
     2108            int iColumn =
     2109              model->integerVariable()[choice.possibleBranch->variable()] ;
     2110            model->messageHandler()->message(CBC_STRONG,model->messages())
     2111              << iObject << iColumn
     2112              <<choice.downMovement<<choice.numIntInfeasDown
     2113              <<choice.upMovement<<choice.numIntInfeasUp
     2114              <<choice.possibleBranch->value()
     2115              <<CoinMessageEol;
     2116            //if (!stateOfSearch)
     2117            //choice.numIntInfeasDown=99999; // temp fudge
     2118            int betterWay = decision->betterBranch(choice.possibleBranch,
     2119                                                   branch_,
     2120                                                   choice.upMovement*changeFactor,
     2121                                                   choice.numIntInfeasUp ,
     2122                                                   choice.downMovement*changeFactor,
     2123                                                   choice.numIntInfeasDown );
     2124            if (iDo>=changeStrategy) {
     2125              // make less likely
     2126              changeStrategy+=numberStrong;
     2127              changeFactor *= 0.9;
     2128            }
     2129            if (betterWay) {
     2130              delete branch_;
     2131              // C) create branching object
     2132              branch_ = choice.possibleBranch;
     2133              choice.possibleBranch=NULL;
     2134              branch_->way(betterWay);
     2135              bestChoice = choice.objectNumber;
     2136              whichChoice = iDo;
     2137            } else {
     2138              delete choice.possibleBranch;
     2139              if (iDo>=2*numberStrong)
     2140                break;
     2141              if (!dynamicObject||dynamicObject->numberTimesUp()>1) {
     2142                if (iDo-whichChoice>=numberStrong)
     2143                  break; // give up
     2144              } else {
     2145                if (iDo-whichChoice>=2*numberStrong)
     2146                  break; // give up
     2147              }
     2148            }
     2149          } else {
     2150            // up feasible, down infeasible
     2151            anyAction=-1;
     2152            //printf("Down infeasible for choice %d sequence %d\n",i,
     2153            // model->object(choice.objectNumber)->columnNumber());
     2154            if (!solveAll) {
     2155              choice.possibleBranch->way(1);
     2156              choice.possibleBranch->branch();
     2157              delete choice.possibleBranch;
     2158              break;
     2159            } else {
     2160              choice.fix=1;
     2161              fixObject[numberToFix++]=choice;
     2162            }
     2163          }
     2164        } else {
     2165          if(choice.downMovement<1.0e100) {
     2166            // down feasible, up infeasible
     2167            anyAction=-1;
     2168            //printf("Up infeasible for choice %d sequence %d\n",i,
     2169            // model->object(choice.objectNumber)->columnNumber());
     2170            if (!solveAll) {
     2171              choice.possibleBranch->way(-1);
     2172              choice.possibleBranch->branch();
     2173              delete choice.possibleBranch;
     2174              break;
     2175            } else {
     2176              choice.fix=-1;
     2177              fixObject[numberToFix++]=choice;
     2178            }
     2179          } else {
     2180            // neither side feasible
     2181            anyAction=-2;
     2182            delete choice.possibleBranch;
     2183            //printf("Both infeasible for choice %d sequence %d\n",i,
     2184            // model->object(choice.objectNumber)->columnNumber());
     2185            break;
     2186          }
     2187        }
     2188      }
     2189      if (model->messageHandler()->logLevel()>3) {
     2190        if (anyAction==-2)
     2191          printf("infeasible\n");
     2192        else if(anyAction==-1)
     2193          printf("%d fixed\n",numberToFix);
     2194        else
     2195          printf("choosing %d\n",bestChoice);
     2196      }
     2197      // Delete the snapshot
     2198      solver->unmarkHotStart();
     2199      // back to normal
     2200      solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,NULL) ;
     2201      solver->setIntParam(OsiMaxNumIterationHotStart,saveLimit);
     2202      // restore basis
     2203      solver->setWarmStart(ws);
     2204      // Unless infeasible we will carry on
     2205      // But we could fix anyway
     2206      if (numberToFix) {
     2207        if (anyAction==-2) {
     2208          // take off
     2209          for (i = 0 ; i < numberToFix ; i++) {
     2210            delete fixObject[i].possibleBranch;
     2211          }
     2212        } else {
     2213          // apply and take off
     2214          for (i = 0 ; i < numberToFix ; i++) {
     2215            fixObject[i].possibleBranch->way(fixObject[i].fix) ;
     2216            fixObject[i].possibleBranch->branch() ;
     2217            delete fixObject[i].possibleBranch;
     2218          }
     2219          bool feasible=true;
     2220          // can do quick optimality check
     2221          int easy=2;
     2222          solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,&easy) ;
     2223          solver->resolve() ;
     2224          solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo,NULL) ;
     2225          feasible = solver->isProvenOptimal();
     2226          if (feasible) {
     2227            anyAction=0;
     2228            memcpy(saveSolution,solver->getColSolution(),numberColumns*sizeof(double));
     2229            model->reserveCurrentSolution(saveSolution);
     2230            memcpy(saveLower,solver->getColLower(),numberColumns*sizeof(double));
     2231            memcpy(saveUpper,solver->getColUpper(),numberColumns*sizeof(double));
     2232            // See if candidate still possible
     2233            if (branch_) {
     2234              const CbcObject * object = model->object(bestChoice);
     2235              int preferredWay;
     2236              double infeasibility = object->infeasibility(preferredWay);
     2237              if (!infeasibility) {
     2238                // take out
     2239                delete branch_;
     2240                branch_=NULL;
     2241              } else {
     2242                branch_->way(preferredWay);
     2243              }
     2244            }
     2245          } else {
     2246            anyAction=-2;
     2247            finished=true;
     2248          }
     2249          // If  fixed then round again
     2250          if (!branch_) {
     2251            finished=false;
     2252          }
     2253          // If these in then different action
     2254#if 0
     2255          //if (!anyAction)
     2256          //anyAction=-1;
     2257          //finished=true;
     2258#endif
     2259        }
     2260      }
     2261      delete ws;
     2262    }
     2263  }
     2264 
     2265  // Set guessed solution value
     2266  guessedObjectiveValue_ = objectiveValue_+estimatedDegradation;
     2267/*
     2268  Cleanup, then we're outta here.
     2269*/
     2270  if (!model->branchingMethod())
     2271    delete decision;
     2272   
     2273  delete [] fixObject;
     2274  delete [] sort;
     2275  delete [] whichObject;
     2276  delete [] saveLower;
     2277  delete [] saveUpper;
     2278 
     2279  // restore solution
     2280  solver->setColSolution(saveSolution);
     2281  model->reserveCurrentSolution(saveSolution);
     2282  delete [] saveSolution;
     2283  return anyAction;
     2284}
     2285
    18132286
    18142287CbcNode::CbcNode(const CbcNode & rhs)
Note: See TracChangeset for help on using the changeset viewer.