source: trunk/Cbc/src/CbcHeuristicRINS.cpp @ 862

Last change on this file since 862 was 838, checked in by forrest, 12 years ago

for deterministic parallel

File size: 9.5 KB
Line 
1// Copyright (C) 2006, International Business Machines
2// Corporation and others.  All Rights Reserved.
3#if defined(_MSC_VER)
4// Turn off compiler warning about long names
5#  pragma warning(disable:4786)
6#endif
7#include <cassert>
8#include <cmath>
9#include <cfloat>
10
11#include "OsiSolverInterface.hpp"
12#include "CbcModel.hpp"
13#include "CbcMessage.hpp"
14#include "CbcHeuristicRINS.hpp"
15#include "CbcBranchActual.hpp"
16#include "CbcStrategy.hpp"
17#include "CglPreProcess.hpp"
18
19// Default Constructor
20CbcHeuristicRINS::CbcHeuristicRINS() 
21  :CbcHeuristic()
22{
23  numberSolutions_=0;
24  numberSuccesses_=0;
25  numberTries_=0;
26  howOften_=100;
27  decayFactor_ = 0.5; 
28  used_=NULL;
29}
30
31// Constructor with model - assumed before cuts
32
33CbcHeuristicRINS::CbcHeuristicRINS(CbcModel & model)
34  :CbcHeuristic(model)
35{
36  numberSolutions_=0;
37  numberSuccesses_=0;
38  numberTries_=0;
39  howOften_=100;
40  decayFactor_ = 0.5; 
41  assert(model.solver());
42  int numberColumns = model.solver()->getNumCols();
43  used_ = new char[numberColumns];
44  memset(used_,0,numberColumns);
45}
46
47// Destructor
48CbcHeuristicRINS::~CbcHeuristicRINS ()
49{
50  delete [] used_;
51}
52
53// Clone
54CbcHeuristic *
55CbcHeuristicRINS::clone() const
56{
57  return new CbcHeuristicRINS(*this);
58}
59
60// Assignment operator
61CbcHeuristicRINS & 
62CbcHeuristicRINS::operator=( const CbcHeuristicRINS& rhs)
63{
64  if (this!=&rhs) {
65    CbcHeuristic::operator=(rhs);
66    numberSolutions_ = rhs.numberSolutions_;
67    howOften_ = rhs.howOften_;
68    decayFactor_ = rhs.decayFactor_;
69    numberSuccesses_ = rhs.numberSuccesses_;
70    numberTries_ = rhs.numberTries_;
71    delete [] used_;
72    if (model_&&rhs.used_) {
73      int numberColumns = model_->solver()->getNumCols();
74      used_ = new char[numberColumns];
75      memcpy(used_,rhs.used_,numberColumns);
76    } else {
77      used_=NULL;
78    }
79  }
80  return *this;
81}
82
83// Create C++ lines to get to current state
84void 
85CbcHeuristicRINS::generateCpp( FILE * fp) 
86{
87  CbcHeuristicRINS other;
88  fprintf(fp,"0#include \"CbcHeuristicRINS.hpp\"\n");
89  fprintf(fp,"3  CbcHeuristicRINS heuristicRINS(*cbcModel);\n");
90  CbcHeuristic::generateCpp(fp,"heuristicRINS");
91  if (howOften_!=other.howOften_)
92    fprintf(fp,"3  heuristicRINS.setHowOften(%d);\n",howOften_);
93  else
94    fprintf(fp,"4  heuristicRINS.setHowOften(%d);\n",howOften_);
95  fprintf(fp,"3  cbcModel->addHeuristic(&heuristicRINS);\n");
96}
97
98// Copy constructor
99CbcHeuristicRINS::CbcHeuristicRINS(const CbcHeuristicRINS & rhs)
100:
101  CbcHeuristic(rhs),
102  numberSolutions_(rhs.numberSolutions_),
103  howOften_(rhs.howOften_),
104  decayFactor_(rhs.decayFactor_),
105  numberSuccesses_(rhs.numberSuccesses_),
106  numberTries_(rhs.numberTries_)
107{
108  if (model_&&rhs.used_) {
109    int numberColumns = model_->solver()->getNumCols();
110    used_ = new char[numberColumns];
111    memcpy(used_,rhs.used_,numberColumns);
112  } else {
113    used_=NULL;
114  }
115}
116// Resets stuff if model changes
117void 
118CbcHeuristicRINS::resetModel(CbcModel * model)
119{
120  //CbcHeuristic::resetModel(model);
121  delete [] used_;
122  if (model_&&used_) {
123    int numberColumns = model_->solver()->getNumCols();
124    used_ = new char[numberColumns];
125    memset(used_,0,numberColumns);
126  } else {
127    used_=NULL;
128  }
129}
130/*
131  First tries setting a variable to better value.  If feasible then
132  tries setting others.  If not feasible then tries swaps
133  Returns 1 if solution, 0 if not */
134int
135CbcHeuristicRINS::solution(double & solutionValue,
136                         double * betterSolution)
137{
138  int returnCode=0;
139  const double * bestSolution = model_->bestSolution();
140  if (!bestSolution)
141    return 0; // No solution found yet
142  if (numberSolutions_<model_->getSolutionCount()) {
143    // new solution - add info
144    numberSolutions_=model_->getSolutionCount();
145
146    int numberIntegers = model_->numberIntegers();
147    const int * integerVariable = model_->integerVariable();
148 
149    int i;
150    for (i=0;i<numberIntegers;i++) {
151      int iColumn = integerVariable[i];
152      const OsiObject * object = model_->object(i);
153      // get original bounds
154      double originalLower;
155      double originalUpper;
156      getIntegerInformation( object,originalLower, originalUpper); 
157      double value=bestSolution[iColumn];
158      if (value<originalLower) {
159        value=originalLower;
160      } else if (value>originalUpper) {
161        value=originalUpper;
162      }
163      double nearest=floor(value+0.5);
164      // if away from lower bound mark that fact
165      if (nearest>originalLower) {
166        used_[iColumn]=1;
167      }
168    }
169  } 
170  if ((model_->getNodeCount()%howOften_)==0&&model_->getCurrentPassNumber()==1) {
171    OsiSolverInterface * solver = model_->solver();
172
173    int numberIntegers = model_->numberIntegers();
174    const int * integerVariable = model_->integerVariable();
175 
176    const double * currentSolution = solver->getColSolution();
177    OsiSolverInterface * newSolver = model_->continuousSolver()->clone();
178    const double * colLower = newSolver->getColLower();
179    //const double * colUpper = newSolver->getColUpper();
180
181    double primalTolerance;
182    solver->getDblParam(OsiPrimalTolerance,primalTolerance);
183   
184    int i;
185    int nFix=0;
186    for (i=0;i<numberIntegers;i++) {
187      int iColumn=integerVariable[i];
188      const OsiObject * object = model_->object(i);
189      // get original bounds
190      double originalLower;
191      double originalUpper;
192      getIntegerInformation( object,originalLower, originalUpper); 
193      double valueInt=bestSolution[iColumn];
194      if (valueInt<originalLower) {
195        valueInt=originalLower;
196      } else if (valueInt>originalUpper) {
197        valueInt=originalUpper;
198      }
199      if (fabs(currentSolution[iColumn]-valueInt)<10.0*primalTolerance) {
200        double nearest=floor(valueInt+0.5);
201        newSolver->setColLower(iColumn,nearest);
202        newSolver->setColUpper(iColumn,colLower[iColumn]);
203        nFix++;
204      }
205    }
206    if (nFix>numberIntegers/5) {
207      //printf("%d integers have same value\n",nFix);
208      returnCode = smallBranchAndBound(newSolver,numberNodes_,betterSolution,solutionValue,
209                                         model_->getCutoff(),"CbcHeuristicRINS");
210      if (returnCode<0)
211        returnCode=0; // returned on size
212      if ((returnCode&1)!=0)
213        numberSuccesses_++;
214      //printf("return code %d",returnCode);
215      if ((returnCode&2)!=0) {
216        // could add cut
217        returnCode &= ~2;
218        //printf("could add cut with %d elements (if all 0-1)\n",nFix);
219      } else {
220        //printf("\n");
221      }
222      numberTries_++;
223      if ((numberTries_%10)==0&&numberSuccesses_*3<numberTries_)
224        howOften_ += howOften_*decayFactor_;
225    }
226
227    delete newSolver;
228  }
229  return returnCode;
230}
231// update model
232void CbcHeuristicRINS::setModel(CbcModel * model)
233{
234  model_ = model;
235  // Get a copy of original matrix
236  assert(model_->solver());
237  delete [] used_;
238  int numberColumns = model->solver()->getNumCols();
239  used_ = new char[numberColumns];
240  memset(used_,0,numberColumns);
241}
242// Default Constructor
243CbcHeuristicRENS::CbcHeuristicRENS() 
244  :CbcHeuristic()
245{
246  numberTries_=0;
247}
248
249// Constructor with model - assumed before cuts
250
251CbcHeuristicRENS::CbcHeuristicRENS(CbcModel & model)
252  :CbcHeuristic(model)
253{
254  numberTries_=0;
255}
256
257// Destructor
258CbcHeuristicRENS::~CbcHeuristicRENS ()
259{
260}
261
262// Clone
263CbcHeuristic *
264CbcHeuristicRENS::clone() const
265{
266  return new CbcHeuristicRENS(*this);
267}
268
269// Assignment operator
270CbcHeuristicRENS & 
271CbcHeuristicRENS::operator=( const CbcHeuristicRENS& rhs)
272{
273  if (this!=&rhs) {
274    CbcHeuristic::operator=(rhs);
275    numberTries_ = rhs.numberTries_;
276  }
277  return *this;
278}
279
280// Copy constructor
281CbcHeuristicRENS::CbcHeuristicRENS(const CbcHeuristicRENS & rhs)
282:
283  CbcHeuristic(rhs),
284  numberTries_(rhs.numberTries_)
285{
286}
287// Resets stuff if model changes
288void 
289CbcHeuristicRENS::resetModel(CbcModel * model)
290{
291}
292int
293CbcHeuristicRENS::solution(double & solutionValue,
294                         double * betterSolution)
295{
296  int returnCode=0;
297  if (numberTries_)
298    return 0; 
299  numberTries_++;
300  OsiSolverInterface * solver = model_->solver();
301 
302  int numberIntegers = model_->numberIntegers();
303  const int * integerVariable = model_->integerVariable();
304 
305  const double * currentSolution = solver->getColSolution();
306  OsiSolverInterface * newSolver = model_->continuousSolver()->clone();
307  const double * colLower = newSolver->getColLower();
308  const double * colUpper = newSolver->getColUpper();
309
310  double primalTolerance;
311  solver->getDblParam(OsiPrimalTolerance,primalTolerance);
312   
313  int i;
314  int numberFixed=0;
315  int numberTightened=0;
316
317  for (i=0;i<numberIntegers;i++) {
318    int iColumn=integerVariable[i];
319    double value = currentSolution[iColumn];
320    double lower = colLower[iColumn];
321    double upper = colUpper[iColumn];
322    value = CoinMax(value,lower);
323    value = CoinMin(value,upper);
324    if (fabs(value-floor(value+0.5))<1.0e-8) {
325      value = floor(value+0.5);
326      newSolver->setColLower(iColumn,value);
327      newSolver->setColUpper(iColumn,value);
328      numberFixed++;
329    } else if (colUpper[iColumn]-colLower[iColumn]>=2.0) {
330      numberTightened++;
331      newSolver->setColLower(iColumn,floor(value));
332      newSolver->setColUpper(iColumn,ceil(value));
333    }
334  }
335  if (numberFixed>numberIntegers/5) {
336#ifdef COIN_DEVELOP
337    printf("%d integers fixed and %d tightened\n",numberFixed,numberTightened);
338#endif
339    returnCode = smallBranchAndBound(newSolver,numberNodes_,betterSolution,solutionValue,
340                                     model_->getCutoff(),"CbcHeuristicRENS");
341    if (returnCode<0)
342      returnCode=0; // returned on size
343    //printf("return code %d",returnCode);
344    if ((returnCode&2)!=0) {
345      // could add cut
346      returnCode &= ~2;
347      //printf("could add cut with %d elements (if all 0-1)\n",nFix);
348    } else {
349      //printf("\n");
350    }
351  }
352 
353  delete newSolver;
354  return returnCode;
355}
356// update model
357void CbcHeuristicRENS::setModel(CbcModel * model)
358{
359  model_ = model;
360}
361
362 
Note: See TracBrowser for help on using the repository browser.