Ignore:
File:
1 edited

Legend:

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

    r1675 r1839  
    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  if (!model_->bestSolution())
     1073    return 0; // odd - because in parallel mode
     1074  numberSolutions_ = model_->getSolutionCount();
     1075  lastRunDeep_ = nodeCount;
     1076  numRuns_++;
     1077  //howOftenShallow_ = numberSolutions_;
     1078 
     1079/*
     1080  Load up a new solver with the solution.
     1081
     1082  Why continuousSolver(), as opposed to solver()?
     1083*/
     1084  OsiSolverInterface * newSolver = model_->continuousSolver()->clone();
     1085  int numberColumns=newSolver->getNumCols();
     1086  double * obj = CoinCopyOfArray(newSolver->getObjCoefficients(),numberColumns);
     1087  int * indices = new int [numberColumns];
     1088  int n=0;
     1089  for (int i=0;i<numberColumns;i++) {
     1090    if (obj[i]) {
     1091      indices[n]=i;
     1092      obj[n++]=obj[i];
     1093    }
     1094  }
     1095  double cutoff=model_->getCutoff();
     1096  assert (cutoff<1.0e20);
     1097  if (model_->getCutoffIncrement()<1.0e-4)
     1098    cutoff -= 0.01;
     1099  double offset;
     1100  newSolver->getDblParam(OsiObjOffset, offset);
     1101  newSolver->setDblParam(OsiObjOffset, 0.0);
     1102  newSolver->addRow(n,indices,obj,-COIN_DBL_MAX,cutoff+offset);
     1103  delete [] indices;
     1104  memset(obj,0,numberColumns*sizeof(double));
     1105  newSolver->setDblParam(OsiDualObjectiveLimit, 1.0e20);
     1106  int numberIntegers = model_->numberIntegers();
     1107  const int * integerVariable = model_->integerVariable();
     1108  const double * solutionIn = model_->bestSolution();
     1109  for (int i = 0; i < numberIntegers; i++) {
     1110    int iColumn = integerVariable[i];
     1111    if (fabs(solutionIn[iColumn])<1.0e-5)
     1112      obj[iColumn]=1.0;
     1113    else if (fabs(solutionIn[iColumn]-1.0)<1.0e-5)
     1114      obj[iColumn]=-1.0;
     1115  }
     1116  newSolver->setObjective(obj);
     1117  delete [] obj;
     1118  //newSolver->writeMps("xxxx");
     1119  int maxSolutions = model_->getMaximumSolutions();
     1120  model_->setMaximumSolutions(1);
     1121  bool pumpAdded = false;
     1122  if (feasibilityPumpOptions_ == -3 && feasibilityPump_) {
     1123    // add back feasibility pump
     1124    pumpAdded = true;
     1125    for (int i = 0; i < model_->numberHeuristics(); i++) {
     1126      const CbcHeuristicFPump* pump =
     1127        dynamic_cast<const CbcHeuristicFPump*>(model_->heuristic(i));
     1128      if (pump) {
     1129        pumpAdded = false;
     1130        break;
     1131      }
     1132    }
     1133    if (pumpAdded)
     1134      model_->addHeuristic(feasibilityPump_);
     1135  }
     1136  int returnCode =
     1137    smallBranchAndBound(newSolver, numberNodes_, betterSolution, solutionValue,
     1138                        1.0e20, "CbcHeuristicProximity");
     1139  if (pumpAdded) {
     1140    // take off feasibility pump
     1141    int lastHeuristic = model_->numberHeuristics()-1;
     1142    model_->setNumberHeuristics(lastHeuristic);
     1143    delete model_->heuristic(lastHeuristic);
     1144  }
     1145  model_->setMaximumSolutions(maxSolutions);
     1146 /*
     1147  -2 is return due to user event, and -1 is overloaded with what look to be
     1148  two contradictory meanings.
     1149*/
     1150  if (returnCode < 0) {
     1151    returnCode = 0;
     1152  }
     1153/*
     1154  If the result is complete exploration with a solution (3) or proven
     1155  infeasibility (2), we could generate a cut (the AI folks would call it a
     1156  nogood) to prevent us from going down this route in the future.
     1157*/
     1158  if ((returnCode&2) != 0) {
     1159    // could add cut
     1160    returnCode &= ~2;
     1161  }
     1162  char proxPrint[200];
     1163  if ((returnCode&1) != 0) {
     1164    // redo objective
     1165    const double * obj = model_->continuousSolver()->getObjCoefficients();
     1166    solutionValue = - offset;
     1167    int sumIncrease=0.0;
     1168    int sumDecrease=0.0;
     1169    int numberIncrease=0;
     1170    int numberDecrease=0;
     1171    for (int i=0;i<numberColumns;i++) {
     1172      solutionValue += obj[i]*betterSolution[i];
     1173      if (model_->isInteger(i)) {
     1174        int change=static_cast<int>(floor(solutionIn[i]-betterSolution[i]+0.5));
     1175        if (change>0) {
     1176          numberIncrease++;
     1177          sumIncrease+=change;
     1178        } else if (change<0) {
     1179          numberDecrease++;
     1180          sumDecrease-=change;
     1181        }
     1182      }
     1183    }
     1184    sprintf(proxPrint,"Proximity search ran %d nodes (out of %d) - in new solution %d increased (%d), %d decreased (%d)",
     1185            numberNodesDone_,numberNodes_,
     1186            numberIncrease,sumIncrease,numberDecrease,sumDecrease);
     1187  } else {
     1188    sprintf(proxPrint,"Proximity search ran %d nodes - no new solution",
     1189            numberNodesDone_);
     1190  }
     1191  model_->messageHandler()->message(CBC_FPUMP1, model_->messages())
     1192    << proxPrint
     1193    << CoinMessageEol;
     1194 
     1195  delete newSolver;
     1196  return returnCode;
     1197}
     1198// update model
     1199void CbcHeuristicProximity::setModel(CbcModel * model)
     1200{
     1201    model_ = model;
     1202    // Get a copy of original matrix
     1203    assert(model_->solver());
     1204    delete [] used_;
     1205    int numberColumns = model->solver()->getNumCols();
     1206    used_ = new int[numberColumns];
     1207    memset(used_, 0, numberColumns*sizeof(int));
     1208}
     1209
    9301210// Default Constructor
    9311211CbcHeuristicNaive::CbcHeuristicNaive()
     
    9591239{
    9601240    CbcHeuristicNaive other;
    961     fprintf(fp, "0#include \"CbcHeuristicLocal.hpp\"\n");
     1241    fprintf(fp, "0#include \"CbcHeuristicProximity.hpp\"\n");
    9621242    fprintf(fp, "3  CbcHeuristicNaive naive(*cbcModel);\n");
    9631243    CbcHeuristic::generateCpp(fp, "naive");
     
    10621342        }
    10631343    }
    1064     // Now fix all integers as close to zero if zero or large cost
     1344    // Now fix all integers as close to zero if not zero or large cost
    10651345    int nFix = 0;
    10661346    for (i = 0; i < numberIntegers; i++) {
     
    12361516{
    12371517    CbcHeuristicCrossover other;
    1238     fprintf(fp, "0#include \"CbcHeuristicLocal.hpp\"\n");
     1518    fprintf(fp, "0#include \"CbcHeuristicProximity.hpp\"\n");
    12391519    fprintf(fp, "3  CbcHeuristicCrossover crossover(*cbcModel);\n");
    12401520    CbcHeuristic::generateCpp(fp, "crossover");
Note: See TracChangeset for help on using the changeset viewer.