source: trunk/CbcStrategy.cpp @ 197

Last change on this file since 197 was 197, checked in by forrest, 14 years ago

stuff

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 15.4 KB
Line 
1// Copyright (C) 2005, 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 "CbcStrategy.hpp"
15#include "CbcCutGenerator.hpp"
16// Cuts
17
18#include "CglGomory.hpp"
19#include "CglProbing.hpp"
20#include "CglKnapsackCover.hpp"
21#include "CglOddHole.hpp"
22#include "CglClique.hpp"
23#include "CglFlowCover.hpp"
24#include "CglMixedIntegerRounding2.hpp"
25
26// Heuristics
27
28#include "CbcHeuristic.hpp"
29
30// Default Constructor
31CbcStrategy::CbcStrategy() 
32  :depth_(0)
33{
34}
35
36// Destructor
37CbcStrategy::~CbcStrategy ()
38{
39}
40
41// Default Constructor
42CbcStrategyDefault::CbcStrategyDefault(bool cutsOnlyAtRoot,
43                                       int numberStrong,
44                                       int numberBeforeTrust,
45                                       int printLevel)
46  :CbcStrategy(),
47   cutsOnlyAtRoot_(cutsOnlyAtRoot),
48   numberStrong_(numberStrong),
49   numberBeforeTrust_(numberBeforeTrust),
50   printLevel_(printLevel)
51{
52}
53
54
55// Destructor
56CbcStrategyDefault::~CbcStrategyDefault ()
57{
58}
59
60// Clone
61CbcStrategy *
62CbcStrategyDefault::clone() const
63{
64  return new CbcStrategyDefault(*this);
65}
66
67// Copy constructor
68CbcStrategyDefault::CbcStrategyDefault(const CbcStrategyDefault & rhs)
69:
70  CbcStrategy(rhs),
71  cutsOnlyAtRoot_(rhs.cutsOnlyAtRoot_),
72  numberStrong_(rhs.numberStrong_),
73  numberBeforeTrust_(rhs.numberBeforeTrust_),
74  printLevel_(rhs.printLevel_)
75{
76  setNested(rhs.getNested());
77}
78
79// Setup cut generators
80void 
81CbcStrategyDefault::setupCutGenerators(CbcModel & model)
82{
83  // Set up some cut generators and defaults
84  // Probing first as gets tight bounds on continuous
85
86  CglProbing generator1;
87  generator1.setUsingObjective(true);
88  generator1.setMaxPass(1);
89  // Number of unsatisfied variables to look at
90  generator1.setMaxProbe(10);
91  // How far to follow the consequences
92  generator1.setMaxLook(10);
93  // Only look at rows with fewer than this number of elements
94  generator1.setMaxElements(200);
95  //generator1.setRowCuts(3);
96
97  CglGomory generator2;
98  // try larger limit
99  generator2.setLimit(300);
100
101  CglKnapsackCover generator3;
102
103  //CglOddHole generator4;
104  //generator4.setMinimumViolation(0.005);
105  //generator4.setMinimumViolationPer(0.00002);
106  // try larger limit
107  //generator4.setMaximumEntries(200);
108
109  CglClique generator5;
110  generator5.setStarCliqueReport(false);
111  generator5.setRowCliqueReport(false);
112
113  CglMixedIntegerRounding2 mixedGen;
114  CglFlowCover flowGen;
115 
116  // Add in generators
117  int setting = cutsOnlyAtRoot_ ? -99 : -1;
118  int numberGenerators = model.numberCutGenerators();
119  int iGenerator;
120  bool found;
121  found=false;
122  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
123    CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
124    CglProbing * cgl = dynamic_cast<CglProbing *>(generator);
125    if (cgl) {
126      found=true;
127      break;
128    }
129  }
130  if (!found)
131    model.addCutGenerator(&generator1,setting,"Probing");
132  found=false;
133  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
134    CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
135    CglGomory * cgl = dynamic_cast<CglGomory *>(generator);
136    if (cgl) {
137      found=true;
138      break;
139    }
140  }
141  if (!found)
142  model.addCutGenerator(&generator2,setting,"Gomory");
143  found=false;
144  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
145    CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
146    CglKnapsackCover * cgl = dynamic_cast<CglKnapsackCover *>(generator);
147    if (cgl) {
148      found=true;
149      break;
150    }
151  }
152  if (!found)
153    model.addCutGenerator(&generator3,setting,"Knapsack");
154  //model.addCutGenerator(&generator4,setting,"OddHole");
155  found=false;
156  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
157    CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
158    CglClique * cgl = dynamic_cast<CglClique *>(generator);
159    if (cgl) {
160      found=true;
161      break;
162    }
163  }
164  if (!found)
165    model.addCutGenerator(&generator5,setting,"Clique");
166  found=false;
167  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
168    CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
169    CglFlowCover * cgl = dynamic_cast<CglFlowCover *>(generator);
170    if (cgl) {
171      found=true;
172      break;
173    }
174  }
175  if (!found)
176    model.addCutGenerator(&flowGen,setting,"FlowCover");
177  found=false;
178  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
179    CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
180    CglMixedIntegerRounding2 * cgl = dynamic_cast<CglMixedIntegerRounding2 *>(generator);
181    if (cgl) {
182      found=true;
183      break;
184    }
185  }
186  if (!found)
187    model.addCutGenerator(&mixedGen,setting,"MixedIntegerRounding2");
188  // Say we want timings
189  int newNumberGenerators = model.numberCutGenerators();
190  for (iGenerator=numberGenerators;iGenerator<newNumberGenerators;iGenerator++) {
191    CbcCutGenerator * generator = model.cutGenerator(iGenerator);
192    generator->setTiming(true);
193  }
194  if (model.getNumCols()<500)
195    model.setMaximumCutPassesAtRoot(-100); // always do 100 if possible
196  else if (model.getNumCols()<5000)
197    model.setMaximumCutPassesAtRoot(100); // use minimum drop
198  else
199    model.setMaximumCutPassesAtRoot(20);
200}
201// Setup heuristics
202void 
203CbcStrategyDefault::setupHeuristics(CbcModel & model)
204{
205  // Allow rounding heuristic
206
207  CbcRounding heuristic1(model);
208  int numberHeuristics = model.numberHeuristics();
209  int iHeuristic;
210  bool found;
211  found=false;
212  for (iHeuristic=0;iHeuristic<numberHeuristics;iHeuristic++) {
213    CbcHeuristic * heuristic = model.heuristic(iHeuristic);
214    CbcRounding * cgl = dynamic_cast<CbcRounding *>(heuristic);
215    if (cgl) {
216      found=true;
217      break;
218    }
219  }
220  if (!found)
221    model.addHeuristic(&heuristic1);
222}
223// Do printing stuff
224void 
225CbcStrategyDefault::setupPrinting(CbcModel & model,int modelLogLevel)
226{
227  if (!modelLogLevel) {
228    model.solver()->setHintParam(OsiDoReducePrint,true,OsiHintTry);
229    model.messageHandler()->setLogLevel(0);
230    model.solver()->messageHandler()->setLogLevel(0);
231  } else if (modelLogLevel==1) {
232    model.solver()->setHintParam(OsiDoReducePrint,true,OsiHintTry);
233    model.messageHandler()->setLogLevel(1);
234    model.solver()->messageHandler()->setLogLevel(0);
235  } else {
236    model.messageHandler()->setLogLevel(2);
237    model.solver()->messageHandler()->setLogLevel(1);
238    model.setPrintFrequency(50);
239  }
240}
241// Other stuff e.g. strong branching
242void 
243CbcStrategyDefault::setupOther(CbcModel & model)
244{
245  model.setNumberStrong(numberStrong_);
246  model.setNumberBeforeTrust(numberBeforeTrust_);
247}
248// Default Constructor
249CbcStrategyDefaultSubTree::CbcStrategyDefaultSubTree(CbcModel * parent ,
250                                                     bool cutsOnlyAtRoot,
251                                       int numberStrong,
252                                       int numberBeforeTrust,
253                                       int printLevel)
254  :CbcStrategy(),
255   parentModel_(parent),
256   cutsOnlyAtRoot_(cutsOnlyAtRoot),
257   numberStrong_(numberStrong),
258   numberBeforeTrust_(numberBeforeTrust),
259   printLevel_(printLevel)
260{
261}
262
263
264// Destructor
265CbcStrategyDefaultSubTree::~CbcStrategyDefaultSubTree ()
266{
267}
268
269// Clone
270CbcStrategy *
271CbcStrategyDefaultSubTree::clone() const
272{
273  return new CbcStrategyDefaultSubTree(*this);
274}
275
276// Copy constructor
277CbcStrategyDefaultSubTree::CbcStrategyDefaultSubTree(const CbcStrategyDefaultSubTree & rhs)
278:
279  CbcStrategy(rhs),
280  parentModel_(rhs.parentModel_),
281  cutsOnlyAtRoot_(rhs.cutsOnlyAtRoot_),
282  numberStrong_(rhs.numberStrong_),
283  numberBeforeTrust_(rhs.numberBeforeTrust_),
284  printLevel_(rhs.printLevel_)
285{
286  setNested(rhs.getNested());
287}
288
289// Setup cut generators
290void 
291CbcStrategyDefaultSubTree::setupCutGenerators(CbcModel & model)
292{
293  // Set up some cut generators and defaults
294  // Probing first as gets tight bounds on continuous
295
296  CglProbing generator1;
297  generator1.setUsingObjective(true);
298  generator1.setMaxPass(1);
299  // Number of unsatisfied variables to look at
300  generator1.setMaxProbe(10);
301  // How far to follow the consequences
302  generator1.setMaxLook(10);
303  // Only look at rows with fewer than this number of elements
304  generator1.setMaxElements(200);
305  //generator1.setRowCuts(3);
306
307  CglGomory generator2;
308  // try larger limit
309  generator2.setLimit(300);
310
311  CglKnapsackCover generator3;
312
313  //CglOddHole generator4;
314  //generator4.setMinimumViolation(0.005);
315  //generator4.setMinimumViolationPer(0.00002);
316  // try larger limit
317  //generator4.setMaximumEntries(200);
318
319  CglClique generator5;
320  generator5.setStarCliqueReport(false);
321  generator5.setRowCliqueReport(false);
322
323  CglMixedIntegerRounding2 mixedGen;
324  CglFlowCover flowGen;
325 
326  // Add in generators
327  int setting = cutsOnlyAtRoot_ ? -99 : -1;
328  int numberGenerators = model.numberCutGenerators();
329  int numberParentGenerators = parentModel_->numberCutGenerators();
330  int iGenerator;
331  bool found;
332  found=false;
333  int howOften=0;
334  for (iGenerator=0;iGenerator<numberParentGenerators;iGenerator++) {
335    CglCutGenerator * generator = parentModel_->cutGenerator(iGenerator)->generator();
336    CglProbing * cgl = dynamic_cast<CglProbing *>(generator);
337    if (cgl) {
338      found=true;
339      howOften = parentModel_->cutGenerator(iGenerator)->howOften();
340      break;
341    }
342  }
343  if (found&&howOften>=0) {
344    found=false;
345    for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
346      CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
347      CglProbing * cgl = dynamic_cast<CglProbing *>(generator);
348      if (cgl) {
349        found=true;
350        break;
351      }
352    }
353    if (!found)
354      model.addCutGenerator(&generator1,setting,"Probing");
355  }
356  found=false;
357  for (iGenerator=0;iGenerator<numberParentGenerators;iGenerator++) {
358    CglCutGenerator * generator = parentModel_->cutGenerator(iGenerator)->generator();
359    CglGomory * cgl = dynamic_cast<CglGomory *>(generator);
360    if (cgl) {
361      found=true;
362      howOften = parentModel_->cutGenerator(iGenerator)->howOften();
363      break;
364    }
365  }
366  if (found&&howOften>=0) {
367    found=false;
368    for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
369      CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
370      CglGomory * cgl = dynamic_cast<CglGomory *>(generator);
371      if (cgl) {
372        found=true;
373        break;
374      }
375    }
376    if (!found)
377      model.addCutGenerator(&generator2,setting,"Gomory");
378  }
379  found=false;
380  for (iGenerator=0;iGenerator<numberParentGenerators;iGenerator++) {
381    CglCutGenerator * generator = parentModel_->cutGenerator(iGenerator)->generator();
382    CglKnapsackCover * cgl = dynamic_cast<CglKnapsackCover *>(generator);
383    if (cgl) {
384      found=true;
385      howOften = parentModel_->cutGenerator(iGenerator)->howOften();
386      break;
387    }
388  }
389  if (found&&howOften>=0) {
390    found=false;
391    for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
392      CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
393      CglKnapsackCover * cgl = dynamic_cast<CglKnapsackCover *>(generator);
394      if (cgl) {
395        found=true;
396        break;
397      }
398    }
399    if (!found)
400      model.addCutGenerator(&generator3,setting,"Knapsack");
401  }
402  found=false;
403  for (iGenerator=0;iGenerator<numberParentGenerators;iGenerator++) {
404    CglCutGenerator * generator = parentModel_->cutGenerator(iGenerator)->generator();
405    CglClique * cgl = dynamic_cast<CglClique *>(generator);
406    if (cgl) {
407      found=true;
408      howOften = parentModel_->cutGenerator(iGenerator)->howOften();
409      break;
410    }
411  }
412  if (found&&howOften>=0) {
413    found=false;
414    for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
415      CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
416      CglClique * cgl = dynamic_cast<CglClique *>(generator);
417      if (cgl) {
418        found=true;
419        break;
420      }
421    }
422    if (!found)
423      model.addCutGenerator(&generator5,setting,"Clique");
424  }
425  found=false;
426  for (iGenerator=0;iGenerator<numberParentGenerators;iGenerator++) {
427    CglCutGenerator * generator = parentModel_->cutGenerator(iGenerator)->generator();
428    CglFlowCover * cgl = dynamic_cast<CglFlowCover *>(generator);
429    if (cgl) {
430      found=true;
431      howOften = parentModel_->cutGenerator(iGenerator)->howOften();
432      break;
433    }
434  }
435  if (found&&howOften>=0) {
436    found=false;
437    for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
438      CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
439      CglFlowCover * cgl = dynamic_cast<CglFlowCover *>(generator);
440      if (cgl) {
441        found=true;
442        break;
443      }
444    }
445    if (!found)
446      model.addCutGenerator(&flowGen,setting,"FlowCover");
447    found=false;
448  }
449  for (iGenerator=0;iGenerator<numberParentGenerators;iGenerator++) {
450    CglCutGenerator * generator = parentModel_->cutGenerator(iGenerator)->generator();
451    CglMixedIntegerRounding2 * cgl = dynamic_cast<CglMixedIntegerRounding2 *>(generator);
452    if (cgl) {
453      found=true;
454      howOften = parentModel_->cutGenerator(iGenerator)->howOften();
455      break;
456    }
457  }
458  if (found&&howOften>=0) {
459    found=false;
460    for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
461      CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
462      CglMixedIntegerRounding2 * cgl = dynamic_cast<CglMixedIntegerRounding2 *>(generator);
463      if (cgl) {
464        found=true;
465        break;
466      }
467    }
468    if (!found)
469      model.addCutGenerator(&mixedGen,setting,"MixedIntegerRounding2");
470  }
471#if 0
472  // Say we want timings
473  int newNumberGenerators = model.numberCutGenerators();
474  for (iGenerator=numberGenerators;iGenerator<newNumberGenerators;iGenerator++) {
475    CbcCutGenerator * generator = model.cutGenerator(iGenerator);
476    generator->setTiming(true);
477  }
478#endif
479  if (model.getNumCols()<500)
480    model.setMaximumCutPassesAtRoot(-100); // always do 100 if possible
481  else if (model.getNumCols()<5000)
482    model.setMaximumCutPassesAtRoot(100); // use minimum drop
483  else
484    model.setMaximumCutPassesAtRoot(20);
485}
486// Setup heuristics
487void 
488CbcStrategyDefaultSubTree::setupHeuristics(CbcModel & model)
489{
490  // Allow rounding heuristic
491
492  CbcRounding heuristic1(model);
493  int numberHeuristics = model.numberHeuristics();
494  int iHeuristic;
495  bool found;
496  found=false;
497  for (iHeuristic=0;iHeuristic<numberHeuristics;iHeuristic++) {
498    CbcHeuristic * heuristic = model.heuristic(iHeuristic);
499    CbcRounding * cgl = dynamic_cast<CbcRounding *>(heuristic);
500    if (cgl) {
501      found=true;
502      break;
503    }
504  }
505  if (!found)
506    model.addHeuristic(&heuristic1);
507}
508// Do printing stuff
509void 
510CbcStrategyDefaultSubTree::setupPrinting(CbcModel & model,int modelLogLevel)
511{
512  if (!modelLogLevel) {
513    model.solver()->setHintParam(OsiDoReducePrint,true,OsiHintTry);
514    model.messageHandler()->setLogLevel(0);
515    model.solver()->messageHandler()->setLogLevel(0);
516  } else if (modelLogLevel==1) {
517    model.solver()->setHintParam(OsiDoReducePrint,true,OsiHintTry);
518    model.messageHandler()->setLogLevel(1);
519    model.solver()->messageHandler()->setLogLevel(0);
520  } else {
521    model.messageHandler()->setLogLevel(2);
522    model.solver()->messageHandler()->setLogLevel(1);
523    model.setPrintFrequency(50);
524  }
525}
526// Other stuff e.g. strong branching
527void 
528CbcStrategyDefaultSubTree::setupOther(CbcModel & model)
529{
530  model.setNumberStrong(numberStrong_);
531  model.setNumberBeforeTrust(numberBeforeTrust_);
532}
533
534
535 
Note: See TracBrowser for help on using the repository browser.