Changeset 1802 for trunk/Cbc


Ignore:
Timestamp:
Nov 21, 2012 4:38:56 AM (7 years ago)
Author:
forrest
Message:

add Proximity heuristic (Fischetti and Monaci) - shouldn't break anything

Location:
trunk/Cbc/src
Files:
9 edited

Legend:

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

    r1730 r1802  
    707707    {
    708708        int saveLogLevel = solver->messageHandler()->logLevel();
    709         if (saveLogLevel == 1)
     709        if (saveLogLevel == 1) 
    710710            solver->messageHandler()->setLogLevel(0);
    711711        OsiPresolve * pinfo = new OsiPresolve();
     
    838838    if (solver->isProvenOptimal()) {
    839839        CglPreProcess process;
     840        OsiSolverInterface * solver2 = NULL;
    840841        if ((model_->moreSpecialOptions()&65536)!=0)
    841842          process.setOptions(2+4+8); // no cuts
    842         /* Do not try and produce equality cliques and
    843            do up to 2 passes (normally) 5 if restart */
    844         int numberPasses = 2;
    845         if (numberNodes < 0) {
    846             numberPasses = 5;
    847             // Say some rows cuts
    848             int numberRows = solver->getNumRows();
    849             if (numberNodes_ < numberRows && true /* think */) {
    850                 char * type = new char[numberRows];
    851                 memset(type, 0, numberNodes_);
    852                 memset(type + numberNodes_, 1, numberRows - numberNodes_);
    853                 process.passInRowTypes(type, numberRows);
    854                 delete [] type;
    855             }
    856         }
    857         if (logLevel <= 1)
    858             process.messageHandler()->setLogLevel(0);
     843        /* Do not try and produce equality cliques and
     844           do up to 2 passes (normally) 5 if restart */
     845        int numberPasses = 2;
     846        if (numberNodes < 0) {
     847          numberPasses = 5;
     848          // Say some rows cuts
     849          int numberRows = solver->getNumRows();
     850          if (numberNodes_ < numberRows && true /* think */) {
     851            char * type = new char[numberRows];
     852            memset(type, 0, numberNodes_);
     853            memset(type + numberNodes_, 1, numberRows - numberNodes_);
     854            process.passInRowTypes(type, numberRows);
     855            delete [] type;
     856          }
     857        }
     858        if (logLevel <= 1)
     859          process.messageHandler()->setLogLevel(0);
    859860        if (!solver->defaultHandler()&&
    860861            solver->messageHandler()->logLevel(0)!=-1000)
    861862          process.passInMessageHandler(solver->messageHandler());
    862         OsiSolverInterface * solver2 = process.preProcessNonDefault(*solver, false,
    863                                        numberPasses);
    864         if (!solver2) {
     863        solver2 = process.preProcessNonDefault(*solver, false,
     864                                               numberPasses);
     865          if (!solver2) {
    865866            if (logLevel > 1)
    866                 printf("Pre-processing says infeasible\n");
     867              printf("Pre-processing says infeasible\n");
    867868            returnCode = 2; // so will be infeasible
    868         } else {
     869          } else {
    869870#ifdef COIN_DEVELOP_z
    870871            if (numberNodes < 0) {
    871                 solver2->writeMpsNative("after2.mps", NULL, NULL, 2, 1);
     872              solver2->writeMpsNative("after2.mps", NULL, NULL, 2, 1);
    872873            }
    873874#endif
     
    899900                    // normal
    900901                    model.setSpecialOptions(saveModelOptions | 2048);
    901                     if (logLevel <= 1)
     902                    if (logLevel <= 1 && feasibilityPumpOptions_ != -3)
    902903                        model.setLogLevel(0);
    903904                    else
     
    907908                    model.setCutoff(signedCutoff);
    908909                    // Don't do if original fraction > 1.0 and too large
    909                     if (fractionSmall_>1.0) {
     910                    if (fractionSmall_>1.0 && fractionSmall_ < 1000000.0) {
    910911                      /* 1.4 means -1 nodes if >.4
    911912                         2.4 means -1 nodes if >.5 and 0 otherwise
     
    9991000#endif
    10001001                model.setParentModel(*model_);
    1001                 model.setOriginalColumns(process.originalColumns());
     1002                model.setMaximumSolutions(model_->getMaximumSolutions());
     1003                model.setOriginalColumns(process.originalColumns());
    10021004                model.setSearchStrategy(-1);
    10031005                // If no feasibility pump then insert a lightweight one
    1004                 if (feasibilityPumpOptions_ >= 0) {
    1005                     bool gotPump = false;
     1006                if (feasibilityPumpOptions_ >= 0 || feasibilityPumpOptions_ == -2) {
     1007                    CbcHeuristicFPump * fpump = NULL;
    10061008                    for (int i = 0; i < model.numberHeuristics(); i++) {
    1007                         const CbcHeuristicFPump* pump =
    1008                             dynamic_cast<const CbcHeuristicFPump*>(model.heuristic(i));
    1009                         if (pump)
    1010                             gotPump = true;
     1009                        CbcHeuristicFPump* pump =
     1010                            dynamic_cast<CbcHeuristicFPump*>(model.heuristic(i));
     1011                        if (pump) {
     1012                            fpump = pump;
     1013                            break;
     1014                        }
    10111015                    }
    1012                     if (!gotPump) {
     1016                    if (!fpump) {
    10131017                        CbcHeuristicFPump heuristic4;
    10141018                        // use any cutoff
     
    10171021                          heuristic4.setMaximumPasses(10);
    10181022                        int pumpTune = feasibilityPumpOptions_;
     1023                        if (pumpTune==-2)
     1024                          pumpTune = 4; // proximity
    10191025                        if (pumpTune > 0) {
    10201026                            /*
     
    10731079                        }
    10741080                        model.addHeuristic(&heuristic4, "feasibility pump", 0);
     1081       
    10751082                    }
    1076                 }
     1083                } else if (feasibilityPumpOptions_==-3) {
     1084                  // add all (except this)
     1085                  for (int i = 0; i < model_->numberHeuristics(); i++) {
     1086                    if (strcmp(heuristicName(),model_->heuristic(i)->heuristicName()))
     1087                      model.addHeuristic(model_->heuristic(i));
     1088                  }
     1089                }
    10771090                //printf("sol %x\n",inputSolution_);
    10781091                if (inputSolution_) {
     
    11691182#define ALWAYS_DUAL
    11701183#ifdef ALWAYS_DUAL
    1171                     OsiSolverInterface * solver = model.solver();
     1184                    OsiSolverInterface * solverD = model.solver();
    11721185                    bool takeHint;
    11731186                    OsiHintStrength strength;
    1174                     solver->getHintParam(OsiDoDualInResolve, takeHint, strength);
    1175                     solver->setHintParam(OsiDoDualInResolve, true, OsiHintDo);
     1187                    solverD->getHintParam(OsiDoDualInResolve, takeHint, strength);
     1188                    solverD->setHintParam(OsiDoDualInResolve, true, OsiHintDo);
    11761189#endif
    11771190                    model.passInEventHandler(model_->getEventHandler());
     
    11821195                    model_->setSpecialOptions(saveOptions);
    11831196#ifdef ALWAYS_DUAL
    1184                     solver = model.solver();
    1185                     solver->setHintParam(OsiDoDualInResolve, takeHint, strength);
     1197                    solverD = model.solver();
     1198                    solverD->setHintParam(OsiDoDualInResolve, takeHint, strength);
    11861199#endif
    11871200#ifdef COIN_DEVELOP
     
    12381251                    }
    12391252#endif
    1240                     process.postProcess(*model.solver());
     1253                    //if (fractionSmall_ < 1000000.0)
     1254                      process.postProcess(*model.solver());
    12411255                    if (solver->isProvenOptimal() && solver->getObjValue()*solver->getObjSense() < cutoff) {
    12421256                        // Solution now back in solver
     
    12561270                                            process.numberIterationsPre() +
    12571271                                            process.numberIterationsPost();
    1258                 if (totalNumberIterations > 100*(numberNodes + 10)) {
     1272                if (totalNumberIterations > 100*(numberNodes + 10)
     1273                    && fractionSmall_ < 1000000.0) {
    12591274                    // only allow smaller problems
    12601275                    fractionSmall = fractionSmall_;
  • trunk/Cbc/src/CbcHeuristic.hpp

    r1600 r1802  
    155155                first try halving distance to best possible then
    156156                try keep halving distance to known cutoff
     157        16 bit - needs new solution to run
    157158        1024 bit - stop all heuristics on max time
    158159    */
     
    167168                first try halving distance to best possible then
    168169                try keep halving distance to known cutoff
     170        16 bit - needs new solution to run
    169171        1024 bit - stop all heuristics on max time
    170172    */
     
    314316    /// Number of nodes in any sub tree
    315317    int numberNodes_;
    316     /// Feasibility pump options (-1 is off)
     318    /** Feasibility pump options , -1 is off
     319        >=0 for feasibility pump itself
     320        -2 quick proximity search
     321        -3 longer proximity search
     322    */
    317323    int feasibilityPumpOptions_;
    318324    /// Fraction of new(rows+columns)/old(rows+columns) before doing small branch and bound
     
    334340                first try halving distance to best possible then
    335341                try keep halving distance to known cutoff
     342        16 bit - needs new solution to run
    336343        1024 bit - stop all heuristics on max time
    337344    */
  • trunk/Cbc/src/CbcHeuristicFPump.cpp

    r1573 r1802  
    378378    double * newSolution = new double [numberColumns];
    379379    double newSolutionValue = COIN_DBL_MAX;
     380    int maxSolutions = model_->getMaximumSolutions();
     381    int numberSolutions=0;
    380382    bool solutionFound = false;
    381383    int * usedColumn = NULL;
     
    447449    bool exitAll = false;
    448450    //double saveBestObjective = model_->getMinimizationObjValue();
    449     int numberSolutions = 0;
    450451    OsiSolverInterface * solver = NULL;
    451452    double artificialFactor = 0.00001;
     
    848849                        if ((accumulate_&1) != 0) {
    849850                            model_->incrementUsed(betterSolution); // for local search
    850                             numberSolutions++;
    851851                        }
    852852                        solutionValue = newSolutionValue;
    853853                        solutionFound = true;
     854                        numberSolutions++;
     855                        if (numberSolutions>=maxSolutions)
     856                          exitAll = true;
    854857                        if (general && saveValue != newSolutionValue) {
    855858                            sprintf(pumpPrint, "Cleaned solution of %g", solutionValue);
     
    10681071                                dynamic_cast<CoinWarmStartBasis *>(solver->getWarmStart()) ;
    10691072                            solutionFound = true;
     1073                            numberSolutions++;
     1074                            if (numberSolutions>=maxSolutions)
     1075                              exitAll = true;
    10701076                            if (exitNow(newSolutionValue))
    10711077                                exitAll = true;
     
    10891095                            if ((accumulate_&1) != 0) {
    10901096                                model_->incrementUsed(betterSolution); // for local search
    1091                                 numberSolutions++;
    10921097                            }
    10931098                            solutionValue = newSolutionValue;
    10941099                            solutionFound = true;
     1100                            numberSolutions++;
     1101                            if (numberSolutions>=maxSolutions)
     1102                              exitAll = true;
    10951103                            if (exitNow(newSolutionValue))
    10961104                                exitAll = true;
     
    16401648            memcpy(betterSolution, roundingSolution, numberColumns*sizeof(double));
    16411649            solutionFound = true;
     1650            numberSolutions++;
     1651            if (numberSolutions>=maxSolutions)
     1652              exitAll = true;
    16421653            if (exitNow(roundingObjective))
    16431654                exitAll = true;
     
    19581969                    if ((accumulate_&1) != 0) {
    19591970                        model_->incrementUsed(betterSolution); // for local search
    1960                         numberSolutions++;
    19611971                    }
    19621972                    solutionValue = newSolutionValue;
    19631973                    solutionFound = true;
     1974                    numberSolutions++;
     1975                    if (numberSolutions>=maxSolutions)
     1976                      exitAll = true;
    19641977                    if (exitNow(newSolutionValue))
    19651978                        exitAll = true;
     
    20672080            solutionValue = newSolutionValue;
    20682081            solutionFound = true;
     2082            numberSolutions++;
     2083            if (numberSolutions>=maxSolutions)
     2084              exitAll = true;
    20692085            if (exitNow(newSolutionValue))
    20702086                exitAll = true;
     
    20842100        sprintf(pumpPrint, "After %.2f seconds - Feasibility pump exiting - took %.2f seconds",
    20852101                model_->getCurrentSeconds(), CoinCpuTime() - time1);
    2086     else
    2087         sprintf(pumpPrint, "After %.2f seconds - Feasibility pump exiting with objective of %g - took %.2f seconds",
    2088                 model_->getCurrentSeconds(), solutionValue, CoinCpuTime() - time1);
     2102    else if (numberSolutions < maxSolutions)
     2103      sprintf(pumpPrint, "After %.2f seconds - Feasibility pump exiting with objective of %g - took %.2f seconds",
     2104              model_->getCurrentSeconds(), solutionValue, CoinCpuTime() - time1);
     2105    else
     2106        sprintf(pumpPrint, "After %.2f seconds - Feasibility pump exiting with objective of %g (stopping after %d solutions) - took %.2f seconds",
     2107                model_->getCurrentSeconds(), solutionValue,
     2108                numberSolutions,CoinCpuTime() - time1);
    20892109    model_->messageHandler()->message(CBC_FPUMP1, model_->messages())
    2090     << pumpPrint
    2091     << CoinMessageEol;
     2110      << pumpPrint
     2111      << CoinMessageEol;
    20922112    if (bestBasis.getNumStructural())
    20932113        model_->setBestSolutionBasis(bestBasis);
  • trunk/Cbc/src/CbcHeuristicLocal.cpp

    r1641 r1802  
    1717#include "CbcMessage.hpp"
    1818#include "CbcHeuristicLocal.hpp"
     19#include "CbcHeuristicFPump.hpp"
    1920#include "CbcBranchActual.hpp"
    2021#include "CbcStrategy.hpp"
     
    2930    used_ = NULL;
    3031    lastRunDeep_ = -1000000;
     32    switches_ |= 16; // needs a new solution
    3133}
    3234
     
    3941    swap_ = 0;
    4042    lastRunDeep_ = -1000000;
     43    switches_ |= 16; // needs a new solution
    4144    // Get a copy of original matrix
    4245    assert(model.solver());
     
    928931    memset(used_, 0, numberColumns*sizeof(int));
    929932}
     933
     934// Default Constructor
     935CbcHeuristicProximity::CbcHeuristicProximity()
     936        : CbcHeuristic()
     937{
     938    feasibilityPump_ = NULL;
     939    numberSolutions_ = 0;
     940    used_ = NULL;
     941    lastRunDeep_ = -1000000;
     942    switches_ |= 16; // needs a new solution
     943}
     944
     945// Constructor with model - assumed before cuts
     946
     947CbcHeuristicProximity::CbcHeuristicProximity(CbcModel & model)
     948        : CbcHeuristic(model)
     949{
     950    feasibilityPump_ = NULL;
     951    numberSolutions_ = 0;
     952    lastRunDeep_ = -1000000;
     953    switches_ |= 16; // needs a new solution
     954    int numberColumns = model.solver()->getNumCols();
     955    used_ = new int[numberColumns];
     956    memset(used_, 0, numberColumns*sizeof(int));
     957}
     958
     959// Destructor
     960CbcHeuristicProximity::~CbcHeuristicProximity ()
     961{
     962    delete feasibilityPump_;
     963    delete [] used_;
     964}
     965
     966// Clone
     967CbcHeuristic *
     968CbcHeuristicProximity::clone() const
     969{
     970    return new CbcHeuristicProximity(*this);
     971}
     972// Create C++ lines to get to current state
     973void
     974CbcHeuristicProximity::generateCpp( FILE * fp)
     975{
     976    CbcHeuristicProximity other;
     977    fprintf(fp, "0#include \"CbcHeuristicProximity.hpp\"\n");
     978    fprintf(fp, "3  CbcHeuristicProximity heuristicProximity(*cbcModel);\n");
     979    CbcHeuristic::generateCpp(fp, "heuristicProximity");
     980    fprintf(fp, "3  cbcModel->addHeuristic(&heuristicProximity);\n");
     981}
     982
     983// Copy constructor
     984CbcHeuristicProximity::CbcHeuristicProximity(const CbcHeuristicProximity & rhs)
     985  :
     986  CbcHeuristic(rhs),
     987  numberSolutions_(rhs.numberSolutions_)
     988{
     989    feasibilityPump_ = NULL;
     990    if (model_ && rhs.used_) {
     991        int numberColumns = model_->solver()->getNumCols();
     992        used_ = CoinCopyOfArray(rhs.used_, numberColumns);
     993        if (rhs.feasibilityPump_)
     994          feasibilityPump_ = new CbcHeuristicFPump(*rhs.feasibilityPump_);
     995    } else {
     996        used_ = NULL;
     997    }
     998}
     999
     1000// Assignment operator
     1001CbcHeuristicProximity &
     1002CbcHeuristicProximity::operator=( const CbcHeuristicProximity & rhs)
     1003{
     1004    if (this != &rhs) {
     1005        CbcHeuristic::operator=(rhs);
     1006        numberSolutions_ = rhs.numberSolutions_;
     1007        delete [] used_;
     1008        delete feasibilityPump_;
     1009        feasibilityPump_ = NULL;
     1010        if (model_ && rhs.used_) {
     1011            int numberColumns = model_->solver()->getNumCols();
     1012            used_ = CoinCopyOfArray(rhs.used_, numberColumns);
     1013            if (rhs.feasibilityPump_)
     1014              feasibilityPump_ = new CbcHeuristicFPump(*rhs.feasibilityPump_);
     1015        } else {
     1016            used_ = NULL;
     1017        }
     1018    }
     1019    return *this;
     1020}
     1021
     1022// Resets stuff if model changes
     1023void
     1024CbcHeuristicProximity::resetModel(CbcModel * /*model*/)
     1025{
     1026    //CbcHeuristic::resetModel(model);
     1027    delete [] used_;
     1028    if (model_ && used_) {
     1029        int numberColumns = model_->solver()->getNumCols();
     1030        used_ = new int[numberColumns];
     1031        memset(used_, 0, numberColumns*sizeof(int));
     1032    } else {
     1033        used_ = NULL;
     1034    }
     1035}
     1036/*
     1037  Run a mini-BaB search after changing objective
     1038
     1039  Return values are:
     1040    1: smallBranchAndBound found a solution
     1041    0: everything else
     1042
     1043  The degree of overload as return codes from smallBranchAndBound are folded
     1044  into 0 is such that it's impossible to distinguish return codes that really
     1045  require attention from a simple `nothing of interest'.
     1046*/
     1047int
     1048CbcHeuristicProximity::solution(double & solutionValue,
     1049                            double * betterSolution)
     1050{
     1051  if (feasibilityPumpOptions_ == -3 && numCouldRun_==0 &&
     1052      !feasibilityPump_ ) {
     1053    // clone feasibility pump
     1054    for (int i = 0; i < model_->numberHeuristics(); i++) {
     1055      const CbcHeuristicFPump* pump =
     1056        dynamic_cast<const CbcHeuristicFPump*>(model_->heuristic(i));
     1057      if (pump) {
     1058        feasibilityPump_ = new CbcHeuristicFPump(*pump);
     1059        break;
     1060      }
     1061    }
     1062  }
     1063/*
     1064  Execute only if a new solution has been discovered since the last time we
     1065  were called.
     1066*/
     1067
     1068  numCouldRun_++;
     1069  int nodeCount = model_->getNodeCount();
     1070  if (numberSolutions_ == model_->getSolutionCount())
     1071    return 0;
     1072  numberSolutions_ = model_->getSolutionCount();
     1073  lastRunDeep_ = nodeCount;
     1074  numRuns_++;
     1075  //howOftenShallow_ = numberSolutions_;
     1076 
     1077/*
     1078  Load up a new solver with the solution.
     1079
     1080  Why continuousSolver(), as opposed to solver()?
     1081*/
     1082  OsiSolverInterface * newSolver = model_->continuousSolver()->clone();
     1083  int numberColumns=newSolver->getNumCols();
     1084  double * obj = CoinCopyOfArray(newSolver->getObjCoefficients(),numberColumns);
     1085  int * indices = new int [numberColumns];
     1086  int n=0;
     1087  for (int i=0;i<numberColumns;i++) {
     1088    if (obj[i]) {
     1089      indices[n]=i;
     1090      obj[n++]=obj[i];
     1091    }
     1092  }
     1093  double cutoff=model_->getCutoff();
     1094  assert (cutoff<1.0e20);
     1095  if (model_->getCutoffIncrement()<1.0e-4)
     1096    cutoff -= 0.01;
     1097  double offset;
     1098  newSolver->getDblParam(OsiObjOffset, offset);
     1099  newSolver->setDblParam(OsiObjOffset, 0.0);
     1100  newSolver->addRow(n,indices,obj,-COIN_DBL_MAX,cutoff+offset);
     1101  delete [] indices;
     1102  memset(obj,0,numberColumns*sizeof(double));
     1103  newSolver->setDblParam(OsiDualObjectiveLimit, 1.0e20);
     1104  int numberIntegers = model_->numberIntegers();
     1105  const int * integerVariable = model_->integerVariable();
     1106  const double * solutionIn = model_->bestSolution();
     1107  for (int i = 0; i < numberIntegers; i++) {
     1108    int iColumn = integerVariable[i];
     1109    if (fabs(solutionIn[iColumn])<1.0e-5)
     1110      obj[iColumn]=1.0;
     1111    else if (fabs(solutionIn[iColumn]-1.0)<1.0e-5)
     1112      obj[iColumn]=-1.0;
     1113  }
     1114  newSolver->setObjective(obj);
     1115  delete [] obj;
     1116  //newSolver->writeMps("xxxx");
     1117  char proxPrint[200];
     1118  sprintf(proxPrint,"Running proximity search for %d nodes",numberNodes_);
     1119  model_->messageHandler()->message(CBC_FPUMP1, model_->messages())
     1120    << proxPrint
     1121    << CoinMessageEol;
     1122  int maxSolutions = model_->getMaximumSolutions();
     1123  model_->setMaximumSolutions(1);
     1124  bool pumpAdded = false;
     1125  if (feasibilityPumpOptions_ == -3 && feasibilityPump_) {
     1126    // add back feasibility pump
     1127    pumpAdded = true;
     1128    for (int i = 0; i < model_->numberHeuristics(); i++) {
     1129      const CbcHeuristicFPump* pump =
     1130        dynamic_cast<const CbcHeuristicFPump*>(model_->heuristic(i));
     1131      if (pump) {
     1132        pumpAdded = false;
     1133        break;
     1134      }
     1135    }
     1136    if (pumpAdded)
     1137      model_->addHeuristic(feasibilityPump_);
     1138  }
     1139  int returnCode =
     1140    smallBranchAndBound(newSolver, numberNodes_, betterSolution, solutionValue,
     1141                        1.0e20, "CbcHeuristicProximity");
     1142  if (pumpAdded) {
     1143    // take off feasibility pump
     1144    int lastHeuristic = model_->numberHeuristics()-1;
     1145    model_->setNumberHeuristics(lastHeuristic);
     1146    delete model_->heuristic(lastHeuristic);
     1147  }
     1148  model_->setMaximumSolutions(maxSolutions);
     1149 /*
     1150  -2 is return due to user event, and -1 is overloaded with what look to be
     1151  two contradictory meanings.
     1152*/
     1153  if (returnCode < 0) {
     1154    returnCode = 0;
     1155  }
     1156/*
     1157  If the result is complete exploration with a solution (3) or proven
     1158  infeasibility (2), we could generate a cut (the AI folks would call it a
     1159  nogood) to prevent us from going down this route in the future.
     1160*/
     1161  if ((returnCode&2) != 0) {
     1162    // could add cut
     1163    returnCode &= ~2;
     1164  }
     1165  if ((returnCode&1) != 0) {
     1166    // redo objective
     1167    const double * obj = model_->continuousSolver()->getObjCoefficients();
     1168    solutionValue = - offset;
     1169    for (int i=0;i<numberColumns;i++) {
     1170      solutionValue += obj[i]*betterSolution[i];
     1171    }
     1172  }
     1173 
     1174  delete newSolver;
     1175  return returnCode;
     1176}
     1177// update model
     1178void CbcHeuristicProximity::setModel(CbcModel * model)
     1179{
     1180    model_ = model;
     1181    // Get a copy of original matrix
     1182    assert(model_->solver());
     1183    delete [] used_;
     1184    int numberColumns = model->solver()->getNumCols();
     1185    used_ = new int[numberColumns];
     1186    memset(used_, 0, numberColumns*sizeof(int));
     1187}
     1188
    9301189// Default Constructor
    9311190CbcHeuristicNaive::CbcHeuristicNaive()
     
    9591218{
    9601219    CbcHeuristicNaive other;
    961     fprintf(fp, "0#include \"CbcHeuristicLocal.hpp\"\n");
     1220    fprintf(fp, "0#include \"CbcHeuristicProximity.hpp\"\n");
    9621221    fprintf(fp, "3  CbcHeuristicNaive naive(*cbcModel);\n");
    9631222    CbcHeuristic::generateCpp(fp, "naive");
     
    12361495{
    12371496    CbcHeuristicCrossover other;
    1238     fprintf(fp, "0#include \"CbcHeuristicLocal.hpp\"\n");
     1497    fprintf(fp, "0#include \"CbcHeuristicProximity.hpp\"\n");
    12391498    fprintf(fp, "3  CbcHeuristicCrossover crossover(*cbcModel);\n");
    12401499    CbcHeuristic::generateCpp(fp, "crossover");
  • trunk/Cbc/src/CbcHeuristicLocal.hpp

    r1573 r1802  
    8181    // Type of search 0=normal, 1=BAB
    8282    int swap_;
     83    /// Whether a variable has been in a solution (also when)
     84    int * used_;
     85};
     86
     87/** Proximity Search class
     88 */
     89class CbcHeuristicFPump;
     90class CbcHeuristicProximity : public CbcHeuristic {
     91public:
     92
     93    // Default Constructor
     94    CbcHeuristicProximity ();
     95
     96    /* Constructor with model - assumed before cuts
     97    */
     98    CbcHeuristicProximity (CbcModel & model);
     99
     100    // Copy constructor
     101    CbcHeuristicProximity ( const CbcHeuristicProximity &);
     102
     103    // Destructor
     104    ~CbcHeuristicProximity ();
     105
     106    /// Clone
     107    virtual CbcHeuristic * clone() const;
     108
     109    /// Assignment operator
     110    CbcHeuristicProximity & operator=(const CbcHeuristicProximity& 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    /// Used array so we can set
     129    inline int * used() const {
     130        return used_;
     131    }
     132
     133protected:
     134    // Data
     135    // Copy of Feasibility pump
     136    CbcHeuristicFPump * feasibilityPump_;
     137    // Number of solutions so we only do after new solution
     138    int numberSolutions_;
    83139    /// Whether a variable has been in a solution (also when)
    84140    int * used_;
  • trunk/Cbc/src/CbcModel.cpp

    r1798 r1802  
    24312431      User hook, says John.
    24322432    */
    2433     if ( intParam_[CbcMaxNumNode] < 0)
    2434         eventHappened_ = true; // stop as fast as possible
     2433    if ( intParam_[CbcMaxNumNode] < 0
     2434      ||numberSolutions_>=getMaximumSolutions())
     2435      eventHappened_ = true; // stop as fast as possible
    24352436    stoppedOnGap_ = false ;
    24362437    // See if can stop on gap
     
    39593960            secondaryStatus_ = 4;
    39603961            status_ = 1 ;
    3961         } else if (eventHappened_) {
    3962             handler_->message(CBC_EVENT, messages_) << CoinMessageEol ;
    3963             secondaryStatus_ = 5;
    3964             status_ = 5 ;
     3962        } else if (numberSolutions_ >= intParam_[CbcMaxNumSol]) {
     3963            handler_->message(CBC_MAXSOLS, messages_) << CoinMessageEol ;
     3964            secondaryStatus_ = 6;
     3965            status_ = 1 ;
    39653966        } else if (isNodeLimitReached()) {
    39663967            handler_->message(CBC_MAXNODES, messages_) << CoinMessageEol ;
     
    39723973            status_ = 1 ;
    39733974        } else {
    3974             assert(numberSolutions_ >= intParam_[CbcMaxNumSol]);
    3975             handler_->message(CBC_MAXSOLS, messages_) << CoinMessageEol ;
    3976             secondaryStatus_ = 6;
    3977             status_ = 1 ;
     3975            handler_->message(CBC_EVENT, messages_) << CoinMessageEol ;
     3976            secondaryStatus_ = 5;
     3977            status_ = 5 ;
    39783978        }
    39793979    }
     
    1312613126        // Modify based on size etc
    1312713127        adjustHeuristics();
    13128         // See if already withing allowable gap
     13128        // See if already within allowable gap
    1312913129        bool exitNow = false;
    1313013130        for (i = 0; i < numberHeuristics_; i++) {
     
    1313313133        }
    1313413134        if (!exitNow) {
     13135          /** -1 first time otherwise number of solutions last time */
     13136          int lastSolutionCount = -1;
     13137          while (lastSolutionCount) {
     13138            int thisSolutionCount=0;
    1313513139#ifdef CBC_THREAD
    1313613140            if ((threadMode_&4) != 0) {
     
    1315513159                        if (!heuristic_[i]->shouldHeurRun(0))
    1315613160                            continue;
     13161                        if (lastSolutionCount>0&&
     13162                            (heuristic_[i]->switches()&16)==0)
     13163                          continue; // no point
    1315713164                        parameters[i-iChunk].solutionValue = heuristicValue;
    1315813165                        // Don't want a strategy object
     
    1320213209                                    incrementUsed(newSolution);
    1320313210                                    // increment number of solutions so other heuristics can test
    13204                                     numberSolutions_++;
     13211                                    thisSolutionCount++;
    1320513212                                    numberHeuristicSolutions_++;
    1320613213                                    found = i + iChunk ;
     
    1322613233                    if (!heuristic_[i]->shouldHeurRun(whereFrom))
    1322713234                        continue;
    13228                     if (maximumSecondsReached())
     13235                    if (lastSolutionCount>0&&
     13236                        (heuristic_[i]->switches()&16)==0)
     13237                      continue; // no point
     13238                    if (maximumSecondsReached()) {
     13239                        thisSolutionCount=-1000000;
    1322913240                        break;
     13241                    }
    1323013242                    // see if heuristic will do anything
    1323113243                    double saveValue = heuristicValue ;
     
    1324913261                        setBestSolution(CBC_ROUNDING, heuristicValue, newSolution) ;
    1325013262                        if (bestObjective_ < currentObjective) {
     13263                            thisSolutionCount++;
    1325113264                            heuristic_[i]->incrementNumberSolutionsFound();
    1325213265                            found = i ;
    1325313266                            incrementUsed(newSolution);
    1325413267                            // increment number of solutions so other heuristics can test
    13255                             numberSolutions_++;
     13268                            //                            numberSolutions_++;
    1325613269                            numberHeuristicSolutions_++;
    1325713270#ifdef CLP_INVESTIGATE
     
    1326013273#endif
    1326113274                            whereFrom |= 8; // say solution found
    13262                             if (heuristic_[i]->exitNow(bestObjective_))
     13275                            if (heuristic_[i]->exitNow(bestObjective_)
     13276                                ||numberSolutions_>=getMaximumSolutions()) {
     13277                              thisSolutionCount=-1000000;
    1326313278                                break;
     13279                            }
    1326413280                            if (eventHandler) {
    1326513281                              if (!eventHandler->event(CbcEventHandler::heuristicSolution)) {
    1326613282                                eventHappened_ = true; // exit
     13283                                thisSolutionCount=-1000000;
    1326713284                                break;
    1326813285                              }
     
    1327513292                                stoppedOnGap_ = true ;
    1327613293                              //eventHappened_=true; // stop as fast as possible
     13294                              thisSolutionCount=-1000000;
    1327713295                              break;
    1327813296                            }
     
    1329313311                      if (!eventHandler->event(CbcEventHandler::afterHeuristic)) {
    1329413312                        eventHappened_ = true; // exit
     13313                        thisSolutionCount=-1000000;
    1329513314                        break;
    1329613315                      }
     
    1330013319            }
    1330113320#endif
     13321            if (thisSolutionCount<=0)
     13322              break;
     13323            lastSolutionCount=thisSolutionCount;
     13324          }
    1330213325        }
    1330313326        currentPassNumber_ = 0;
  • trunk/Cbc/src/CbcModel.hpp

    r1798 r1802  
    15881588    inline int numberHeuristics() const {
    15891589        return numberHeuristics_;
     1590    }
     1591    /// Set the number of heuristics
     1592    inline void setNumberHeuristics(int value) {
     1593        numberHeuristics_ = value;
    15901594    }
    15911595    /// Pointer to heuristic solver which found last solution (or NULL)
  • trunk/Cbc/src/CbcNode.cpp

    r1745 r1802  
    22922292                            }
    22932293                        } else if (columnLower[i] < columnUpper[i]) {
    2294                             if (solution[i] != saveSolution[i]) {
     2294                            if (fabs(solution[i] - saveSolution[i]) >
     2295                                integerTolerance) {
    22952296                                nFreeNon++;
    22962297                                if (fabs(solution[i] - saveSolution[i]) > mostAway) {
  • trunk/Cbc/src/CbcSolverHeuristics.cpp

    r1644 r1802  
    11601160    int useGreedy = parameters_[whichParam(CBC_PARAM_STR_GREEDY, numberParameters_, parameters_)].currentOptionAsInteger();
    11611161    int useCombine = parameters_[whichParam(CBC_PARAM_STR_COMBINE, numberParameters_, parameters_)].currentOptionAsInteger();
     1162    int useProximity = parameters_[whichParam(CBC_PARAM_STR_PROXIMITY, numberParameters_, parameters_)].currentOptionAsInteger();
    11621163    int useCrossover = parameters_[whichParam(CBC_PARAM_STR_CROSSOVER2, numberParameters_, parameters_)].currentOptionAsInteger();
    11631164    //int usePivotC = parameters_[whichParam(CBC_PARAM_STR_PIVOTANDCOMPLEMENT, numberParameters_, parameters_)].currentOptionAsInteger();
     
    15611562        anyToDo = true;
    15621563    }
     1564    if ((useProximity >= kType && useProximity <= kType + 1)||
     1565        (kType == 1 && useProximity >= 4)) {
     1566        CbcHeuristicProximity heuristic2a(*model);
     1567        heuristic2a.setHeuristicName("Proximity Search");
     1568        heuristic2a.setFractionSmall(9999999.0);
     1569        heuristic2a.setNumberNodes(30);
     1570        heuristic2a.setFeasibilityPumpOptions(-2);
     1571        if (useProximity>=4) {
     1572          const int nodes[]={10,100,300};
     1573          heuristic2a.setNumberNodes(nodes[useProximity-4]);
     1574          // more print out and stronger feasibility pump
     1575          if (useProximity==6)
     1576            heuristic2a.setFeasibilityPumpOptions(-3);
     1577        }
     1578        model->addHeuristic(&heuristic2a);
     1579        anyToDo = true;
     1580    }
    15631581    if (useCrossover >= kType && useCrossover <= kType + 1) {
    15641582        CbcHeuristicCrossover heuristic2a(*model);
Note: See TracChangeset for help on using the changeset viewer.