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