Dip 0.95.0
Loading...
Searching...
No Matches
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
67extern "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//---
90class DecompVar;
91class DecompCut;
92typedef std::list<DecompVar*> DecompVarList;
93typedef std::list<DecompCut*> DecompCutList;
94
95//===========================================================================//
96//---
97//--- DECOMP constants
98//---
99const double DecompBigNum = 1.0e21;
100const double DecompEpsilon = 1.0e-6;
101const double DecompZero = 1.0e-14;
102
103//===========================================================================//
104//---
105//--- DECOMP enums (for algorithms)
106//---
107
108
110 bool doCut;
117 double bestLB;
118 double bestUB;
119};
120
121
122
130const 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//---
150const 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//---
172const 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//---
190const std::string DecompStatusStr[3] = {
191 "STAT_FEASIBLE",
192 "STAT_INFEASIBLE",
193 "STAT_UNKNOWN"
194};
195
201const std::string DecompPriceCutStrategyStr[3] = {
202 "Default",
203 "Favor Price",
204 "Favor Cut"
205};
206
207//===========================================================================//
215
216//===========================================================================//
222
228
233
234//===========================================================================//
239
246
247
248
249//===========================================================================//
251 //original row
253 //branching row
255 //convexity constraint
257 //row which is a cut
259};
260const 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};
305const 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
324/*
325enum 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:92
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
double bestUB
Definition Decomp.h:118
double bestLB
Definition Decomp.h:117
double timeSetupReal
Definition Decomp.h:114
double timeSolveCpu
Definition Decomp.h:115