1 /*===========================================================================* 2 * This file is part of the Discrete Conic Optimization (DisCO) Solver. * 3 * * 4 * DisCO is distributed under the Eclipse Public License as part of the * 5 * COIN-OR repository (http://www.coin-or.org). * 6 * * 7 * Authors: * 8 * Aykut Bulut, Lehigh University * 9 * Yan Xu, Lehigh University * 10 * Ted Ralphs, Lehigh University * 11 * * 12 * Copyright (C) 2001-2018, Lehigh University, Aykut Bulut, Yan Xu, and * 13 * Ted Ralphs. * 14 * All Rights Reserved. * 15 *===========================================================================*/ 16 17 18 #ifndef DcoModel_hpp_ 19 #define DcoModel_hpp_ 20 21 #include <BcpsModel.h> 22 #include <OsiConicSolverInterface.hpp> 23 #include <OsiLorentzCone.hpp> 24 #include <BcpsBranchStrategy.h> 25 26 27 #include "DcoParams.hpp" 28 #include "DcoConstraint.hpp" 29 30 class DcoConGenerator; 31 class DcoSolution; 32 class DcoHeuristic; 33 34 class CglCutGenerator; 35 class CglConicCutGenerator; 36 37 /** 38 Represents a discrete conic optimization problem (master problem). 39 Some set of rows/columns will be relaxed in this problem to get subproblems 40 represented by the branch and bound tree nodes. 41 42 # Fields of DcoModel 43 relaxedCols_ keeps the set of relaxed columns. relaxedRows_ keeps the set 44 of relaxed rows. We relax integer columns only, their integrality 45 constraint is relaxed. When OA algorithm is used we relax rows corresponding 46 to conic constraints. 47 48 In DcoModel columns are stored in cols_ inherited from BcpsModel. We keep 49 number of integer variables at numIntegerCols_ and their indices at (int 50 * intColIndices_). intColIndices_[0] gives the index of the first integer 51 column in the cols_ array. 52 53 DcoModel objects are kept at constraints_ and variables_ inherited from 54 BcpsModel. 55 56 In Blis (MILP solver built on top of Bcps), integer variables have their own 57 class, BlisObjectInt. BlisObjectInt inherits BcpsObject class. 58 59 # Cut generation 60 61 Pointers to cut generators are stored in conGenerators_. Type of generators 62 are DcoConGenerator. DcoConGenerator is an abstract base class (ABC) for 63 constraint generators. Two different classes implements this ABC, 64 DcoLinearConGenerator and DcoConicConGenerator. DcoConGenerator has a single 65 pure virtual function, generateConstraints(conPool). This function generates 66 constraints and add them to the given pool. 67 68 DcoLinearConGenerator implements linear cuts. CglCutGenerator is given as an 69 input to constructor. 70 71 DcoConicConGenerator implements generating supports for conic 72 constraints. Constructor takes a CglConicCutGenerator as an input. 73 74 # Heuristics 75 76 # setupSelf() 77 78 In serial code this function is called after readInstance() method. 79 80 In parallel code it is called after readInstance() in the master 81 processor. In other processors it is called after the received encoded 82 object (AlpsEncoded instance) is decoded to self. This decode part covers 83 the following fields, variables_, constraints_, dcoPar_ and objSense_. 84 85 setupSelf() should genrate all fields of DcoModel from the 4 data fields 86 mentioned above (variables_, constraints_, dcoPar_ and objSense_). 87 88 This function also loads the problem defined by self to the solver. It 89 sets/creates branching strategy, cut generator and heuristics object. 90 91 */ 92 93 class DcoModel: public BcpsModel { 94 /// Subproblem solver. 95 #if defined(__OA__) 96 OsiSolverInterface * solver_; 97 #else 98 OsiConicSolverInterface * solver_; 99 #endif 100 std::string problemName_; 101 102 ///========================================================================== 103 /// Fields that will be set by ::readInstance() and sent to other processors 104 /// through network. ::setupSelf() will use these fields to set the rest. 105 ///========================================================================== 106 ///@name Variable and constraint bounds. 107 //@{ 108 // colLB_ and colUB_ used when installing subproblems in 109 // each node. Having it a class member we do not need to allocate and delete 110 // memory every time a subproblem is installed to the solver in a node. 111 /// Column lower bound, corresponds to the last subproblem installed. 112 double * colLB_; 113 /// Column upper bound, corresponds to the last subproblem installed. 114 double * colUB_; 115 /// Row lower bound. 116 double * rowLB_; 117 /// Row upper bound. 118 double * rowUB_; 119 //@} 120 121 ///@name Constraint matrix (linear part) and conic constraints. These can be 122 /// freed at the end of ::setupSelf() 123 //@{ 124 /// Constraint matrix. 125 CoinPackedMatrix * matrix_; 126 /// We keep cones in basic form for now, it is easier to send/receive 127 int * coneStart_; 128 int * coneMembers_; 129 int * coneType_; 130 //@} 131 132 ///@name Number of columns and rows 133 //@{ 134 /// Number of columns. 135 int numCols_; 136 /// Number of rows (constraints), linear + conic. 137 int numRows_; 138 /// Number of linear rows. 139 int numLinearRows_; 140 /// Number of conic rows. 141 int numConicRows_; 142 //@} 143 144 ///@name Objective function 145 //@{ 146 double objSense_; 147 double * objCoef_; 148 //@} 149 150 ///@name Column types 151 //@{ 152 /// Number of integer columns in the problem. 153 int numIntegerCols_; 154 /// Indices of integer columns. Columns are stored in cols_ inherited from 155 /// BcpsModel. Size of numIntegerCols_. 156 int * integerCols_; 157 int * isInteger_; 158 //@} 159 ///========================================================================== 160 161 ///========================================================================== 162 /// Fields that will be set by ::setupSelf(). constraints_ and variables_ 163 /// inherited from BcpsModel will also set by ::setupSelf(). 164 ///========================================================================== 165 ///@name Variable selection function. 166 //@{ 167 /// Branchs strategy. 168 BcpsBranchStrategy * branchStrategy_; 169 /// Ramp up branch strategy. 170 BcpsBranchStrategy * rampUpBranchStrategy_; 171 //@} 172 173 ///@name Dco parameters. 174 //@{ 175 /// DisCO parameter. 176 DcoParams * dcoPar_; 177 //@} 178 179 ///@name Relaxed objects data. 180 //@{ 181 /// Number of relaxed columns 182 int numRelaxedCols_; 183 /// Array of indices to relaxed columns. 184 int * relaxedCols_; 185 /// Number of relaxed rows 186 int numRelaxedRows_; 187 /// Array of indices to relaxed rows. 188 int * relaxedRows_; 189 //@} 190 191 ///@name Heuristics 192 //@{ 193 DcoHeurStrategy heurStrategy_; 194 int heurFrequency_; 195 std::vector<DcoHeuristic*> heuristics_; 196 //@} 197 198 ///@name Cut generator related. 199 //@{ 200 /// global cut strategy, it will be set with respect to specific cut 201 /// strategies. It will be set to the most allowing one, ie. if we have 202 /// strategies with root and periodic calls, it will be set to periodic. 203 DcoCutStrategy cutStrategy_; 204 /// Cut generation frequency, it will be set with respect to specific cut 205 /// strategies. It will be set to the most frequent one, ie. if we have 206 /// strategies with frequencies 10 and 20, it will be set to 10. 207 int cutGenerationFrequency_; 208 /// Constraint generators. 209 //std::vector<DcoConGenerator*> conGenerators_; 210 std::map<DcoConstraintType, DcoConGenerator*> conGenerators_; 211 /// Current number of approximation cuts in solver added by 212 /// #approximateCones(). 213 int initOAcuts_; 214 //@} 215 216 /// Number of relaxation iterations. 217 long long int numRelaxIterations_; 218 ///========================================================================== 219 220 221 // Private Functions 222 ///@name Read Helpers 223 //@{ 224 /// Add variables to the model. Helps readInstance function. 225 void setupAddVariables(); 226 /// Add linear constraints to the model. Helps readInstance function. 227 void setupAddLinearConstraints(); 228 /// Add conic constraints to the model. Helps readInstance function. 229 void setupAddConicConstraints(); 230 //@} 231 232 ///@name Setup Helpers 233 //@{ 234 /// Set log levels, Alps, Bcps and Disco 235 void setMessageLevel(); 236 /// Set branching strategy from parameters. 237 void setBranchingStrategy(); 238 /// Add constraint generators with respect to parameters. 239 void addConstraintGenerators(); 240 /// Add heuristics 241 void addHeuristics(); 242 //@} 243 244 /// write parameters to oustream 245 void writeParameters(std::ostream& outstream) const; 246 247 public: 248 ///@name Message printing 249 //@{ 250 /// DisCO message handler. 251 CoinMessageHandler * dcoMessageHandler_; 252 /// DisCO messages. 253 CoinMessages * dcoMessages_; 254 //@} 255 256 ///@name Constructors and Destructors 257 //@{ 258 /// Default constructor. 259 DcoModel(); 260 /// Destructor. 261 virtual ~DcoModel(); 262 //@} 263 264 ///@name Solver related 265 //@{ 266 /// Set solver 267 #if defined(__OA__) 268 void setSolver(OsiSolverInterface * solver); 269 #else 270 void setSolver(OsiConicSolverInterface * solver); 271 #endif 272 /// Get solver 273 #if defined(__OA__) solver()274 OsiSolverInterface * solver() {return solver_;} 275 #else solver()276 OsiConicSolverInterface * solver() {return solver_;} 277 #endif 278 //@} 279 280 ///@name Other functions 281 //@{ 282 /// Approximate cones. 283 void approximateCones(); 284 /// Return the current number of approximation cuts in solver that are added 285 /// by #approximateCones() initOAcuts() const286 int initOAcuts() const { return initOAcuts_; } 287 /// Decrease #initOAcuts_ by input. decreaseInitOAcuts(int num)288 void decreaseInitOAcuts( int num) { initOAcuts_ -= num; } 289 290 /// return to branch strategy. branchStrategy()291 BcpsBranchStrategy * branchStrategy() {return branchStrategy_;} 292 /// return Dco Parameter dcoPar() const293 DcoParams const * dcoPar() const {return dcoPar_;} 294 /// get upper bound of the objective value for minimization 295 double bestQuality(); 296 /// Accumulate number of relaxation iterations addNumRelaxIterations(int iter)297 void addNumRelaxIterations(int iter) {numRelaxIterations_ += iter; } 298 /// Add current solver iterations to the total 299 void addNumRelaxIterations(); 300 /// Get number of relaxation iterations numRelaxIterations() const301 long long int numRelaxIterations() const {return numRelaxIterations_;} 302 //@} 303 304 ///@name Querry problem data 305 //@{ 306 /// Get number of core variables. getNumCoreVariables() const307 int getNumCoreVariables() const {return numCols_;} 308 /// Get number of core linear constraints. getNumCoreLinearConstraints() const309 int getNumCoreLinearConstraints() const {return numLinearRows_;} 310 /// Get number of core conic constraints. getNumCoreConicConstraints() const311 int getNumCoreConicConstraints() const {return numConicRows_;} 312 /// Get column lower bounds. colLB()313 double * colLB() {return colLB_;} 314 /// Get column upper bounds. colUB()315 double * colUB() {return colUB_;} 316 /// Get row lower bounds. rowLB()317 double * rowLB() {return rowLB_;} 318 /// Get row upper bounds. rowUB()319 double * rowUB() {return rowUB_;} 320 /// Get objective sense, 1 for min, -1 for max objSense() const321 double objSense() const { return objSense_; } 322 /// Get number of integer variables. numIntegerCols() const323 int numIntegerCols() const { return numIntegerCols_; } 324 /// Get indices of integer variables. Size of numIntegerCols(). integerCols() const325 int const * integerCols() const { return integerCols_; } coneStart() const326 int const * coneStart() const { return coneStart_; } coneMembers() const327 int const * coneMembers() const { return coneMembers_; } coneType() const328 int const * coneType() const { return coneType_; } 329 //@} 330 331 ///@name Querry relaxed problem objects 332 //@{ 333 /// Get number of relaxed columns. numRelaxedCols() const334 int numRelaxedCols() const {return numRelaxedCols_;} 335 /// Get array of indices to relaxed columns. relaxedCols() const336 int const * relaxedCols() const {return relaxedCols_;} 337 /// Get number of relaxed rows numRelaxedRows() const338 int numRelaxedRows() const {return numRelaxedRows_;} 339 /// Get array of indices to relaxed rows. relaxedRows() const340 int const * relaxedRows() const {return relaxedRows_;} 341 //@} 342 343 ///@name Constraint Generation related. 344 //@{ 345 /// Add constraint generator using linear Cgl. 346 void addConGenerator(CglCutGenerator * cgl_gen, DcoConstraintType type, 347 DcoCutStrategy dco_strategy, int frequency); 348 /// Add constraint generator using conic Cgl. 349 void addConGenerator(CglConicCutGenerator * cgl_gen, DcoConstraintType type, 350 DcoCutStrategy dco_strategy, int frequency); 351 /// Add constraint generator. 352 void addConGenerator(DcoConGenerator * dco_gen); 353 /// Get the number of constraint generators. numConGenerators() const354 long unsigned int numConGenerators() const { return conGenerators_.size(); } 355 /// Get a specific constraint generator. conGenerators(DcoConstraintType type) const356 DcoConGenerator * conGenerators(DcoConstraintType type) const { return conGenerators_.at(type); } conGenerators()357 std::map<DcoConstraintType, DcoConGenerator*> conGenerators() { return conGenerators_; } 358 /// Get global cut strategy. It will be set using specific cut strategies, to 359 /// the most allowing one. If we have strategies with root and periodic 360 /// calls, it will be set to periodic. cutStrategy() const361 DcoCutStrategy cutStrategy() const {return cutStrategy_;} 362 /// Set global cut strategy. It will be set using specific cut strategies, to 363 /// the most allowing one. If we have strategies with root and periodic 364 /// calls, it will be set to periodic. setCutStrategy(DcoCutStrategy strategy)365 void setCutStrategy(DcoCutStrategy strategy) {cutStrategy_ = strategy;} 366 /// greatest common divisor of all cut generation strategies cutGenerationFrequency() const367 int cutGenerationFrequency() const { return cutGenerationFrequency_; } 368 //@} 369 370 ///@name Heuristics related 371 //@{ 372 // get number of heuristics numHeuristics() const373 long unsigned int numHeuristics() const { return heuristics_.size(); } 374 // get a constant specific heuristic, for reading statistics. heuristics(long unsigned int i) const375 DcoHeuristic const * heuristics(long unsigned int i) const { return heuristics_[i]; } 376 // get a specific heuristic, for solution search heuristics(long unsigned int i)377 DcoHeuristic * heuristics(long unsigned int i) { return heuristics_[i]; } 378 //@} 379 380 381 /// Check feasiblity of subproblem solution, store number of infeasible 382 /// columns and rows. 383 virtual DcoSolution * feasibleSolution(int & numInfColumns, double & colInf, 384 int & numInfRows, double & rowInf); 385 386 ///@name Virtual functions from AlpsModel 387 //@{ 388 /// Read in the problem instance. Currently linear Mps files and Mosek 389 /// style conic mps files. 390 virtual void readInstance(char const * dataFile); 391 void readInstanceMps(char const * dataFile); 392 void readInstanceCbf(char const * dataFile); 393 /// Reads in parameters. 394 /// This function is called from AlpsKnowledgeBrokerSerial::initializeSearch 395 /// It reads and stores the parameters in alpsPar_ inherited from AlpsModel. 396 virtual void readParameters(int const argnum, char const * const * arglist); 397 /// Do necessary work to make model ready for use, such as classify 398 /// variable and constraint types. 399 /// Called from AlpsKnowledgeBrokerSerial::initializeSearch. Called 400 /// after readParameters and preprocess. 401 virtual bool setupSelf(); 402 /// Preprocessing the model. Default does nothing. We do not have any 403 /// preprocessing for now. 404 /// Called from AlpsKnowledgeBrokerSerial::initializeSearch. Called 405 /// after readParameters and before setupSelf. 406 virtual void preprocess(); 407 /// Postprocessing the model. Default does nothing. We do not have any 408 /// postprocessing for now. 409 virtual void postprocess(); 410 /// Create the root node. 411 virtual AlpsTreeNode * createRoot(); 412 /** This function is called every time the node counts hits 413 AlpsParams::intParams::nodeLogInterval. It prints information related to 414 search status. In parallel mode only master should log. */ 415 virtual void nodeLog(AlpsTreeNode * node, bool force); 416 /// This is called at the end of the AlpsKnowledgeBroker::rootSearch 417 /// Prints solution statistics 418 virtual void modelLog(); 419 //@} 420 421 ///@name Encode and Decode functions 422 //@{ 423 424 // note(aykut): It is enough to encode the DcoModel fields that are minimal 425 // (less network communication). setupSelf() will be called by Alps to set 426 // up the rest of the fields that can be constructed/computed from the set 427 // ones. 428 429 // This grabs function "#AlpsEncoded * AlpsKnowledge::encoding() const" 430 // inherited from #AlpsKnowledge. It will not get into overload resoulution 431 // since we declare "#AlpsEncoded * encode() const" here. 432 using AlpsKnowledge::encode; 433 /// The method that encodes the this instance of model into the given 434 /// #AlpsEncoded object. 435 virtual AlpsReturnStatus encode(AlpsEncoded * encoded) const; 436 /// The method that decodes the given #AlpsEncoded object into a new #DcoModel 437 /// instance and returns a pointer to it. 438 virtual AlpsKnowledge * decode(AlpsEncoded & encoded) const; 439 /// The method that decodes this instance from the given #AlpsEncoded object. 440 virtual AlpsReturnStatus decodeToSelf(AlpsEncoded & encoded); 441 //@} 442 443 /// report feasibility of the best solution 444 void reportFeasibility(); 445 446 }; 447 448 #endif 449