Dip  0.95.0
Decomp.h
Go to the documentation of this file.
1 //===========================================================================//
2 // This file is part of the DIP Solver Framework. //
3 // //
4 // DIP is distributed under the Eclipse Public License as part of the //
5 // COIN-OR repository (http://www.coin-or.org). //
6 // //
7 // Authors: Matthew Galati, SAS Institute Inc. (matthew.galati@sas.com) //
8 // Ted Ralphs, Lehigh University (ted@lehigh.edu) //
9 // Jiadong Wang, Lehigh University (jiw408@lehigh.edu) //
10 // //
11 // Copyright (C) 2002-2019, Lehigh University, Matthew Galati, Ted Ralphs //
12 // All Rights Reserved. //
13 // //
14 // Interface to Gurobi is Copyright 2015 Jazz Aviation LP //
15 //===========================================================================//
16 
17 //===========================================================================//
18 #ifndef Decomp_h_
19 #define Decomp_h_
20 
21 //===========================================================================//
22 // Standard Headers //
23 //===========================================================================//
24 //---
25 //--- include the necessary standard libs
26 //---
27 #include <cstdio>
28 #include <cassert>
29 #include <vector>
30 #include <list>
31 #include <iostream>
32 #include <fstream>
33 #include <iomanip>
34 #include <numeric>
35 #include <sstream>
36 #include <algorithm>
37 #include <functional>
38 #include <string>
39 #include <map>
40 #include <limits>
41 #include <cmath>
42 
43 #include "DecompConfig.h"
44 
45 //===========================================================================//
46 // COIN Headers //
47 //===========================================================================//
48 //---
49 //--- include some standard COIN headers (depending on LP solver)
50 //--- depending on LP solver
51 //---
52 #include "CoinError.hpp"
53 #include "CoinFinite.hpp"
54 #include "CoinPackedVector.hpp"
55 #include "CoinPackedMatrix.hpp"
56 
57 #ifdef DIP_HAS_CLP
59 #endif
60 
61 #ifdef DIP_HAS_CPX
62 #include "cplex.h"
64 #endif
65 
66 #ifdef DIP_HAS_GRB
67 extern "C" {
68 #include "gurobi_c.h"
69 }
71 #endif
72 
73 #ifdef DIP_HAS_CBC
75 #endif
76 
77 #ifdef DIP_HAS_SYMPHONY
78 #include "symphony.h"
79 #include "OsiSymSolverInterface.hpp"
80 #endif
81 
82 //===========================================================================//
83 // DECOMP Enums, Constants and Typedefs //
84 //===========================================================================//
85 
86 //===========================================================================//
87 //---
88 //--- DECOMP typedefs
89 //---
90 class DecompVar;
91 class DecompCut;
92 typedef std::list<DecompVar*> DecompVarList;
93 typedef std::list<DecompCut*> DecompCutList;
94 
95 //===========================================================================//
96 //---
97 //--- DECOMP constants
98 //---
99 const double DecompBigNum = 1.0e21;
100 const double DecompEpsilon = 1.0e-6;
101 const double DecompZero = 1.0e-14;
102 
103 //===========================================================================//
104 //---
105 //--- DECOMP enums (for algorithms)
106 //---
107 
108 
110  bool doCut;
112  bool doDirect;
113  double timeSetupCpu ;
115  double timeSolveCpu ;
116  double timeSolveReal ;
117  double bestLB;
118  double bestUB;
119 };
120 
121 
122 
129 };
130 const std::string DecompAlgoStr[5] = {
131  "CUT",
132  "PRICE_AND_CUT",
133  "RELAX_AND_CUT",
134  "VOL_AND_CUT",
135  "DECOMP"
136 };
137 
138 //---
139 //--- node stopping criteria
140 //---
149 };
150 const std::string DecompAlgoStopStr[7] = {
151  "DecompStopNo",
152  "DecompStopGap",
153  "DecompStopTailOff",
154  "DecompStopInfeasible",
155  "DecompStopBound",
156  "DecompStopTime",
157  "DecompStopIterLimit"
158 };
159 
160 
161 //===========================================================================//
162 //---
163 //--- DECOMP enums (for phases)
164 //---
171 };
172 const std::string DecompPhaseStr[6] = {
173  "PHASE_PRICE1",
174  "PHASE_PRICE2",
175  "PHASE_CUT",
176  "PHASE_DONE",
177  "PHASE_UNKNOWN"
178 };
179 
180 //===========================================================================//
181 //---
182 //--- DECOMP enums (for status)
183 //---
189 };
190 const std::string DecompStatusStr[3] = {
191  "STAT_FEASIBLE",
192  "STAT_INFEASIBLE",
193  "STAT_UNKNOWN"
194 };
195 
200 };
201 const std::string DecompPriceCutStrategyStr[3] = {
202  "Default",
203  "Favor Price",
204  "Favor Cut"
205 };
206 
207 //===========================================================================//
214 };
215 
216 //===========================================================================//
221 };
222 
227 };
228 
232 };
233 
234 //===========================================================================//
238 };
239 
245 };
246 
247 
248 
249 //===========================================================================//
251  //original row
253  //branching row
255  //convexity constraint
257  //row which is a cut
259 };
260 const std::string DecompRowTypeStr[4] = {
261  "DecompRow_Original",
262  "DecompRow_Branch",
263  "DecompRow_Convex",
264  "DecompRow_Cut"
265 };
266 
267 //===========================================================================//
268 //Corresponding to the class DecompVar
270  // points generated from bounded subproblem
272  // rays generated from unbounded subproblem
274 };
275 
276 
277 
278 //===========================================================================//
280  //structural column
282  //structural column (which should never be deleted)
284  //master-only column
286  //artifical column for original row (L for <=)
288  //artifical column for original row (G for >=)
290  //artifical column for branching row (L for <=)
292  //artifical column for branching row (G for >=)
294  //artifical column for convexity row (L for <=)
296  //artifical column for convexity row (G for >=)
298  //artifical column for cut (L for <=)
300  //artifical column for cutG(L for >=)
302  //marker used for deletion
304 };
305 const std::string DecompColTypeStr[12] = {
306  "DecompCol_Structural",
307  "DecompCol_Structural_NoDelete",
308  "DecompCol_MasterOnly",
309  "DecompCol_ArtForRowL",
310  "DecompCol_ArtForRowG",
311  "DecompCol_ArtForBranchL",
312  "DecompCol_ArtForBranchG",
313  "DecompCol_ArtForConvexL",
314  "DecompCol_ArtForConvexG",
315  "DecompCol_ArtForCutL",
316  "DecompCol_ArtForCutG",
317  "DecompCol_ToBeDeleted"
318 };
319 
323 };
324 /*
325 enum DecompNumericErrorType {
326 
327 
328 
329 };
330 */
331 
332 //---
333 //--- COIN vectors can do some extra checking if this is true,
334 //--- but, it is expensive, so turn off when in optimized mode
335 //---
336 #ifdef NDEBUG
337 #define DECOMP_TEST_DUPINDEX false
338 #else
339 #define DECOMP_TEST_DUPINDEX true
340 #endif
341 
342 #endif
DecompSolStatOptimal
@ DecompSolStatOptimal
Definition: Decomp.h:210
DecompPhaseStr
const std::string DecompPhaseStr[6]
Definition: Decomp.h:172
DecompColType
DecompColType
Definition: Decomp.h:279
DecompCutList
std::list< DecompCut * > DecompCutList
Definition: Decomp.h:93
DecompCol_ArtForCutG
@ DecompCol_ArtForCutG
Definition: Decomp.h:301
DecompStatError
@ DecompStatError
Definition: Decomp.h:219
DecompRoundRobin
DecompRoundRobin
Definition: Decomp.h:229
DecompMainParam::timeSetupReal
double timeSetupReal
Definition: Decomp.h:114
DecompStopInfeasible
@ DecompStopInfeasible
Definition: Decomp.h:145
DecompPriceCutStrategy
DecompPriceCutStrategy
Definition: Decomp.h:196
DecompRow_Convex
@ DecompRow_Convex
Definition: Decomp.h:256
DecompVarType
DecompVarType
Definition: Decomp.h:269
DecompBranchInMaster
@ DecompBranchInMaster
Definition: Decomp.h:322
DecompMainParam
Definition: Decomp.h:109
DecompSolStatInfeasible
@ DecompSolStatInfeasible
Definition: Decomp.h:212
DecompMainParam::timeSolveCpu
double timeSolveCpu
Definition: Decomp.h:115
DecompStatus
DecompStatus
Definition: Decomp.h:184
SubProbScheduleRuntime
@ SubProbScheduleRuntime
Definition: Decomp.h:244
DecompStatOk
@ DecompStatOk
Definition: Decomp.h:218
CoinPackedVector.hpp
DecompVar
Definition: DecompVar.h:29
DecompVar_Point
@ DecompVar_Point
Definition: Decomp.h:271
OsiCbcSolverInterface.hpp
DecompCol_ArtForBranchL
@ DecompCol_ArtForBranchL
Definition: Decomp.h:291
DecompSolStatFeasible
@ DecompSolStatFeasible
Definition: Decomp.h:211
DecompFuncGeneric
@ DecompFuncGeneric
Definition: Decomp.h:236
DecompCol_ToBeDeleted
@ DecompCol_ToBeDeleted
Definition: Decomp.h:303
DecompAlgoStr
const std::string DecompAlgoStr[5]
Definition: Decomp.h:130
PHASE_PRICE1
@ PHASE_PRICE1
Definition: Decomp.h:166
RELAX_AND_CUT
@ RELAX_AND_CUT
Definition: Decomp.h:126
OsiClpSolverInterface.hpp
OsiGrbSolverInterface.hpp
DecompCol_ArtForCutL
@ DecompCol_ArtForCutL
Definition: Decomp.h:299
DecompCol_ArtForConvexL
@ DecompCol_ArtForConvexL
Definition: Decomp.h:295
DecompStopGap
@ DecompStopGap
Definition: Decomp.h:143
DecompStopTime
@ DecompStopTime
Definition: Decomp.h:147
DecompAlgoStop
DecompAlgoStop
Definition: Decomp.h:141
RoundRobinRotate
@ RoundRobinRotate
Definition: Decomp.h:230
PHASE_DONE
@ PHASE_DONE
Definition: Decomp.h:169
FavorPrice
@ FavorPrice
Definition: Decomp.h:198
PRICE_AND_CUT
@ PRICE_AND_CUT
Definition: Decomp.h:125
FavorCut
@ FavorCut
Definition: Decomp.h:199
DecompBarrier
@ DecompBarrier
Definition: Decomp.h:226
DecompBranchingImplementation
DecompBranchingImplementation
Definition: Decomp.h:320
DecompSolStatNoSolution
@ DecompSolStatNoSolution
Definition: Decomp.h:213
DecompMainParam::bestUB
double bestUB
Definition: Decomp.h:118
DecompCol_ArtForBranchG
@ DecompCol_ArtForBranchG
Definition: Decomp.h:293
STAT_UNKNOWN
@ STAT_UNKNOWN
Definition: Decomp.h:188
CoinFinite.hpp
DecompStatusStr
const std::string DecompStatusStr[3]
Definition: Decomp.h:190
DecompCol_MasterOnly
@ DecompCol_MasterOnly
Definition: Decomp.h:285
DecompStopBound
@ DecompStopBound
Definition: Decomp.h:146
DecompPriceCutStrategyStr
const std::string DecompPriceCutStrategyStr[3]
Definition: Decomp.h:201
DecompStopIterLimit
@ DecompStopIterLimit
Definition: Decomp.h:148
DecompZero
const double DecompZero
Definition: Decomp.h:101
PHASE_PRICE2
@ PHASE_PRICE2
Definition: Decomp.h:167
DecompColTypeStr
const std::string DecompColTypeStr[12]
Definition: Decomp.h:305
DecompEpsilon
const double DecompEpsilon
Definition: Decomp.h:100
PHASE_UNKNOWN
@ PHASE_UNKNOWN
Definition: Decomp.h:170
PHASE_CUT
@ PHASE_CUT
Definition: Decomp.h:168
DecompAlgoType
DecompAlgoType
Definition: Decomp.h:123
DecompCol_Structural_NoDelete
@ DecompCol_Structural_NoDelete
Definition: Decomp.h:283
DecompFunction
DecompFunction
Definition: Decomp.h:235
DecompMainParam::timeSetupCpu
double timeSetupCpu
Definition: Decomp.h:113
SubProbScheduleGuided
@ SubProbScheduleGuided
Definition: Decomp.h:243
DecompDualSimplex
@ DecompDualSimplex
Definition: Decomp.h:224
DecompSubProbParallelType
DecompSubProbParallelType
Definition: Decomp.h:240
STAT_IP_FEASIBLE
@ STAT_IP_FEASIBLE
Definition: Decomp.h:186
STAT_FEASIBLE
@ STAT_FEASIBLE
Definition: Decomp.h:185
DecompGenericStatus
DecompGenericStatus
Definition: Decomp.h:217
DecompMainParam::bestLB
double bestLB
Definition: Decomp.h:117
OsiCpxSolverInterface.hpp
CoinPackedMatrix.hpp
DecompRow_Cut
@ DecompRow_Cut
Definition: Decomp.h:258
DecompCut
Definition: DecompCut.h:34
VOL_AND_CUT
@ VOL_AND_CUT
Definition: Decomp.h:127
DECOMP
@ DECOMP
Definition: Decomp.h:128
DecompMainParam::timeSolveReal
double timeSolveReal
Definition: Decomp.h:116
SubProbScheduleDynamic
@ SubProbScheduleDynamic
Definition: Decomp.h:242
Default
@ Default
Definition: Decomp.h:197
SubProbScheduleStatic
@ SubProbScheduleStatic
Definition: Decomp.h:241
DecompCol_ArtForConvexG
@ DecompCol_ArtForConvexG
Definition: Decomp.h:297
DecompMainParam::doCut
bool doCut
Definition: Decomp.h:110
DecompSolStatError
@ DecompSolStatError
Definition: Decomp.h:209
RoundRobinMostNegRC
@ RoundRobinMostNegRC
Definition: Decomp.h:231
DecompRowTypeStr
const std::string DecompRowTypeStr[4]
Definition: Decomp.h:260
DecompConfig.h
DecompRow_Original
@ DecompRow_Original
Definition: Decomp.h:252
DecompStatOutOfMemory
@ DecompStatOutOfMemory
Definition: Decomp.h:220
DecompRowType
DecompRowType
Definition: Decomp.h:250
DecompAlgoStopStr
const std::string DecompAlgoStopStr[7]
Definition: Decomp.h:150
DecompSolverStatus
DecompSolverStatus
Definition: Decomp.h:208
DecompMainParam::doDirect
bool doDirect
Definition: Decomp.h:112
DecompStopNo
@ DecompStopNo
Definition: Decomp.h:142
DecompCol_Structural
@ DecompCol_Structural
Definition: Decomp.h:281
DecompVar_Ray
@ DecompVar_Ray
Definition: Decomp.h:273
DecompCol_ArtForRowG
@ DecompCol_ArtForRowG
Definition: Decomp.h:289
DecompBranchInSubproblem
@ DecompBranchInSubproblem
Definition: Decomp.h:321
DecompCol_ArtForRowL
@ DecompCol_ArtForRowL
Definition: Decomp.h:287
DecompVarList
std::list< DecompVar * > DecompVarList
Definition: Decomp.h:91
DecompPhase
DecompPhase
Definition: Decomp.h:165
DecompRow_Branch
@ DecompRow_Branch
Definition: Decomp.h:254
DecompSolverType
DecompSolverType
Definition: Decomp.h:223
CoinError.hpp
DecompBigNum
const double DecompBigNum
Definition: Decomp.h:99
DecompMainParam::doPriceCut
bool doPriceCut
Definition: Decomp.h:111
STAT_INFEASIBLE
@ STAT_INFEASIBLE
Definition: Decomp.h:187
DecompStopTailOff
@ DecompStopTailOff
Definition: Decomp.h:144
DecompFuncGenerateInitVars
@ DecompFuncGenerateInitVars
Definition: Decomp.h:237
CUT
@ CUT
Definition: Decomp.h:124
DecompPrimSimplex
@ DecompPrimSimplex
Definition: Decomp.h:225