source: branches/devel/Cbc/src/CbcCutGenerator.cpp @ 417

Last change on this file since 417 was 395, checked in by forrest, 13 years ago

for cut generators

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 9.8 KB
Line 
1// Copyright (C) 2003, 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 "CbcCutGenerator.hpp"
15#include "CglProbing.hpp"
16#include "CoinTime.hpp"
17
18// Default Constructor
19CbcCutGenerator::CbcCutGenerator ()
20  : model_(NULL),
21    generator_(NULL),
22    whenCutGenerator_(-1),
23    whenCutGeneratorInSub_(-100),
24    switchOffIfLessThan_(0),
25    depthCutGenerator_(-1),
26    depthCutGeneratorInSub_(-1),
27    generatorName_(NULL),
28    normal_(true),
29    atSolution_(false),
30    whenInfeasible_(false),
31    mustCallAgain_(false),
32    switchedOff_(false),
33    timing_(false),
34    timeInCutGenerator_(0.0),
35    numberTimes_(0),
36    numberCuts_(0),
37    numberColumnCuts_(0),
38    numberCutsActive_(0)
39{
40}
41// Normal constructor
42CbcCutGenerator::CbcCutGenerator(CbcModel * model,CglCutGenerator * generator,
43                                 int howOften, const char * name,
44                                 bool normal, bool atSolution, 
45                                 bool infeasible, int howOftenInSub,
46                                 int whatDepth, int whatDepthInSub,
47                                 int switchOffIfLessThan)
48  : 
49    depthCutGenerator_(whatDepth),
50    depthCutGeneratorInSub_(whatDepthInSub),
51    mustCallAgain_(false),
52    switchedOff_(false),
53    timing_(false),
54    timeInCutGenerator_(0.0),
55    numberTimes_(0),
56    numberCuts_(0),
57    numberColumnCuts_(0),
58    numberCutsActive_(0)
59{
60  model_ = model;
61  generator_=generator->clone();
62  generator_->refreshSolver(model_->solver());
63  whenCutGenerator_=howOften;
64  whenCutGeneratorInSub_ = howOftenInSub;
65  switchOffIfLessThan_=switchOffIfLessThan;
66  if (name)
67    generatorName_=strdup(name);
68  else
69    generatorName_ = strdup("Unknown");
70  normal_=normal;
71  atSolution_=atSolution;
72  whenInfeasible_=infeasible;
73}
74
75// Copy constructor
76CbcCutGenerator::CbcCutGenerator ( const CbcCutGenerator & rhs)
77{
78  model_ = rhs.model_;
79  generator_=rhs.generator_->clone();
80  generator_->refreshSolver(model_->solver());
81  whenCutGenerator_=rhs.whenCutGenerator_;
82  whenCutGeneratorInSub_ = rhs.whenCutGeneratorInSub_;
83  switchOffIfLessThan_ = rhs.switchOffIfLessThan_;
84  depthCutGenerator_=rhs.depthCutGenerator_;
85  depthCutGeneratorInSub_ = rhs.depthCutGeneratorInSub_;
86  generatorName_=strdup(rhs.generatorName_);
87  normal_=rhs.normal_;
88  atSolution_=rhs.atSolution_;
89  whenInfeasible_=rhs.whenInfeasible_;
90  mustCallAgain_ = rhs.mustCallAgain_;
91  switchedOff_ = rhs.switchedOff_;
92  timing_ = rhs.timing_;
93  timeInCutGenerator_ = rhs.timeInCutGenerator_;
94  numberTimes_ = rhs.numberTimes_;
95  numberCuts_ = rhs.numberCuts_;
96  numberColumnCuts_ = rhs.numberColumnCuts_;
97  numberCutsActive_ = rhs.numberCutsActive_;
98}
99
100// Assignment operator
101CbcCutGenerator & 
102CbcCutGenerator::operator=( const CbcCutGenerator& rhs)
103{
104  if (this!=&rhs) {
105    delete generator_;
106    free(generatorName_);
107    model_ = rhs.model_;
108    generator_=rhs.generator_->clone();
109    generator_->refreshSolver(model_->solver());
110    whenCutGenerator_=rhs.whenCutGenerator_;
111    whenCutGeneratorInSub_ = rhs.whenCutGeneratorInSub_;
112    switchOffIfLessThan_ = rhs.switchOffIfLessThan_;
113    depthCutGenerator_=rhs.depthCutGenerator_;
114    depthCutGeneratorInSub_ = rhs.depthCutGeneratorInSub_;
115    generatorName_=strdup(rhs.generatorName_);
116    normal_=rhs.normal_;
117    atSolution_=rhs.atSolution_;
118    whenInfeasible_=rhs.whenInfeasible_;
119    mustCallAgain_ = rhs.mustCallAgain_;
120    switchedOff_ = rhs.switchedOff_;
121    timing_ = rhs.timing_;
122    timeInCutGenerator_ = rhs.timeInCutGenerator_;
123    numberTimes_ = rhs.numberTimes_;
124    numberCuts_ = rhs.numberCuts_;
125    numberColumnCuts_ = rhs.numberColumnCuts_;
126    numberCutsActive_ = rhs.numberCutsActive_;
127  }
128  return *this;
129}
130
131// Destructor
132CbcCutGenerator::~CbcCutGenerator ()
133{
134  free(generatorName_);
135  delete generator_;
136}
137
138/* This is used to refresh any inforamtion.
139   It also refreshes the solver in the cut generator
140   in case generator wants to do some work
141*/
142void 
143CbcCutGenerator::refreshModel(CbcModel * model)
144{
145  model_=model;
146  generator_->refreshSolver(model_->solver());
147}
148/* Generate cuts for the model data contained in si.
149   The generated cuts are inserted into and returned in the
150   collection of cuts cs.
151*/
152bool
153CbcCutGenerator::generateCuts( OsiCuts & cs , bool fullScan, CbcNode * node)
154{
155  int howOften = whenCutGenerator_;
156  if (howOften==-100)
157    return false;
158  if (howOften>0)
159    howOften = howOften % 1000000;
160  else 
161    howOften=1;
162  if (!howOften)
163    howOften=1;
164  bool returnCode=false;
165  OsiSolverInterface * solver = model_->solver();
166  int depth;
167  if (node)
168    depth=node->depth();
169  else
170    depth=0;
171  int pass=model_->getCurrentPassNumber()-1;
172  bool doThis=(model_->getNodeCount()%howOften)==0;
173  if (depthCutGenerator_>0) {
174    doThis = (depth % depthCutGenerator_) ==0;
175    if (depth<depthCutGenerator_)
176      doThis=true; // and also at top of tree
177  }
178  // But turn off if 100
179  if (howOften==100)
180    doThis=false;
181  // Switch off if special setting
182  if (whenCutGeneratorInSub_==-200) {
183    fullScan=false;
184    doThis=false;
185  }
186  if (fullScan||doThis) {
187    double time1=0.0;
188    if (timing_)
189      time1 = CoinCpuTime();
190    int cutsBefore = cs.sizeCuts();
191    CglTreeInfo info;
192    info.level = depth;
193    info.pass = pass;
194    info.formulation_rows = model_->numberRowsAtContinuous();
195    info.inTree = node!=NULL;
196    incrementNumberTimesEntered();
197    CglProbing* generator =
198      dynamic_cast<CglProbing*>(generator_);
199    if (!generator) {
200      // Pass across model information in case it could be useful
201      //OsiSolverInterface * solver = model_->solver();
202      //void * saveData = solver->getApplicationData();
203      //solver->setApplicationData(model_);
204      generator_->generateCuts(*solver,cs,info);
205      //solver->setApplicationData(saveData);
206    } else {
207      // Probing - return tight column bounds
208      generator->generateCutsAndModify(*solver,cs,info);
209      const double * tightLower = generator->tightLower();
210      const double * lower = solver->getColLower();
211      const double * tightUpper = generator->tightUpper();
212      const double * upper = solver->getColUpper();
213      const double * solution = solver->getColSolution();
214      int j;
215      int numberColumns = solver->getNumCols();
216      double primalTolerance = 1.0e-8;
217#if 0
218      int numberChanged=0,ifCut=0;
219      CoinPackedVector lbs;
220      CoinPackedVector ubs;
221      for (j=0;j<numberColumns;j++) {
222        if (solver->isInteger(j)) {
223          if (tightUpper[j]<upper[j]) {
224            numberChanged++;
225            assert (tightUpper[j]==floor(tightUpper[j]+0.5));
226            ubs.insert(j,tightUpper[j]);
227            if (tightUpper[j]<solution[j]-primalTolerance)
228              ifCut=1;
229          }
230          if (tightLower[j]>lower[j]) {
231            numberChanged++;
232            assert (tightLower[j]==floor(tightLower[j]+0.5));
233            lbs.insert(j,tightLower[j]);
234            if (tightLower[j]>solution[j]+primalTolerance)
235              ifCut=1;
236          }
237        } else {
238          if (tightUpper[j]==tightLower[j]&&
239              upper[j]>lower[j]) {
240            // fix
241            //solver->setColLower(j,tightLower[j]);
242            //solver->setColUpper(j,tightUpper[j]);
243            double value = tightUpper[j];
244            numberChanged++;
245            if (value<upper[j])
246              ubs.insert(j,value);
247            if (value>lower[j])
248              lbs.insert(j,value);
249          }
250        }
251      }
252      if (numberChanged) {
253        OsiColCut cc;
254        cc.setUbs(ubs);
255        cc.setLbs(lbs);
256        if (ifCut) {
257          cc.setEffectiveness(100.0);
258        } else {
259          cc.setEffectiveness(1.0e-5);
260        }
261        cs.insert(cc);
262      }
263      // need to resolve if some bounds changed
264      returnCode = !solver->basisIsAvailable();
265      assert (!returnCode);
266#else
267      for (j=0;j<numberColumns;j++) {
268        if (solver->isInteger(j)) {
269          if (tightUpper[j]<upper[j]) {
270            double nearest = floor(tightUpper[j]+0.5);
271            assert (fabs(tightUpper[j]-nearest)<1.0e-7);
272            solver->setColUpper(j,nearest);
273            if (nearest<solution[j]-primalTolerance)
274              returnCode=true;
275          }
276          if (tightLower[j]>lower[j]) {
277            double nearest = floor(tightLower[j]+0.5);
278            assert (fabs(tightLower[j]-nearest)<1.0e-7);
279            solver->setColLower(j,nearest);
280            if (nearest>solution[j]+primalTolerance)
281              returnCode=true;
282          }
283        } else {
284          if (tightUpper[j]==tightLower[j]&&
285              upper[j]>lower[j]) {
286            // fix
287            solver->setColLower(j,tightLower[j]);
288            solver->setColUpper(j,tightUpper[j]);
289            if (tightLower[j]>solution[j]+primalTolerance||
290                tightUpper[j]<solution[j]-primalTolerance)
291              returnCode=true;
292          }
293        }
294      }
295      //if (!solver->basisIsAvailable())
296      //returnCode=true;
297#endif
298    }
299    if (timing_)
300      timeInCutGenerator_ += CoinCpuTime()-time1;
301    // switch off if first time and no good
302    if (node==NULL&&!pass) {
303      if (cs.sizeCuts()-cutsBefore<CoinAbs(switchOffIfLessThan_)) {
304        whenCutGenerator_=-99;
305        whenCutGeneratorInSub_ = -200;
306      }
307    }
308  }
309  return returnCode;
310}
311void 
312CbcCutGenerator::setHowOften(int howOften) 
313{
314 
315  if (howOften>=1000000) {
316    // leave Probing every 10
317    howOften = howOften % 1000000;
318    CglProbing* generator =
319      dynamic_cast<CglProbing*>(generator_);
320   
321    if (generator&&howOften>10) 
322      howOften=10+1000000;
323    else
324      howOften += 1000000;
325  }
326  whenCutGenerator_ = howOften;
327}
328void 
329CbcCutGenerator::setWhatDepth(int value) 
330{
331  depthCutGenerator_ = value;
332}
333void 
334CbcCutGenerator::setWhatDepthInSub(int value) 
335{
336  depthCutGeneratorInSub_ = value;
337}
Note: See TracBrowser for help on using the repository browser.