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 Dco_hpp_ 19 #define Dco_hpp_ 20 21 #include "AlpsConfig.h" 22 #include "BcpsConfig.h" 23 #include "DcoConfig.hpp" 24 25 //! \page handle HomePage 26 27 /*! \mainpage 28 29 # Bcps ideas for future 30 31 We keep relaxed cols/rows (the whole object or integrality of the object) in 32 BcpsModel in list BcpsObject ** relaxed_. This way Bcps can check the 33 feasibility of its relaxed objects through virtual functions that will be 34 impelemnted in Disco level. 35 36 Can subproblems have different relaxed objects? Yes they can. But make sure 37 all relaxed objects are in the relaxed_. If subproblems have different 38 relaxed objects we will get a more depocposition like algorithm. Moreover if 39 not all integrality is relaxed we might need a discrete solver (a DcoModel 40 instance?) to solve the problem. 41 42 Subproblems might have different solvers? A subprobllem might be an LP, SOCO, 43 MILP or even MISOCO. How will DcoTreeNode::bound know about the solver to be 44 used? 45 46 When subproblem is solved with the solver we go back and check the 47 feasibility of the objects that are relaxed in the subproblem (objects in 48 relaxed_). This is done through infeasible() virtual function defined in 49 BcpsObject. 50 After this check we have a list of objects that are infeasible. At this 51 point we need to decide what to do with them. Options are (1) generate 52 cuts (using generateConstraints()), (2) lift the subproblem (using 53 generateVariables()), (3) branch. 54 (1) We can generate cuts when infeasible objects are continuous or 55 integer. Generate a separating hyperplane that cuts the subproblem solution 56 from feasible region. 57 (2) Branching when the object is continuous. This is similar to branch 58 on variables. Branching procedure should create new subproblems where 59 infeasible object has new upper and lower bounds. 60 61 feasibility checking should be implemented in Bcps level. Itertate over 62 cols/rows and check their feasiblity. Store infeasible cols (BcpsVariable) 63 and rows (BcpsConstraint). This function checks the feasibility of the 64 solution stored in the solver at the time of the call. 65 66 BcpsModel::feasibleSolution() should be able to check cols or rows only. 67 In a typical branch and bound we need to check feasibility of cols only. 68 In DisCO we may want to check both or check cols only. 69 70 # DisCO ideas 71 72 # Style Guide 73 74 <ul> 75 76 <li> Use two space indentation. Ted might object this, but this is my 77 (aykut) favorite anyway. He will use commit hooks to get code in his 78 favorite form. 79 80 <li> Avoid too many nested code blocks and many indentation levels. Reading 81 code with too many nested blocks is not fun. 3 levels of for/if blocks as 82 follows is fine 83 84 ``` 85 void ClassName::func() { 86 for (;;) { 87 if (boolean1) { 88 for (;;) { 89 } 90 } 91 } 92 } 93 ``` 94 95 If you have 4 or more, most probably there is a better way of doing what you 96 are doing (create a new function, design change, etc.). 97 98 <li> Curly braces that mark start of code block is used after the block 99 specifier as in the example from the previous bullet. This is true for 100 functions and class definitions too. 101 102 <li> One line between function definitions. Two lines between class 103 declerations if the header file has more than one. 104 105 <li> One class decleration per header file. It is OK to add two classes in 106 the same header if (1) they are closely related and (2) the second one is 107 not a major class but just a helper for the major class (class that has the 108 same name as the hearder file). 109 110 <li> Class declared in a header file should have the same name as the 111 header file. Source file that contains definition of the class should have 112 the same name. 113 114 <li> No whitespace at line endings. Please do not insert whitespaces at 115 line endings. Such trailing white spaces should be removed. Trailing white 116 spaces are redundant characters and are not wellcomed in DisCO source 117 code. I (aykut) use following snippet in my .emacs, which removes the 118 trailing white spaces at each save. I strongly advise you to do so. 119 120 ``` 121 ;; remove trailing whitespace at each save 122 (add-hook 'before-save-hook 'delete-trailing-whitespace) 123 ``` 124 125 <li> If a function does not fit in the same line of its decleration in the 126 header file then it is not supposed to be there. Move it to .cpp file. 127 128 <li> All functions defined in .hpp are already inline since bla.bla version 129 of gcc. This makes inline keywords in the header files redundant. Do not 130 use inline for these functions, I (aykut) can not bear redundant stuff 131 floating around. 132 133 <li> Define pointers as `Type * name`. Asterisk character is neither next 134 to `Type` nor variable `name`. `*` is separate since it is neither part of 135 the `Type` nor variable `name`. This is the way recommended by Bjarne 136 Stroustrup and it makes sense. 137 138 <li> We use `const` specifiers as suggested by Bjarne Stroustrup in his 139 book. Check DisCO source code to see how const objects are declared, check 140 Bjarne Stroustrup's "The C++ Language" book to see why. 141 142 <li> Functions in public interface use 143 <a>href="https://en.wikipedia.org/wiki/Camel_case">Camel Case</a> starting 144 with a lower case. Same is true for class members. 145 146 <li> From time to time private function might use underscores. 147 148 <li> Right now we do not have a rule for local variables in 149 functions. Camel Case and underscores are used together. This might 150 change. Not sure about this now. 151 152 <li> Header files should have "hpp" as extension. Source files should have 153 "cpp" as extension. 154 155 <li> Each header file should have include safeguard macros. Include 156 safeguard have a specific format. For header file Dco.hpp include safeguard 157 is as follows. 158 159 ``` 160 #ifndef Dco_hpp_ 161 #define Dco_hpp_ 162 Stuff that is needed in header file. 163 #endif 164 ``` 165 166 <li> In source files limit rows to 79 characters. There might be a few 167 lines ignoring this for now, this should be fixed. Following might be 168 usefull in case you are using emacs (M-q wraps lines). 169 170 ``` 171 (setq-default fill-column 79) 172 ``` 173 174 <li> Adding comments for a specific part of code. To add comments for a 175 specific part of code, first put the relevant code snippet into a block and 176 write comments for the block. Comments should be in doxygen format. See 177 following example 178 179 ``` 180 start doxygen comments (forward slash, asterisk, exclamation) 181 Comments regarding the following code block. 182 end doxygen comments (asterisk, forward slash) 183 { 184 code that is being commented 185 } 186 ``` 187 188 <li> Go local as much as possible. Create variables in the namespace level 189 that is directly relevant not in the upper levels. 190 191 <li> Keep documentation up to date. 192 193 </ul> 194 195 */ 196 197 #include <vector> 198 199 /*! Possible types of a constraint. 200 */ 201 enum DcoConstraintType { 202 DcoConstraintTypeNotSet = 0, 203 // Core constraint that comes with the problem 204 DcoConstraintTypeCore , 205 // MILP cuts 206 DcoConstraintTypeClique, 207 DcoConstraintTypeFCover, 208 DcoConstraintTypeGomory, 209 DcoConstraintTypeKnap, 210 DcoConstraintTypeMIR, 211 DcoConstraintTypeOddHole, 212 DcoConstraintTypeProbe, 213 DcoConstraintTypeTwoMIR, 214 // Conic Cuts 215 DcoConstraintTypeIPM, 216 DcoConstraintTypeIPMint, 217 DcoConstraintTypeOA, 218 DcoConstraintTypeCMIR, 219 DcoConstraintTypeGD1, 220 DcoConstraintTypeEnd 221 }; 222 223 // declare variable name map. This will get defined in a source file. 224 extern std::vector<char const *> const dcoConstraintTypeName; 225 226 enum DcoLorentzConeType { 227 DcoLorentzCone = 0, 228 DcoRotatedLorentzCone 229 }; 230 231 enum DcoSubproblemStatus{ 232 DcoSubproblemStatusOptimal, 233 DcoSubproblemStatusAbandoned, 234 DcoSubproblemStatusPrimalInfeasible, 235 DcoSubproblemStatusDualInfeasible, 236 DcoSubproblemStatusPrimalObjLim, 237 DcoSubproblemStatusDualObjLim, 238 DcoSubproblemStatusIterLim, 239 DcoSubproblemStatusUnknown 240 }; 241 242 enum DcoReturnStatus { 243 DcoReturnStatusOk = 0, 244 DcoReturnStatusErrLp, 245 DcoReturnStatusInfeasible, 246 DcoReturnStatusUnbounded, 247 DcoReturnStatusOverObjLim, 248 DcoReturnStatusFeasible, 249 DcoReturnStatusBranch, 250 DcoReturnStatusUnknown 251 }; 252 253 254 enum DcoCutStrategy { 255 DcoCutStrategyNotSet = -1, 256 DcoCutStrategyNone = 0, 257 DcoCutStrategyRoot, 258 DcoCutStrategyAuto, 259 DcoCutStrategyPeriodic 260 }; 261 262 /*! 263 MILP cuts that are available when OA algorithm is chosen. 264 */ 265 enum DcoLinearCutType { 266 DcoLinearCutTypeNotSet = -1, 267 DcoLinearCutTypeClique = 0, 268 DcoLinearCutTypeFCover, 269 DcoLinearCutTypeGomory, 270 DcoLinearCutTypeKnap, 271 DcoLinearCutTypeMIR, 272 DcoLinearCutTypeOddHole, 273 DcoLinearCutTypeProbe, 274 DcoLinearCutTypeTwoMIR, 275 DcoLinearCutTypeEnd 276 }; 277 278 /*! 279 Cuts that approximates conic constraints. They are used when OA algorithm is 280 chosen. 281 */ 282 enum DcoConicCutType { 283 DcoConicCutTypeNotSet = -1, 284 DcoConicCutTypeIPM = 0, 285 DcoConicCutTypeIPMInt, 286 DcoConicCutTypeOA, 287 DcoConicCutTypeMIR, 288 DcoConicCutTypeGD1 289 }; 290 291 enum DcoConicCutStrategy { 292 DcoConicCutStrategyNotSet = -1, 293 DcoConicCutStrategyNone = 0, 294 DcoConicCutStrategyRoot, 295 DcoConicCutStrategyAuto, 296 DcoConicCutStrategyPeriodic 297 }; 298 299 enum DcoHeurStrategy { 300 DcoHeurStrategyNotSet = -1, 301 DcoHeurStrategyNone = 0, 302 DcoHeurStrategyRoot, 303 DcoHeurStrategyAuto, 304 DcoHeurStrategyPeriodic, 305 DcoHeurStrategyBeforeRoot // Before solving first relaxation 306 }; 307 308 enum DcoHeurType { 309 DcoHeurTypeNotSet = -1, 310 DcoHeurTypeRounding 311 }; 312 313 enum DcoHotStartStrategy{ 314 DcoHotStartBranchIncorrect, 315 DcoHotStartBranchCorrect 316 }; 317 318 enum DcoBranchingStrategy{ 319 DcoBranchingStrategyMaxInfeasibility, 320 DcoBranchingStrategyPseudoCost, 321 DcoBranchingStrategyReliability, 322 DcoBranchingStrategyStrong, 323 DcoBranchingStrategyBilevel 324 }; 325 326 enum DcoSolutionType { 327 DcoSolutionTypeBounding, 328 DcoSolutionTypeBranching, 329 DcoSolutionTypeDiving, 330 DcoSolutionTypeHeuristic, 331 DcoSolutionTypeStrong 332 }; 333 334 /** Branching object type. */ 335 enum DcoBranchingObjectType { 336 DcoBranchingObjectTypeNone = 0, 337 DcoBranchingObjectTypeInt, 338 DcoBranchingObjectTypeSos, 339 DcoBranchingObjectTypeBilevel 340 }; 341 342 /** Node branch direction, is it a left node or right */ 343 enum DcoNodeBranchDir { 344 DcoNodeBranchDirectionDown = 0, 345 DcoNodeBranchDirectionUp 346 }; 347 348 /** Integral type */ 349 enum DcoIntegralityType { 350 DcoIntegralityTypeCont = 0, 351 DcoIntegralityTypeInt 352 }; 353 354 #endif 355