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 
128  DECOMP
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 
199  FavorCut
200 };
201 const std::string DecompPriceCutStrategyStr[3] = {
202  "Default",
203  "Favor Price",
204  "Favor Cut"
205 };
206 
207 //===========================================================================//
214 };
215 
216 //===========================================================================//
221 };
222 
226  DecompBarrier = 2
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
const std::string DecompRowTypeStr[4]
Definition: Decomp.h:260
DecompSubProbParallelType
Definition: Decomp.h:240
@ SubProbScheduleGuided
Definition: Decomp.h:243
@ SubProbScheduleDynamic
Definition: Decomp.h:242
@ SubProbScheduleStatic
Definition: Decomp.h:241
@ SubProbScheduleRuntime
Definition: Decomp.h:244
const std::string DecompAlgoStopStr[7]
Definition: Decomp.h:150
DecompBranchingImplementation
Definition: Decomp.h:320
@ DecompBranchInMaster
Definition: Decomp.h:322
@ DecompBranchInSubproblem
Definition: Decomp.h:321
const double DecompZero
Definition: Decomp.h:101
DecompStatus
Definition: Decomp.h:184
@ STAT_INFEASIBLE
Definition: Decomp.h:187
@ STAT_FEASIBLE
Definition: Decomp.h:185
@ STAT_UNKNOWN
Definition: Decomp.h:188
@ STAT_IP_FEASIBLE
Definition: Decomp.h:186
const std::string DecompPriceCutStrategyStr[3]
Definition: Decomp.h:201
const std::string DecompColTypeStr[12]
Definition: Decomp.h:305
DecompAlgoStop
Definition: Decomp.h:141
@ DecompStopNo
Definition: Decomp.h:142
@ DecompStopTailOff
Definition: Decomp.h:144
@ DecompStopIterLimit
Definition: Decomp.h:148
@ DecompStopBound
Definition: Decomp.h:146
@ DecompStopInfeasible
Definition: Decomp.h:145
@ DecompStopGap
Definition: Decomp.h:143
@ DecompStopTime
Definition: Decomp.h:147
DecompSolverType
Definition: Decomp.h:223
@ DecompBarrier
Definition: Decomp.h:226
@ DecompPrimSimplex
Definition: Decomp.h:225
@ DecompDualSimplex
Definition: Decomp.h:224
DecompGenericStatus
Definition: Decomp.h:217
@ DecompStatOutOfMemory
Definition: Decomp.h:220
@ DecompStatOk
Definition: Decomp.h:218
@ DecompStatError
Definition: Decomp.h:219
DecompAlgoType
Definition: Decomp.h:123
@ CUT
Definition: Decomp.h:124
@ DECOMP
Definition: Decomp.h:128
@ PRICE_AND_CUT
Definition: Decomp.h:125
@ VOL_AND_CUT
Definition: Decomp.h:127
@ RELAX_AND_CUT
Definition: Decomp.h:126
DecompSolverStatus
Definition: Decomp.h:208
@ DecompSolStatError
Definition: Decomp.h:209
@ DecompSolStatInfeasible
Definition: Decomp.h:212
@ DecompSolStatNoSolution
Definition: Decomp.h:213
@ DecompSolStatOptimal
Definition: Decomp.h:210
@ DecompSolStatFeasible
Definition: Decomp.h:211
DecompFunction
Definition: Decomp.h:235
@ DecompFuncGeneric
Definition: Decomp.h:236
@ DecompFuncGenerateInitVars
Definition: Decomp.h:237
const std::string DecompAlgoStr[5]
Definition: Decomp.h:130
std::list< DecompVar * > DecompVarList
Definition: Decomp.h:91
const std::string DecompPhaseStr[6]
Definition: Decomp.h:172
DecompRoundRobin
Definition: Decomp.h:229
@ RoundRobinRotate
Definition: Decomp.h:230
@ RoundRobinMostNegRC
Definition: Decomp.h:231
DecompRowType
Definition: Decomp.h:250
@ DecompRow_Branch
Definition: Decomp.h:254
@ DecompRow_Convex
Definition: Decomp.h:256
@ DecompRow_Cut
Definition: Decomp.h:258
@ DecompRow_Original
Definition: Decomp.h:252
DecompPriceCutStrategy
Definition: Decomp.h:196
@ FavorCut
Definition: Decomp.h:199
@ Default
Definition: Decomp.h:197
@ FavorPrice
Definition: Decomp.h:198
DecompVarType
Definition: Decomp.h:269
@ DecompVar_Point
Definition: Decomp.h:271
@ DecompVar_Ray
Definition: Decomp.h:273
const double DecompEpsilon
Definition: Decomp.h:100
DecompPhase
Definition: Decomp.h:165
@ PHASE_PRICE2
Definition: Decomp.h:167
@ PHASE_DONE
Definition: Decomp.h:169
@ PHASE_UNKNOWN
Definition: Decomp.h:170
@ PHASE_CUT
Definition: Decomp.h:168
@ PHASE_PRICE1
Definition: Decomp.h:166
std::list< DecompCut * > DecompCutList
Definition: Decomp.h:93
const std::string DecompStatusStr[3]
Definition: Decomp.h:190
DecompColType
Definition: Decomp.h:279
@ DecompCol_ArtForBranchL
Definition: Decomp.h:291
@ DecompCol_MasterOnly
Definition: Decomp.h:285
@ DecompCol_Structural
Definition: Decomp.h:281
@ DecompCol_ArtForBranchG
Definition: Decomp.h:293
@ DecompCol_ArtForConvexG
Definition: Decomp.h:297
@ DecompCol_ArtForRowL
Definition: Decomp.h:287
@ DecompCol_ToBeDeleted
Definition: Decomp.h:303
@ DecompCol_ArtForCutG
Definition: Decomp.h:301
@ DecompCol_ArtForRowG
Definition: Decomp.h:289
@ DecompCol_Structural_NoDelete
Definition: Decomp.h:283
@ DecompCol_ArtForConvexL
Definition: Decomp.h:295
@ DecompCol_ArtForCutL
Definition: Decomp.h:299
const double DecompBigNum
Definition: Decomp.h:99
double timeSolveReal
Definition: Decomp.h:116
double timeSetupCpu
Definition: Decomp.h:113
bool doPriceCut
Definition: Decomp.h:111
bool doDirect
Definition: Decomp.h:112
double bestUB
Definition: Decomp.h:118
double bestLB
Definition: Decomp.h:117
double timeSetupReal
Definition: Decomp.h:114
double timeSolveCpu
Definition: Decomp.h:115