source: trunk/Cbc/src/CbcCutGenerator.cpp @ 310

Last change on this file since 310 was 310, checked in by andreasw, 13 years ago

first commit for autotools conversion to be able to move more files

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