1 // Copyright (C) 2005, International Business Machines 2 // Corporation and others. All Rights Reserved. 3 // This code is licensed under the terms of the Eclipse Public License (EPL). 4 5 #ifndef CglPreProcess_H 6 #define CglPreProcess_H 7 8 #include <string> 9 #include <vector> 10 11 #include "CoinMessageHandler.hpp" 12 #include "OsiSolverInterface.hpp" 13 #include "CglStored.hpp" 14 #include "OsiPresolve.hpp" 15 #include "CglCutGenerator.hpp" 16 17 //############################################################################# 18 19 /** Class for preProcessing and postProcessing. 20 21 While cuts can be added at any time in the tree, some cuts are actually just 22 stronger versions of existing constraints. In this case they can replace those 23 constraints rather than being added as new constraints. This is awkward in the 24 tree but reasonable at the root node. 25 26 This is a general process class which uses other cut generators to strengthen 27 constraints, establish that constraints are redundant, fix variables and 28 find relationships such as x + y == 1. 29 30 Presolve will also be done. 31 32 If row names existed they may be replaced by R0000000..., unless 33 setKeepColumnNames(true) is set. 34 35 */ 36 37 class CglPreProcess { 38 39 public: 40 ///@name Main methods 41 //@{ 42 /** preProcess problem - returning new problem. 43 If makeEquality true then <= cliques converted to ==. 44 Presolve will be done numberPasses times. 45 46 Returns NULL if infeasible 47 48 This version uses default strategy. For more control copy and edit 49 code from this function i.e. call preProcessNonDefault 50 */ 51 OsiSolverInterface *preProcess(OsiSolverInterface &model, 52 bool makeEquality = false, int numberPasses = 5); 53 /** preProcess problem - returning new problem. 54 If makeEquality true then <= cliques converted to ==. 55 Presolve will be done numberPasses times. 56 57 Returns NULL if infeasible 58 59 This version assumes user has added cut generators to CglPreProcess object 60 before calling it. As an example use coding in preProcess 61 If makeEquality is 1 add slacks to get cliques, 62 if 2 add slacks to get sos (but only if looks plausible) and keep sos info 63 */ 64 OsiSolverInterface *preProcessNonDefault(OsiSolverInterface &model, 65 int makeEquality = 0, int numberPasses = 5, 66 int tuning = 0); 67 /** Creates solution in original model 68 deleteStuff 0 - don't, 1 do (but not if infeasible), 2 always */ 69 void postProcess(OsiSolverInterface &model, int deleteStuff = 2); 70 /** Tightens primal bounds to make dual and branch and cutfaster. Unless 71 fixed or integral, bounds are slightly looser than they could be. 72 Returns non-zero if problem infeasible 73 Fudge for branch and bound - put bounds on columns of factor * 74 largest value (at continuous) - should improve stability 75 in branch and bound on infeasible branches (0.0 is off) 76 */ 77 int tightenPrimalBounds(OsiSolverInterface &model, double factor = 0.0); 78 /** Fix some of problem - returning new problem. 79 Uses reduced costs. 80 Optional signed character array 81 1 always keep, -1 always discard, 0 use djs 82 83 */ 84 OsiSolverInterface *someFixed(OsiSolverInterface &model, 85 double fractionToKeep = 0.25, 86 bool fixContinuousAsWell = false, 87 char *keep = NULL) const; 88 /** Replace cliques by more maximal cliques 89 Returns NULL if rows not reduced by greater than cliquesNeeded*rows 90 91 */ 92 OsiSolverInterface *cliqueIt(OsiSolverInterface &model, 93 double cliquesNeeded = 0.0) const; 94 /// If we have a cutoff - fix variables 95 int reducedCostFix(OsiSolverInterface &model); 96 //@} 97 98 //--------------------------------------------------------------------------- 99 100 /**@name Parameter set/get methods 101 102 The set methods return true if the parameter was set to the given value, 103 false if the value of the parameter is out of range. 104 105 The get methods return the value of the parameter. 106 107 */ 108 //@{ 109 /** Set cutoff bound on the objective function. 110 111 When using strict comparison, the bound is adjusted by a tolerance to 112 avoid accidentally cutting off the optimal solution. 113 */ 114 void setCutoff(double value); 115 116 /// Get the cutoff bound on the objective function - always as minimize 117 double getCutoff() const; 118 /// The original solver associated with this model. originalModel() const119 inline OsiSolverInterface *originalModel() const 120 { 121 return originalModel_; 122 } 123 /// Set original model (probably acopy) setOriginalModel(OsiSolverInterface * originalModel)124 inline void setOriginalModel(OsiSolverInterface *originalModel) 125 { 126 originalModel_ = originalModel; 127 } 128 /// Solver after making clique equalities (may == original) startModel() const129 inline OsiSolverInterface *startModel() const 130 { 131 return startModel_; 132 } 133 /// Number of solvers numberSolvers() const134 inline int numberSolvers() const 135 { 136 return numberSolvers_; 137 } 138 /// Copies of solver at various stages after presolve modelAtPass(int iPass) const139 inline OsiSolverInterface *modelAtPass(int iPass) const 140 { 141 if (iPass >= 0 && iPass < numberSolvers_) 142 return model_[iPass]; 143 else 144 return NULL; 145 } 146 /// Copies of solver at various stages after presolve after modifications modifiedModel(int iPass) const147 inline OsiSolverInterface *modifiedModel(int iPass) const 148 { 149 if (iPass >= 0 && iPass < numberSolvers_) 150 return modifiedModel_[iPass]; 151 else 152 return NULL; 153 } 154 /// Matching presolve information presolve(int iPass) const155 inline OsiPresolve *presolve(int iPass) const 156 { 157 if (iPass >= 0 && iPass < numberSolvers_) 158 return presolve_[iPass]; 159 else 160 return NULL; 161 } 162 /// Set matching presolve information setPresolve(int iPass,OsiPresolve * presolve)163 inline void setPresolve(int iPass, OsiPresolve *presolve) 164 { 165 if (iPass >= 0 && iPass < numberSolvers_) 166 presolve_[iPass] = presolve; 167 } 168 /** Return a pointer to the original columns (with possible clique slacks) 169 MUST be called before postProcess otherwise you just get 0,1,2.. */ 170 const int *originalColumns(); 171 /** Return a pointer to the original rows 172 MUST be called before postProcess otherwise you just get 0,1,2.. */ 173 const int *originalRows(); 174 /// Number of SOS if found numberSOS() const175 inline int numberSOS() const 176 { 177 return numberSOS_; 178 } 179 /// Type of each SOS typeSOS() const180 inline const int *typeSOS() const 181 { 182 return typeSOS_; 183 } 184 /// Start of each SOS startSOS() const185 inline const int *startSOS() const 186 { 187 return startSOS_; 188 } 189 /// Columns in SOS whichSOS() const190 inline const int *whichSOS() const 191 { 192 return whichSOS_; 193 } 194 /// Weights for each SOS column weightSOS() const195 inline const double *weightSOS() const 196 { 197 return weightSOS_; 198 } 199 /// Pass in prohibited columns 200 void passInProhibited(const char *prohibited, int numberColumns); 201 /// Updated prohibited columns prohibited()202 inline const char *prohibited() 203 { 204 return prohibited_; 205 } 206 /// Number of iterations PreProcessing numberIterationsPre() const207 inline int numberIterationsPre() const 208 { 209 return numberIterationsPre_; 210 } 211 /// Number of iterations PostProcessing numberIterationsPost() const212 inline int numberIterationsPost() const 213 { 214 return numberIterationsPost_; 215 } 216 /** Pass in row types 217 0 normal 218 1 cut rows - will be dropped if remain in 219 At end of preprocess cut rows will be dropped 220 and put into cuts 221 */ 222 void passInRowTypes(const char *rowTypes, int numberRows); 223 /** Updated row types - may be NULL 224 Carried around and corresponds to existing rows 225 -1 added by preprocess e.g. x+y=1 226 0 normal 227 1 cut rows - can be dropped if wanted 228 */ rowTypes()229 inline const char *rowTypes() 230 { 231 return rowType_; 232 } 233 /// Return cuts from dropped rows cuts() const234 inline const CglStored &cuts() const 235 { 236 return cuts_; 237 } 238 /// Return pointer to cuts from dropped rows cutsPointer() const239 inline const CglStored *cutsPointer() const 240 { 241 return &cuts_; 242 } 243 /// Update prohibited and rowType 244 void update(const OsiPresolve *pinfo, const OsiSolverInterface *solver); 245 /// Get options options() const246 inline int options() const 247 { 248 return options_; 249 } 250 /// Set options setOptions(int value)251 inline void setOptions(int value) 252 { 253 options_ = value; 254 } 255 //@} 256 257 ///@name Cut generator methods 258 //@{ 259 /// Get the number of cut generators numberCutGenerators() const260 inline int numberCutGenerators() const 261 { 262 return numberCutGenerators_; 263 } 264 /// Get the list of cut generators cutGenerators() const265 inline CglCutGenerator **cutGenerators() const 266 { 267 return generator_; 268 } 269 ///Get the specified cut generator cutGenerator(int i) const270 inline CglCutGenerator *cutGenerator(int i) const 271 { 272 return generator_[i]; 273 } 274 /** Add one generator - up to user to delete generators. 275 */ 276 void addCutGenerator(CglCutGenerator *generator); 277 //@} 278 279 /**@name Setting/Accessing application data */ 280 //@{ 281 /** Set application data. 282 283 This is a pointer that the application can store into and 284 retrieve. 285 This field is available for the application to optionally 286 define and use. 287 */ 288 void setApplicationData(void *appData); 289 290 /// Get application data 291 void *getApplicationData() const; 292 //@} 293 294 //--------------------------------------------------------------------------- 295 296 /**@name Message handling */ 297 //@{ 298 /// Pass in Message handler (not deleted at end) 299 void passInMessageHandler(CoinMessageHandler *handler); 300 /// Set language 301 void newLanguage(CoinMessages::Language language); setLanguage(CoinMessages::Language language)302 inline void setLanguage(CoinMessages::Language language) 303 { 304 newLanguage(language); 305 } 306 /// Return handler messageHandler() const307 inline CoinMessageHandler *messageHandler() const 308 { 309 return handler_; 310 } 311 /// Return messages messages()312 inline CoinMessages messages() 313 { 314 return messages_; 315 } 316 /// Return pointer to messages messagesPointer()317 inline CoinMessages *messagesPointer() 318 { 319 return &messages_; 320 } 321 //@} 322 //--------------------------------------------------------------------------- 323 324 ///@name Constructors and destructors etc 325 //@{ 326 /// Constructor 327 CglPreProcess(); 328 329 /// Copy constructor . 330 CglPreProcess(const CglPreProcess &rhs); 331 332 /// Assignment operator 333 CglPreProcess &operator=(const CglPreProcess &rhs); 334 335 /// Destructor 336 ~CglPreProcess(); 337 338 /// Clears out as much as possible 339 void gutsOfDestructor(); 340 341 /// Set time limit 342 void setTimeLimit(const double timeLimit, const bool useElapsedTime); 343 344 /// Keeps original column names 345 void setKeepColumnNames(const bool keep); 346 347 //@} 348 private: 349 ///@name private methods 350 //@{ 351 /** Return model with useful modifications. 352 If constraints true then adds any x+y=1 or x-y=0 constraints 353 If NULL infeasible 354 */ 355 OsiSolverInterface *modified(OsiSolverInterface *model, 356 bool constraints, 357 int &numberChanges, 358 int iBigPass, 359 int numberPasses); 360 /// create original columns and rows 361 void createOriginalIndices(); 362 /// Make continuous variables integer 363 void makeInteger(); 364 //@} 365 366 //--------------------------------------------------------------------------- 367 368 private: 369 ///@name Private member data 370 //@{ 371 372 /// The original solver associated with this model. 373 OsiSolverInterface *originalModel_; 374 /// Solver after making clique equalities (may == original) 375 OsiSolverInterface *startModel_; 376 /// Number of solvers at various stages 377 int numberSolvers_; 378 /// Copies of solver at various stages after presolve 379 OsiSolverInterface **model_; 380 /// Copies of solver at various stages after presolve after modifications 381 OsiSolverInterface **modifiedModel_; 382 /// Matching presolve information 383 OsiPresolve **presolve_; 384 385 /// Message handler 386 CoinMessageHandler *handler_; 387 388 /** Flag to say if handler_ is the default handler. 389 390 The default handler is deleted when the model is deleted. Other 391 handlers (supplied by the client) will not be deleted. 392 */ 393 bool defaultHandler_; 394 395 /// Cgl messages 396 CoinMessages messages_; 397 398 /// Pointer to user-defined data structure 399 void *appData_; 400 /// Original column numbers 401 int *originalColumn_; 402 /// Original row numbers 403 int *originalRow_; 404 /// Number of cut generators 405 int numberCutGenerators_; 406 /// Cut generators 407 CglCutGenerator **generator_; 408 /// Number of SOS if found 409 int numberSOS_; 410 /// Type of each SOS 411 int *typeSOS_; 412 /// Start of each SOS 413 int *startSOS_; 414 /// Columns in SOS 415 int *whichSOS_; 416 /// Weights for each SOS column 417 double *weightSOS_; 418 /// Number of columns in original prohibition set 419 int numberProhibited_; 420 /// Number of iterations done in PreProcessing 421 int numberIterationsPre_; 422 /// Number of iterations done in PostProcessing 423 int numberIterationsPost_; 424 /// Columns which should not be presolved e.g. SOS 425 char *prohibited_; 426 /// Number of rows in original row types 427 int numberRowType_; 428 /** Options 429 1 - original model had integer bounds before tightening 430 2 - don't do probing 431 4 - don't do duplicate rows 432 8 - don't do cliques 433 16 - some heavy probing options 434 64 - very heavy probing 435 */ 436 int options_; 437 /** Row types (may be NULL) 438 Carried around and corresponds to existing rows 439 -1 added by preprocess e.g. x+y=1 440 0 normal 441 1 cut rows - can be dropped if wanted 442 */ 443 char *rowType_; 444 /// Cuts from dropped rows 445 CglStored cuts_; 446 447 /// use elapsed (wallclock time) or cpu time 448 bool useElapsedTime_; 449 450 /// time limit (default COIN_DBL_MAX) 451 double timeLimit_; 452 453 /// keep column names 454 bool keepColumnNames_; 455 456 /// current elapsed or cpu time 457 double getCurrentCPUTime() const; 458 459 //@} 460 }; 461 462 /// For Bron-Kerbosch 463 class CglBK { 464 465 public: 466 ///@name Main methods 467 //@{ 468 /// For recursive Bron-Kerbosch 469 void bronKerbosch(); 470 /// Creates strengthened smaller model 471 OsiSolverInterface *newSolver(const OsiSolverInterface &model); 472 //@} 473 474 //--------------------------------------------------------------------------- 475 476 /**@name Parameter set/get methods 477 478 The set methods return true if the parameter was set to the given value, 479 false if the value of the parameter is out of range. 480 481 The get methods return the value of the parameter. 482 483 */ 484 //@{ 485 //@} 486 487 //--------------------------------------------------------------------------- 488 489 ///@name Constructors and destructors etc 490 //@{ 491 /// Default constructor 492 CglBK(); 493 494 /// Useful constructor 495 CglBK(const OsiSolverInterface &model, const char *rowType, 496 int numberElements); 497 498 /// Copy constructor . 499 CglBK(const CglBK &rhs); 500 501 /// Assignment operator 502 CglBK &operator=(const CglBK &rhs); 503 504 /// Destructor 505 ~CglBK(); 506 507 //@} 508 509 //--------------------------------------------------------------------------- 510 511 private: 512 ///@name Private member data 513 //@{ 514 /// Current candidates (created at each level) 515 int *candidates_; 516 /// Array to mark stuff 517 char *mark_; 518 /// Starts for graph (numberPossible+1) 519 CoinBigIndex *start_; 520 /// Other column/node 521 int *otherColumn_; 522 /// Original row (in parallel with otherColumn_) 523 int *originalRow_; 524 /// How many times each original row dominated 525 int *dominated_; 526 /// Clique entries 527 CoinPackedMatrix *cliqueMatrix_; 528 /// points to row types 529 const char *rowType_; 530 /// Number of original columns 531 int numberColumns_; 532 /// Number of original rows 533 int numberRows_; 534 /// Number possible 535 int numberPossible_; 536 /// Current number of candidates 537 int numberCandidates_; 538 /// First not (stored backwards from numberPossible_) 539 int firstNot_; 540 /// Current number in clique 541 int numberIn_; 542 /// For acceleration 543 int left_; 544 int lastColumn_; 545 //@} 546 }; 547 /** 548 Only store unique row cuts 549 */ 550 // for hashing 551 typedef struct { 552 int index, next; 553 } CglHashLink; 554 class OsiRowCut; 555 class CglUniqueRowCuts { 556 public: 557 CglUniqueRowCuts(int initialMaxSize = 0, int hashMultiplier = 4); 558 ~CglUniqueRowCuts(); 559 CglUniqueRowCuts(const CglUniqueRowCuts &rhs); 560 CglUniqueRowCuts &operator=(const CglUniqueRowCuts &rhs); cut(int sequence) const561 inline OsiRowCut *cut(int sequence) const 562 { 563 return rowCut_[sequence]; 564 } numberCuts() const565 inline int numberCuts() const 566 { 567 return numberCuts_; 568 } sizeRowCuts() const569 inline int sizeRowCuts() const 570 { 571 return numberCuts_; 572 } rowCutPtr(int sequence)573 inline OsiRowCut *rowCutPtr(int sequence) 574 { 575 return rowCut_[sequence]; 576 } 577 void eraseRowCut(int sequence); 578 // insert cut insert(const OsiRowCut & cut)579 inline void insert(const OsiRowCut &cut) 580 { 581 insertIfNotDuplicate(cut); 582 } 583 // Return 0 if added, 1 if not 584 int insertIfNotDuplicate(const OsiRowCut &cut); 585 // Add in cuts as normal cuts (and delete) 586 void addCuts(OsiCuts &cs); 587 588 private: 589 OsiRowCut **rowCut_; 590 /// Hash table 591 CglHashLink *hash_; 592 int size_; 593 int hashMultiplier_; 594 int numberCuts_; 595 int lastHash_; 596 }; 597 #endif 598 599 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 600 */ 601