1 /* $Id$ */ 2 // Copyright (C) 2003, International Business Machines 3 // Corporation and others. All Rights Reserved. 4 // This code is licensed under the terms of the Eclipse Public License (EPL). 5 6 #ifndef CbcCutGenerator_H 7 #define CbcCutGenerator_H 8 9 #include "OsiSolverInterface.hpp" 10 #include "OsiCuts.hpp" 11 #include "CglCutGenerator.hpp" 12 #include "CbcCutModifier.hpp" 13 14 class CbcModel; 15 class OsiRowCut; 16 class OsiRowCutDebugger; 17 18 //############################################################################# 19 20 /** Interface between Cbc and Cut Generation Library. 21 22 \c CbcCutGenerator is intended to provide an intelligent interface between 23 Cbc and the cutting plane algorithms in the CGL. A \c CbcCutGenerator is 24 bound to a \c CglCutGenerator and to an \c CbcModel. It contains parameters 25 which control when and how the \c generateCuts method of the 26 \c CglCutGenerator will be called. 27 28 The builtin decision criteria available to use when deciding whether to 29 generate cuts are limited: every <i>X</i> nodes, when a solution is found, 30 and when a subproblem is found to be infeasible. The idea is that the class 31 will grow more intelligent with time. 32 33 \todo Add a pointer to function member which will allow a client to install 34 their own decision algorithm to decide whether or not to call the CGL 35 \p generateCuts method. Create a default decision method that looks 36 at the builtin criteria. 37 38 \todo It strikes me as not good that generateCuts contains code specific to 39 individual CGL algorithms. Another set of pointer to function members, 40 so that the client can specify the cut generation method as well as 41 pre- and post-generation methods? Taken a bit further, should this 42 class contain a bunch of pointer to function members, one for each 43 of the places where the cut generator might be referenced? 44 Initialization, root node, search tree node, discovery of solution, 45 and termination all come to mind. Initialization and termination would 46 also be useful for instrumenting cbc. 47 */ 48 49 class CbcCutGenerator { 50 51 public: 52 /** \name Generate Cuts */ 53 //@{ 54 /** Generate cuts for the client model. 55 56 Evaluate the state of the client model and decide whether to generate cuts. 57 The generated cuts are inserted into and returned in the collection of cuts 58 \p cs. 59 60 If \p fullScan is !=0, the generator is obliged to call the CGL 61 \c generateCuts routine. Otherwise, it is free to make a local decision. 62 Negative fullScan says things like at integer solution 63 The current implementation uses \c whenCutGenerator_ to decide. 64 65 The routine returns true if reoptimisation is needed (because the state of 66 the solver interface has been modified). 67 68 If node then can find out depth 69 */ 70 bool generateCuts(OsiCuts &cs, int fullScan, OsiSolverInterface *solver, 71 CbcNode *node); 72 //@} 73 74 /**@name Constructors and destructors */ 75 //@{ 76 /// Default constructor 77 CbcCutGenerator(); 78 79 /// Normal constructor 80 CbcCutGenerator(CbcModel *model, CglCutGenerator *generator, 81 int howOften = 1, const char *name = NULL, 82 bool normal = true, bool atSolution = false, 83 bool infeasible = false, int howOftenInsub = -100, 84 int whatDepth = -1, int whatDepthInSub = -1, int switchOffIfLessThan = 0); 85 86 /// Copy constructor 87 CbcCutGenerator(const CbcCutGenerator &); 88 89 /// Assignment operator 90 CbcCutGenerator &operator=(const CbcCutGenerator &rhs); 91 92 /// Destructor 93 ~CbcCutGenerator(); 94 //@} 95 96 /**@name Gets and sets */ 97 //@{ 98 /** Set the client model. 99 100 In addition to setting the client model, refreshModel also calls 101 the \c refreshSolver method of the CglCutGenerator object. 102 */ 103 void refreshModel(CbcModel *model); 104 105 /// return name of generator cutGeneratorName() const106 inline const char *cutGeneratorName() const 107 { 108 return generatorName_; 109 } 110 111 /// Create C++ lines to show how to tune 112 void generateTuning(FILE *fp); 113 /** Set the cut generation interval 114 115 Set the number of nodes evaluated between calls to the Cgl object's 116 \p generateCuts routine. 117 118 If \p value is positive, cuts will always be generated at the specified 119 interval. 120 If \p value is negative, cuts will initially be generated at the specified 121 interval, but Cbc may adjust the value depending on the success of cuts 122 produced by this generator. 123 124 A value of -100 disables the generator, while a value of -99 means 125 just at root. 126 */ 127 void setHowOften(int value); 128 129 /// Get the cut generation interval. howOften() const130 inline int howOften() const 131 { 132 return whenCutGenerator_; 133 } 134 /// Get the cut generation interval.in sub tree howOftenInSub() const135 inline int howOftenInSub() const 136 { 137 return whenCutGeneratorInSub_; 138 } 139 /// Get level of cut inaccuracy (0 means exact e.g. cliques) inaccuracy() const140 inline int inaccuracy() const 141 { 142 return inaccuracy_; 143 } 144 /// Set level of cut inaccuracy (0 means exact e.g. cliques) setInaccuracy(int level)145 inline void setInaccuracy(int level) 146 { 147 inaccuracy_ = level; 148 } 149 150 /** Set the cut generation depth 151 152 Set the depth criterion for calls to the Cgl object's 153 \p generateCuts routine. Only active if > 0. 154 155 If whenCutGenerator is positive and this is positive then this overrides. 156 If whenCutGenerator is -1 then this is used as criterion if any cuts 157 were generated at root node. 158 If whenCutGenerator is anything else this is ignored. 159 */ 160 void setWhatDepth(int value); 161 /// Set the cut generation depth in sub tree 162 void setWhatDepthInSub(int value); 163 /// Get the cut generation depth criterion. whatDepth() const164 inline int whatDepth() const 165 { 166 return depthCutGenerator_; 167 } 168 /// Get the cut generation depth criterion.in sub tree whatDepthInSub() const169 inline int whatDepthInSub() const 170 { 171 return depthCutGeneratorInSub_; 172 } 173 /// Set maximum number of times to enter setMaximumTries(int value)174 inline void setMaximumTries(int value) 175 { 176 maximumTries_ = value; 177 } 178 /// Get maximum number of times to enter maximumTries() const179 inline int maximumTries() const 180 { 181 return maximumTries_; 182 } 183 184 /// Get switches switches() const185 inline int switches() const 186 { 187 return switches_; 188 } 189 /// Set switches (for copying from virgin state) setSwitches(int value)190 inline void setSwitches(int value) 191 { 192 switches_ = value; 193 } 194 /// Get whether the cut generator should be called in the normal place normal() const195 inline bool normal() const 196 { 197 return (switches_ & 1) != 0; 198 } 199 /// Set whether the cut generator should be called in the normal place setNormal(bool value)200 inline void setNormal(bool value) 201 { 202 switches_ &= ~1; 203 switches_ |= value ? 1 : 0; 204 } 205 /// Get whether the cut generator should be called when a solution is found atSolution() const206 inline bool atSolution() const 207 { 208 return (switches_ & 2) != 0; 209 } 210 /// Set whether the cut generator should be called when a solution is found setAtSolution(bool value)211 inline void setAtSolution(bool value) 212 { 213 switches_ &= ~2; 214 switches_ |= value ? 2 : 0; 215 } 216 /** Get whether the cut generator should be called when the subproblem is 217 found to be infeasible. 218 */ whenInfeasible() const219 inline bool whenInfeasible() const 220 { 221 return (switches_ & 4) != 0; 222 } 223 /** Set whether the cut generator should be called when the subproblem is 224 found to be infeasible. 225 */ setWhenInfeasible(bool value)226 inline void setWhenInfeasible(bool value) 227 { 228 switches_ &= ~4; 229 switches_ |= value ? 4 : 0; 230 } 231 /// Get whether the cut generator is being timed timing() const232 inline bool timing() const 233 { 234 return (switches_ & 64) != 0; 235 } 236 /// Set whether the cut generator is being timed setTiming(bool value)237 inline void setTiming(bool value) 238 { 239 switches_ &= ~64; 240 switches_ |= value ? 64 : 0; 241 timeInCutGenerator_ = 0.0; 242 } 243 /// Return time taken in cut generator timeInCutGenerator() const244 inline double timeInCutGenerator() const 245 { 246 return timeInCutGenerator_; 247 } incrementTimeInCutGenerator(double value)248 inline void incrementTimeInCutGenerator(double value) 249 { 250 timeInCutGenerator_ += value; 251 } 252 /// Get the \c CglCutGenerator corresponding to this \c CbcCutGenerator. generator() const253 inline CglCutGenerator *generator() const 254 { 255 return generator_; 256 } 257 /// Number times cut generator entered numberTimesEntered() const258 inline int numberTimesEntered() const 259 { 260 return numberTimes_; 261 } setNumberTimesEntered(int value)262 inline void setNumberTimesEntered(int value) 263 { 264 numberTimes_ = value; 265 } incrementNumberTimesEntered(int value=1)266 inline void incrementNumberTimesEntered(int value = 1) 267 { 268 numberTimes_ += value; 269 } 270 /// Total number of cuts added numberCutsInTotal() const271 inline int numberCutsInTotal() const 272 { 273 return numberCuts_; 274 } setNumberCutsInTotal(int value)275 inline void setNumberCutsInTotal(int value) 276 { 277 numberCuts_ = value; 278 } incrementNumberCutsInTotal(int value=1)279 inline void incrementNumberCutsInTotal(int value = 1) 280 { 281 numberCuts_ += value; 282 } 283 /// Total number of elements added numberElementsInTotal() const284 inline int numberElementsInTotal() const 285 { 286 return numberElements_; 287 } setNumberElementsInTotal(int value)288 inline void setNumberElementsInTotal(int value) 289 { 290 numberElements_ = value; 291 } incrementNumberElementsInTotal(int value=1)292 inline void incrementNumberElementsInTotal(int value = 1) 293 { 294 numberElements_ += value; 295 } 296 /// Total number of column cuts numberColumnCuts() const297 inline int numberColumnCuts() const 298 { 299 return numberColumnCuts_; 300 } setNumberColumnCuts(int value)301 inline void setNumberColumnCuts(int value) 302 { 303 numberColumnCuts_ = value; 304 } incrementNumberColumnCuts(int value=1)305 inline void incrementNumberColumnCuts(int value = 1) 306 { 307 numberColumnCuts_ += value; 308 } 309 /// Total number of cuts active after (at end of n cut passes at each node) numberCutsActive() const310 inline int numberCutsActive() const 311 { 312 return numberCutsActive_; 313 } setNumberCutsActive(int value)314 inline void setNumberCutsActive(int value) 315 { 316 numberCutsActive_ = value; 317 } incrementNumberCutsActive(int value=1)318 inline void incrementNumberCutsActive(int value = 1) 319 { 320 numberCutsActive_ += value; 321 } setSwitchOffIfLessThan(int value)322 inline void setSwitchOffIfLessThan(int value) 323 { 324 switchOffIfLessThan_ = value; 325 } switchOffIfLessThan() const326 inline int switchOffIfLessThan() const 327 { 328 return switchOffIfLessThan_; 329 } 330 /// Say if optimal basis needed needsOptimalBasis() const331 inline bool needsOptimalBasis() const 332 { 333 return (switches_ & 128) != 0; 334 } 335 /// Set if optimal basis needed setNeedsOptimalBasis(bool yesNo)336 inline void setNeedsOptimalBasis(bool yesNo) 337 { 338 switches_ &= ~128; 339 switches_ |= yesNo ? 128 : 0; 340 } 341 /// Whether generator MUST be called again if any cuts (i.e. ignore break from loop) mustCallAgain() const342 inline bool mustCallAgain() const 343 { 344 return (switches_ & 8) != 0; 345 } 346 /// Set whether generator MUST be called again if any cuts (i.e. ignore break from loop) setMustCallAgain(bool yesNo)347 inline void setMustCallAgain(bool yesNo) 348 { 349 switches_ &= ~8; 350 switches_ |= yesNo ? 8 : 0; 351 } 352 /// Whether generator switched off for moment switchedOff() const353 inline bool switchedOff() const 354 { 355 return (switches_ & 16) != 0; 356 } 357 /// Set whether generator switched off for moment setSwitchedOff(bool yesNo)358 inline void setSwitchedOff(bool yesNo) 359 { 360 switches_ &= ~16; 361 switches_ |= yesNo ? 16 : 0; 362 } 363 /// Whether last round of cuts did little ineffectualCuts() const364 inline bool ineffectualCuts() const 365 { 366 return (switches_ & 512) != 0; 367 } 368 /// Set whether last round of cuts did little setIneffectualCuts(bool yesNo)369 inline void setIneffectualCuts(bool yesNo) 370 { 371 switches_ &= ~512; 372 switches_ |= yesNo ? 512 : 0; 373 } 374 /// Whether to use if any cuts generated whetherToUse() const375 inline bool whetherToUse() const 376 { 377 return (switches_ & 1024) != 0; 378 } 379 /// Set whether to use if any cuts generated setWhetherToUse(bool yesNo)380 inline void setWhetherToUse(bool yesNo) 381 { 382 switches_ &= ~1024; 383 switches_ |= yesNo ? 1024 : 0; 384 } 385 /// Whether in must call again mode (or after others) whetherInMustCallAgainMode() const386 inline bool whetherInMustCallAgainMode() const 387 { 388 return (switches_ & 2048) != 0; 389 } 390 /// Set whether in must call again mode (or after others) setWhetherInMustCallAgainMode(bool yesNo)391 inline void setWhetherInMustCallAgainMode(bool yesNo) 392 { 393 switches_ &= ~2048; 394 switches_ |= yesNo ? 2048 : 0; 395 } 396 /// Whether to call at end whetherCallAtEnd() const397 inline bool whetherCallAtEnd() const 398 { 399 return (switches_ & 4096) != 0; 400 } 401 /// Set whether to call at end setWhetherCallAtEnd(bool yesNo)402 inline void setWhetherCallAtEnd(bool yesNo) 403 { 404 switches_ &= ~4096; 405 switches_ |= yesNo ? 4096 : 0; 406 } 407 /// Whether needs refresh on copy needsRefresh() const408 inline bool needsRefresh() const 409 { 410 return (switches_ & 8192) != 0; 411 } 412 /// Set whether needs refresh on copy setNeedsRefresh(bool yesNo)413 inline void setNeedsRefresh(bool yesNo) 414 { 415 switches_ &= ~8192; 416 switches_ |= yesNo ? 8192 : 0; 417 } 418 /// Number of cuts generated at root numberCutsAtRoot() const419 inline int numberCutsAtRoot() const 420 { 421 return numberCutsAtRoot_; 422 } setNumberCutsAtRoot(int value)423 inline void setNumberCutsAtRoot(int value) 424 { 425 numberCutsAtRoot_ = value; 426 } 427 /// Number of cuts active at root numberActiveCutsAtRoot() const428 inline int numberActiveCutsAtRoot() const 429 { 430 return numberActiveCutsAtRoot_; 431 } setNumberActiveCutsAtRoot(int value)432 inline void setNumberActiveCutsAtRoot(int value) 433 { 434 numberActiveCutsAtRoot_ = value; 435 } 436 /// Number of short cuts at root numberShortCutsAtRoot() const437 inline int numberShortCutsAtRoot() const 438 { 439 return numberShortCutsAtRoot_; 440 } setNumberShortCutsAtRoot(int value)441 inline void setNumberShortCutsAtRoot(int value) 442 { 443 numberShortCutsAtRoot_ = value; 444 } 445 /// Set model setModel(CbcModel * model)446 inline void setModel(CbcModel *model) 447 { 448 model_ = model; 449 } 450 /// Whether global cuts at root globalCutsAtRoot() const451 inline bool globalCutsAtRoot() const 452 { 453 return (switches_ & 32) != 0; 454 } 455 /// Set whether global cuts at root setGlobalCutsAtRoot(bool yesNo)456 inline void setGlobalCutsAtRoot(bool yesNo) 457 { 458 switches_ &= ~32; 459 switches_ |= yesNo ? 32 : 0; 460 } 461 /// Whether global cuts globalCuts() const462 inline bool globalCuts() const 463 { 464 return (switches_ & 256) != 0; 465 } 466 /// Set whether global cuts setGlobalCuts(bool yesNo)467 inline void setGlobalCuts(bool yesNo) 468 { 469 switches_ &= ~256; 470 switches_ |= yesNo ? 256 : 0; 471 } 472 /// Add in statistics from other 473 void addStatistics(const CbcCutGenerator *other); 474 /// Scale back statistics by factor 475 void scaleBackStatistics(int factor); 476 //@} 477 478 private: 479 /**@name Private gets and sets */ 480 //@{ 481 //@} 482 /// Saved cuts 483 OsiCuts savedCuts_; 484 /// Time in cut generator 485 double timeInCutGenerator_; 486 /// The client model 487 CbcModel *model_; 488 489 // The CglCutGenerator object 490 CglCutGenerator *generator_; 491 492 /// Name of generator 493 char *generatorName_; 494 495 /** Number of nodes between calls to the CglCutGenerator::generateCuts 496 routine. 497 */ 498 int whenCutGenerator_; 499 /** Number of nodes between calls to the CglCutGenerator::generateCuts 500 routine in sub tree. 501 */ 502 int whenCutGeneratorInSub_; 503 /** If first pass at root produces fewer than this cuts then switch off 504 */ 505 int switchOffIfLessThan_; 506 507 /** Depth at which to call the CglCutGenerator::generateCuts 508 routine (If >0 then overrides when and is called if depth%depthCutGenerator==0). 509 */ 510 int depthCutGenerator_; 511 512 /** Depth at which to call the CglCutGenerator::generateCuts 513 routine (If >0 then overrides when and is called if depth%depthCutGenerator==0). 514 In sub tree. 515 */ 516 int depthCutGeneratorInSub_; 517 518 /// Level of cut inaccuracy (0 means exact e.g. cliques) 519 int inaccuracy_; 520 /// Number times cut generator entered 521 int numberTimes_; 522 /// Total number of cuts added 523 int numberCuts_; 524 /// Total number of elements added 525 int numberElements_; 526 /// Total number of column cuts added 527 int numberColumnCuts_; 528 /// Total number of cuts active after (at end of n cut passes at each node) 529 int numberCutsActive_; 530 /// Number of cuts generated at root 531 int numberCutsAtRoot_; 532 /// Number of cuts active at root 533 int numberActiveCutsAtRoot_; 534 /// Number of short cuts at root 535 int numberShortCutsAtRoot_; 536 /// Switches - see gets and sets 537 int switches_; 538 /// Maximum number of times to enter 539 int maximumTries_; 540 }; 541 542 // How often to do if mostly switched off (A) 543 #define SCANCUTS 1000 544 // How often to do if mostly switched off (probing B) 545 #define SCANCUTS_PROBING 1000 546 547 #endif 548 549 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 550 */ 551