Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
master.h
Go to the documentation of this file.
1
30#pragma once
31
34
37
38
39class OsiSolverInterface;
40
41#pragma GCC visibility push(default)
42namespace abacus {
43
44
45class Sub;
46class BranchRule;
47class Variable;
48class Constraint;
49
50class History;
51class OpenSub;
52class FixCand;
53class LpMasterOsi;
54
55template<class BaseType, class CoType> class StandardPool;
56
57
59
71
72 friend class Sub;
73 friend class FixCand;
74
75public:
76
78 enum STATUS {
79 Optimal,
86 Guaranteed,
92 ExceptionFathom
94 };
95
97
100 static const char* STATUS_[];
101
102
105 BestFirst,
110 DiveAndBest
112 };
113
115
118 static const char *ENUMSTRAT_[];
119
123 CloseHalfExpensive
125 };
126
128
131 static const char *BRANCHINGSTRAT_[];
132
134
140 NoPrimalBound,
143 OptimumOne
145 };
146
148
151 static const char* PRIMALBOUNDMODE_[];
152
155 SkipByNode,
157 SkipByLevel
158 };
159
161
164 static const char* SKIPPINGMODE_[];
165
172
173
175
178 static const char* CONELIMMODE_[];
179
183 ReducedCost
184 };
185
187
190 static const char* VARELIMMODE_[];
191
193 enum VBCMODE {
196 Pipe
197 };
198
200
203 static const char* VBCMODE_[];
204
205
207
210 enum OSISOLVER { Cbc, Clp, CPLEX, DyLP, FortMP, GLPK, MOSEK, OSL, SoPlex, SYMPHONY, XPRESS_MP, Gurobi, Csdp };
211
213 static const char* OSISOLVER_[];
214
216
240 Master(const char *problemName, bool cutting, bool pricing,
241 OptSense::SENSE optSense = OptSense::Unknown,
242 double eps = 1.0e-4, double machineEps = 1.0e-7,
243 double infinity = 1.0e30,
244 bool readParamFromFile = false);
245
247 virtual ~Master();
248
250
254
267
269 double lowerBound() const;
270
272 double upperBound() const;
273
275
279 double primalBound() const { return primalBound_; }
280
282
287 void primalBound(double x);
288
290
294 double dualBound() const { return dualBound_; }
295
297
302 void dualBound(double x);
303
305
308 bool betterDual(double x) const;
309
311
319 bool primalViolated(double x) const;
320
322
327 bool betterPrimal(double x) const;
328
330 double rootDualBound() const { return rootDualBound_; }
331
333 /***
334 * This function is only correct if any primal bound better than plus/minus infinity corresponds
335 * to a feasible solution.
336 *
337 * \return true If a feasible solution of the optimization problem has been found, false otherwise.
338 */
339 bool feasibleFound() const;
341
343 ENUMSTRAT enumerationStrategy() const { return enumerationStrategy_; }
344
346
349 void enumerationStrategy(ENUMSTRAT strat) { enumerationStrategy_ = strat; }
350
364 virtual int enumerationStrategy(const Sub *s1, const Sub *s2);
365
367
380 bool guaranteed() const;
381
383
389 double guarantee() const;
390
392
396 void printGuarantee() const;
397
399
407 bool check() const;
408
421 bool knownOptimum(double &optVal) const;
422
424 virtual void output() const { }
425
432 bool cutting() const { return cutting_; }
433
440 bool pricing() const { return pricing_; }
441
443 const OptSense *optSense() const { return &optSense_; }
444
446 History *history() const { return history_; }
447
449 OpenSub *openSub() const { return openSub_; }
450
452 StandardPool<Constraint, Variable> *conPool() const { return conPool_; }
453
455 StandardPool<Constraint, Variable> *cutPool() const { return cutPool_; }
456
458 StandardPool<Variable, Constraint> *varPool() const { return varPool_; }
459
461
464 Sub *root() const { return root_; }
465
471 Sub *rRoot() const { return rRoot_; }
472
474 STATUS status() const { return status_; }
475
477 const string &problemName() const { return problemName_; }
478
480 const ogdf::StopwatchWallClock *totalCowTime() const { return &totalCowTime_; }
481
483 inline bool solveApprox() const { return solveApprox_; }
484
486 const ogdf::StopwatchCPU *totalTime() const { return &totalTime_; }
487
489 const ogdf::StopwatchCPU *lpTime() const { return &lpTime_; }
490
492 const ogdf::StopwatchCPU *lpSolverTime() const { return &lpSolverTime_; }
493
495 const ogdf::StopwatchCPU *separationTime() const { return &separationTime_; }
496
498 const ogdf::StopwatchCPU *improveTime() const { return &improveTime_; }
499
501 const ogdf::StopwatchCPU *pricingTime() const { return &pricingTime_; }
502
504 const ogdf::StopwatchCPU *branchingTime() const { return &branchingTime_; }
505
507 int nSub() const { return nSub_; }
508
510 int nLp() const { return nLp_; }
511
513 int highestLevel() const { return highestLevel_; }
514
516 int nNewRoot() const { return nNewRoot_; }
517
519 int nSubSelected() const { return nSubSelected_; }
520
522 void printParameters() const;
523
525 BRANCHINGSTRAT branchingStrategy() const { return branchingStrategy_; }
526
528
531 void branchingStrategy(BRANCHINGSTRAT strat) { branchingStrategy_ = strat; }
532
534 OSISOLVER defaultLpSolver() const { return defaultLpSolver_; }
535
537
540 void defaultLpSolver(OSISOLVER osiSolver) { defaultLpSolver_ = osiSolver; }
541
542 LpMasterOsi *lpMasterOsi() const { return lpMasterOsi_; }
543
545 int nBranchingVariableCandidates() const { return nBranchingVariableCandidates_; }
546
548
553
555 int nStrongBranchingIterations() const { return nStrongBranchingIterations_; }
556
558
562
564 double requiredGuarantee() const { return requiredGuarantee_; }
565
567
574 void requiredGuarantee(double g);
575
577
580 int maxLevel() const { return maxLevel_; }
581
583
588 void maxLevel(int ml);
589
591
594 int maxNSub() const { return maxNSub_; }
595
597
602 void maxNSub(int ml);
603
605 int64_t maxCpuTime() const { return maxCpuTime_; }
606
608 string maxCpuTimeAsString() const;
609
611
614 void maxCpuTime(const string &t);
615
617 void maxCpuTime(int64_t seconds) { maxCpuTime_ = seconds; }
618
620 void maxCpuTime(int hour, int min, int sec);
621
623 int64_t maxCowTime() const { return maxCowTime_; }
624
626 string maxCowTimeAsString() const;
627
629 void maxCowTime(int64_t seconds) { maxCowTime_ = seconds; }
630
632
635 void maxCowTime(const string &t);
636
638 bool objInteger() const { return objInteger_; }
639
641
644 void objInteger(bool b) { objInteger_ = b; }
645
647 int tailOffNLp() const { return tailOffNLp_; }
648
650
656 void tailOffNLp(int n) { tailOffNLp_ = n; }
657
659 double tailOffPercent() const { return tailOffPercent_; }
660
662
668 void tailOffPercent(double p);
669
671
674 bool delayedBranching(int nOpt) const;
675
677
688 void dbThreshold(int threshold) { dbThreshold_ = threshold; }
689
691
694 int dbThreshold() const { return dbThreshold_; }
695
697
701 int minDormantRounds() const { return minDormantRounds_; }
702
704
707 void minDormantRounds(int nRounds) { minDormantRounds_ = nRounds; }
708
710 PRIMALBOUNDMODE pbMode() const { return pbMode_; }
711
713
716 void pbMode(PRIMALBOUNDMODE mode) { pbMode_ = mode; }
717
719
726 int pricingFreq() const { return pricingFreq_; }
727
729
732 void pricingFreq(int f);
733
735 int skipFactor() const { return skipFactor_; }
736
738
741 void skipFactor(int f);
742
744
747 void skippingMode(SKIPPINGMODE mode) { skippingMode_ = mode; }
748
750 SKIPPINGMODE skippingMode() const { return skippingMode_; }
751
753 CONELIMMODE conElimMode() const { return conElimMode_; }
754
756
759 void conElimMode(CONELIMMODE mode) { conElimMode_ = mode; }
760
762 VARELIMMODE varElimMode() const { return varElimMode_; }
763
765
768 void varElimMode(VARELIMMODE mode) { varElimMode_ = mode; }
769
771 double conElimEps() const { return conElimEps_; }
772
774
777 void conElimEps(double eps) { conElimEps_ = eps; }
778
780 double varElimEps() const { return varElimEps_; }
781
783
786 void varElimEps(double eps) { varElimEps_ = eps; }
787
789 int varElimAge() const { return varElimAge_; }
790
792
795 void varElimAge(int age) { varElimAge_ = age; }
796
798 int conElimAge() const { return conElimAge_; }
799
801
804 void conElimAge(int age) { conElimAge_ = age; }
805
810 bool fixSetByRedCost() const { return fixSetByRedCost_; }
811
813
817 void fixSetByRedCost(bool on) { fixSetByRedCost_ = on; }
818
823 bool printLP() const { return printLP_; }
824
826
830 void printLP(bool on) { printLP_ = on; }
831
833 int maxConAdd() const { return maxConAdd_; }
834
836 /***
837 * \param max The maximal number of constraints.
838 */
839 void maxConAdd(int max) { maxConAdd_ = max; }
840
842 int maxConBuffered() const { return maxConBuffered_; }
843
845
851 void maxConBuffered(int max) { maxConBuffered_ = max; }
852
854 int maxVarAdd() const { return maxVarAdd_; }
855
857
860 void maxVarAdd(int max) { maxVarAdd_ = max; }
861
863 int maxVarBuffered() const { return maxVarBuffered_; }
864
866
872 void maxVarBuffered(int max) { maxVarBuffered_ = max; }
873
875 int maxIterations() const { return maxIterations_; }
876
878
887 void maxIterations(int max) { maxIterations_ = max; }
888
893 bool eliminateFixedSet() const { return eliminateFixedSet_; }
894
896
900 void eliminateFixedSet(bool turnOn) { eliminateFixedSet_ = turnOn; }
901
907 bool newRootReOptimize() const { return newRootReOptimize_; }
908
910
913 void newRootReOptimize(bool on) { newRootReOptimize_ = on; }
914
916 const string &optimumFileName() const { return optimumFileName_; }
917
919
922 void optimumFileName(const char *name) { optimumFileName_ = name; }
923
930 bool showAverageCutDistance() const { return showAverageCutDistance_; }
931
933
936 void showAverageCutDistance(bool on) { showAverageCutDistance_ = on; }
937
939 VBCMODE vbcLog() const { return VbcLog_; }
940
942
948 void vbcLog(VBCMODE mode) { VbcLog_ = mode; }
949
951
956 virtual bool setSolverParameters(OsiSolverInterface* interface, bool solverIsApprox);
957
958protected:
959
961
979 virtual void initializePools(
980 ArrayBuffer<Constraint*> &constraints,
981 ArrayBuffer<Variable*> &variables,
982 int varPoolSize,
983 int cutPoolSize,
984 bool dynamicCutPool = false);
985
987
1009 virtual void initializePools(
1010 ArrayBuffer<Constraint*> &constraints,
1012 ArrayBuffer<Variable*> &variables,
1013 int varPoolSize,
1014 int cutPoolSize,
1015 bool dynamicCutPool = false);
1016
1024 void initializeOptSense(OptSense::SENSE sense) { optSense_.sense(sense); }
1025
1027
1040 int bestFirstSearch(const Sub* s1, const Sub* s2) const;
1041
1067 virtual int equalSubCompare(const Sub *s1, const Sub *s2) const;
1068
1070
1081 int depthFirstSearch(const Sub* s1, const Sub* s2) const;
1082
1084
1096 int breadthFirstSearch(const Sub* s1, const Sub* s2) const;
1097
1098
1100
1108 int diveAndBestFirstSearch(const Sub *s1, const Sub* s2) const;
1109
1115 virtual void initializeParameters() { }
1116
1118
1123 virtual Sub *firstSub() = 0;
1124
1131 virtual void initializeOptimization() { }
1132
1139 virtual void terminateOptimization() { }
1140
1142 virtual void assignParameters();
1143
1144private:
1145
1147
1165
1169
1171
1175
1177
1181
1183
1187
1189
1196
1197 int initLP();
1198
1200
1206 void writeTreeInterface(const string &info, bool time = true) const;
1207
1213 void treeInterfaceNewNode(Sub *sub) const;
1214
1216 void treeInterfacePaintNode(int id, int color) const;
1217
1219 void treeInterfaceLowerBound(double lb) const;
1220
1222 void treeInterfaceUpperBound(double ub) const;
1223
1225 void treeInterfaceNodeBounds(int id, double lb, double ub);
1226
1228
1231 void newSub(int level);
1232
1234 void countLp() { ++nLp_; }
1235
1237 void newFixed(int n) { nFixed_ += n; }
1238
1240 void addCons(int n) { nAddCons_ += n; }
1241
1243 void removeCons(int n) { nRemCons_ += n; }
1244
1246 void addVars(int n) { nAddVars_ += n; }
1247
1249 void removeVars(int n) { nRemVars_ += n; }
1250
1252 FixCand *fixCand() const { return fixCand_; }
1253
1255
1262 void rRoot(Sub *newRoot, bool reoptimize);
1263
1265 void status(STATUS stat) { status_ = stat; }
1266
1268
1271 void rootDualBound(double x);
1272
1274
1277
1279
1282
1285
1288
1291
1294
1297
1300
1303
1306
1309
1311
1314
1315
1318
1321
1324
1327
1330
1333
1336
1339
1342
1345
1348
1350 std::ostream *treeStream_;
1351
1353
1357
1359
1363
1365
1369
1372
1375
1378
1381
1384
1387
1394
1397
1400
1403
1409
1412
1415
1418
1421
1424
1427
1430
1433
1439
1442
1448
1451
1454
1457
1460
1463
1466
1469
1472
1475
1478
1480
1483
1486
1489
1492
1495
1497 int nLp_;
1498
1501
1504
1507
1510
1513
1516
1519
1520 Master(const Master &rhs);
1521 const Master &operator=(const Master& rhs);
1522};
1523
1524
1525inline double Master::lowerBound() const
1526{
1527 if (optSense_.max()) return primalBound_;
1528 else return dualBound_;
1529}
1530
1531inline double Master::upperBound() const
1532{
1533 if (optSense_.max()) return dualBound_;
1534 else return primalBound_;
1535}
1536
1537}
1538#pragma GCC visibility pop
Declaration of stopwatch classes.
Global data and functions.
Definition global.h:58
Candidates for fixing.
Definition fixcand.h:64
Solution histories.
Definition history.h:44
The OSI LP master.
Definition lpmasterosi.h:44
The master of the optimization.
Definition master.h:70
Sub * root_
The root node of the enumeration tree.
Definition master.h:1284
int maxVarAdd() const
Returns the maximal number of variables which should be added in the column generation algorithm.
Definition master.h:854
int varElimAge() const
Returns the age for the elimination of variables by the reduced cost criterion.
Definition master.h:789
bool betterPrimal(double x) const
Can be used to check if a value is better than the best know primal bound.
ogdf::StopwatchCPU lpSolverTime_
Definition master.h:1479
History * history() const
Returns a pointer to the object storing the solution history of this branch and cut problem.
Definition master.h:446
int maxNSub() const
Returns the maximal number of subproblems to be processed.
Definition master.h:594
int maxLevel() const
Returns the maximal depth up to which the enumeration should be performed.
Definition master.h:580
void defaultLpSolver(OSISOLVER osiSolver)
Changes the default Lp solver to osiSolver.
Definition master.h:540
void maxVarAdd(int max)
Changes the maximal number of variables that are added in an iteration of the subproblem optimization...
Definition master.h:860
int nBranchingVariableCandidates_
The number of candidates that are evaluated for branching on variables.
Definition master.h:1302
ENUMSTRAT enumerationStrategy_
The enumeration strategy.
Definition master.h:1296
void nStrongBranchingIterations(int n)
Sets the number of simplex iterations that are performed when testing candidates for branching variab...
void maxConAdd(int max)
Sets the maximal number of constraints that are added in an iteration of the cutting plane algorithm.
Definition master.h:839
int bestFirstSearch(const Sub *s1, const Sub *s2) const
Implements the best first search enumeration.
bool newRootReOptimize_
If true, then an already earlier processed node is reoptimized if it becomes the new root of the rema...
Definition master.h:1438
int maxConBuffered_
The size of the buffer for generated cutting planes.
Definition master.h:1420
int maxNSub_
The maximal number of subproblems to be processed.
Definition master.h:1368
int highestLevel_
The highest level which has been reached in the enumeration tree.
Definition master.h:1500
void maxConBuffered(int max)
Changes the maximal number of constraints that are buffered in an iteration of the cutting plane algo...
Definition master.h:851
CONELIMMODE conElimMode_
The way constraints are automatically eliminated in the cutting plane algorithm.
Definition master.h:1450
void pricingFreq(int f)
Sets the number of linear programs being solved between two additional pricing steps to f.
void enumerationStrategy(ENUMSTRAT strat)
Changes the enumeration strategy to strat.
Definition master.h:349
double lowerBound() const
Returns the value of the global lower bound.
Definition master.h:1525
void treeInterfaceNewNode(Sub *sub) const
Adds the subproblem sub to the stream storing information for graphical output of the enumeration tre...
int nStrongBranchingIterations() const
The number of simplex iterations that are performed when testing candidates for branching variables w...
Definition master.h:555
bool printLP() const
Definition master.h:823
void branchingStrategy(BRANCHINGSTRAT strat)
Changes the branching strategy to strat.
Definition master.h:531
ogdf::StopwatchCPU branchingTime_
The timer for the cpu time spent in determining the branching rules.
Definition master.h:1491
double requiredGuarantee() const
The guarantee specification for the optimization.
Definition master.h:564
void primalBound(double x)
Sets the primal bound to x and makes a new entry in the solution history.
void varElimAge(int age)
Changes the age for the elimination of variables by the reduced cost criterion to age.
Definition master.h:795
StandardPool< Constraint, Variable > * conPool() const
Returns a pointer to the default pool storing the constraints of the problem formulation.
Definition master.h:452
void maxCowTime(int64_t seconds)
Sets the maximally allowed wall-clock time to seconds.
Definition master.h:629
BRANCHINGSTRAT
This enumeration defines the two currently implemented branching variable selection strategies.
Definition master.h:121
@ CloseHalf
Selects the variable with fractional part closest to 0.5.
Definition master.h:122
BRANCHINGSTRAT branchingStrategy_
The branching strategy.
Definition master.h:1299
const ogdf::StopwatchCPU * totalTime() const
returns a pointer to the timer measuring the total cpu time for the optimization.
Definition master.h:486
VARELIMMODE varElimMode() const
Returns the mode for the elimination of variables.
Definition master.h:762
double rootDualBound() const
Returns the dual bound at the root node.
Definition master.h:330
const ogdf::StopwatchCPU * lpSolverTime() const
Return a pointer to the timer measuring the cpu time required by the LP solver.
Definition master.h:492
virtual void initializePools(ArrayBuffer< Constraint * > &constraints, ArrayBuffer< Variable * > &variables, int varPoolSize, int cutPoolSize, bool dynamicCutPool=false)
Sets up the default pools for variables, constraints, and cutting planes.
const string & optimumFileName() const
Returns the name of the file that stores the optimum solutions.
Definition master.h:916
void maxNSub(int ml)
Changes the maximal number of subproblems to ml.
double tailOffPercent_
The minimal change of the LP-value on the tailing off analysis.
Definition master.h:1383
ENUMSTRAT enumerationStrategy() const
Returns the enumeration strategy.
Definition master.h:343
StandardPool< Constraint, Variable > * cutPool_
The default pool of dynamically generated constraints.
Definition master.h:1317
int maxIterations() const
Returns the maximal number of iterations per subproblem optimization (-1 means no iteration limit).
Definition master.h:875
void _setDefaultLpParameters()
Initializes the LP solver specific default parameters if they are not read from .abacus.
void nBranchingVariableCandidates(int n)
Sets the number of tested branching variable candidates to n.
void newFixed(int n)
Increments the counter of the number of fixed variables by n.
Definition master.h:1237
bool pricing() const
Definition master.h:440
const ogdf::StopwatchCPU * lpTime() const
Returns a pointer to the timer measuring the cpu time spent in members of the LP-interface.
Definition master.h:489
double varElimEps_
The tolerance for the elimination of variables by the mode ReducedCost.
Definition master.h:1459
Master(const char *problemName, bool cutting, bool pricing, OptSense::SENSE optSense=OptSense::Unknown, double eps=1.0e-4, double machineEps=1.0e-7, double infinity=1.0e30, bool readParamFromFile=false)
The constructor.
bool fixSetByRedCost() const
Definition master.h:810
int maxIterations_
The maximal number of iterations of the cutting plane/column generation algorithm in the subproblem.
Definition master.h:1429
int nStrongBranchingIterations_
The number of simplex iterations that are performed when testing a branching variable candidate withi...
Definition master.h:1305
void dualBound(double x)
Sets the dual bound to x and makes a new entry in the solution history.
void addVars(int n)
Increments the counter for the total number of added variables by n.
Definition master.h:1246
int minDormantRounds() const
Returns the maximal number of rounds, i.e., number of subproblem optimizations, a subproblem is dorma...
Definition master.h:701
Master(const Master &rhs)
bool primalViolated(double x) const
Can be used to compare a value with the one of the best known primal bound.
PRIMALBOUNDMODE pbMode_
The mode of the primal bound initialization.
Definition master.h:1396
void maxLevel(int ml)
This version of the function maxLevel() changes the maximal enumeration depth.
void varElimMode(VARELIMMODE mode)
Changes the variable elimination mode to mode.
Definition master.h:768
int maxVarBuffered_
The size of the buffer for generated variables.
Definition master.h:1426
bool newRootReOptimize() const
Definition master.h:907
double dualBound_
The best known dual bound.
Definition master.h:1326
int nNewRoot() const
Returns the number of root changes of the remaining branch-and-cut tree.
Definition master.h:516
void removeCons(int n)
Increments the counter for the total number of removed constraints by n.
Definition master.h:1243
void minDormantRounds(int nRounds)
Sets the number of rounds a subproblem should stay dormant to nRounds.
Definition master.h:707
int nRemCons_
The total number of removed constraints.
Definition master.h:1509
double primalBound() const
Returns the value of the primal bound.
Definition master.h:279
Sub * select()
Returns a pointer to an open subproblem for further processing.
double guarantee() const
Can be used to access the guarantee which can be given for the best known feasible solution.
CONELIMMODE conElimMode() const
Returns the mode for the elimination of constraints.
Definition master.h:753
STATUS
The various statuses of the optimization process.
Definition master.h:78
@ Unprocessed
The initial status, before the optimization starts.
Definition master.h:84
@ Error
An error occurred during the optimization process.
Definition master.h:82
@ MaxLevel
The status, if subproblems are ignored since the maximum enumeration level is exceeded.
Definition master.h:88
@ Processing
The status while the optimization is performed.
Definition master.h:85
@ MaxCpuTime
The status, if the optimization terminates since the maximum cpu time is exceeded.
Definition master.h:89
@ MaxNSub
The status, if the optimization terminates since the maximum number of subproblems is reached.
Definition master.h:90
@ MaxCowTime
The status, if the optimization terminates since the maximum wall-clock time is exceeded.
Definition master.h:91
const ogdf::StopwatchCPU * pricingTime() const
Returns a pointer to the timer measuring the cpu time spent in pricing.
Definition master.h:501
STATUS status_
The current status of the optimization.
Definition master.h:1468
virtual void assignParameters()
Assigns the parameters that were read from a file to the member variables of the master.
virtual bool setSolverParameters(OsiSolverInterface *interface, bool solverIsApprox)
Sets solver specific parameters.
void optimumFileName(const char *name)
Changes the name of the file in which the value of the optimum solution is searched.
Definition master.h:922
int64_t maxCpuTime() const
Returns the maximal cpu time (in seconds) which can be used by the optimization.
Definition master.h:605
VARELIMMODE
This enumeration defines the ways for automatic variable elimination during the column generation alg...
Definition master.h:181
@ NoVarElim
No variables are eliminated.
Definition master.h:182
bool knownOptimum(double &optVal) const
Opens the file specified with the parameter OptimumFileName in the configuration file ....
bool betterDual(double x) const
Returns true if x is better than the best known dual bound; false otherwise.
virtual ~Master()
The destructor.
void rRoot(Sub *newRoot, bool reoptimize)
Sets the root of the remaining branch-and-cut tree to newRoot.
bool feasibleFound() const
We use this function, e.g., to adapt the enumeration strategy in the DiveAndBest-Strategy.
void maxCpuTime(int hour, int min, int sec)
Sets the maximally allowed cpu time for the optimization to hour, min, sec.
ogdf::StopwatchCPU improveTime_
The timer for the cpu time spent in the heuristics for the computation of feasible solutions.
Definition master.h:1485
bool delayedBranching(int nOpt) const
Returns true if the number of optimizations nOpt of a subproblem exceeds the delayed branching thresh...
void dbThreshold(int threshold)
Sets the number of optimizations of a subproblem until sons are created in Sub::branching().
Definition master.h:688
void _deleteLpMasters()
void removeVars(int n)
Increments the counter for the total number of removed variables by n.
Definition master.h:1249
void conElimAge(int age)
Changes the age for the elimination of constraints to age.
Definition master.h:804
StandardPool< Constraint, Variable > * cutPool() const
Returns a pointer to the default pool for the generated cutting planes.
Definition master.h:455
OSISOLVER
This enumeration defines which solvers can be used to solve the LP-relaxations.
Definition master.h:210
void status(STATUS stat)
Sets the status of the Master.
Definition master.h:1265
void varElimEps(double eps)
Changes the tolerance for the elimination of variables by the reduced cost criterion to eps.
Definition master.h:786
History * history_
The solution history.
Definition master.h:1293
void tailOffPercent(double p)
Sets the minimal change of the dual bound for the tailing off analysis to p.
const ogdf::StopwatchCPU * separationTime() const
Returns a pointer to the timer measuring the cpu time spent in the separation of cutting planes.
Definition master.h:495
StandardPool< Constraint, Variable > * conPool_
The default pool with the constraints of the problem formulation.
Definition master.h:1313
double primalBound_
The best known primal bound.
Definition master.h:1323
int nSubSelected() const
Returns the number of subproblems which have already been selected from the set of open subproblems.
Definition master.h:519
FixCand * fixCand() const
Returns a pointer to the object storing the variables which are candidates for being fixed.
Definition master.h:1252
Sub * rRoot_
The root node of the remaining enumeration tree.
Definition master.h:1287
OptSense optSense_
The sense of the objective function.
Definition master.h:1281
int nLp_
The number of solved LPs.
Definition master.h:1497
CONELIMMODE
This enumeration defines the ways for automatic constraint elimination during the cutting plane phase...
Definition master.h:167
@ NonBinding
Nonbinding constraints are eliminated.
Definition master.h:169
@ NoConElim
No constraints are eliminated.
Definition master.h:168
void writeTreeInterface(const string &info, bool time=true) const
Writes the string info to the stream associated with the Tree Interface.
FixCand * fixCand_
The variables which are candidates for being fixed.
Definition master.h:1332
int minDormantRounds_
The minimal number of rounds, i.e., number of subproblem optimizations, a subproblem is dormant,...
Definition master.h:1393
void conElimMode(CONELIMMODE mode)
Changes the constraint elimination mode to mode.
Definition master.h:759
void _initializeParameters()
Reads the parameter-file .abacus.
int maxConBuffered() const
Returns the size of the buffer for generated constraints in the cutting plane algorithm.
Definition master.h:842
void skipFactor(int f)
Sets the frequency for constraint and variable generation to f.
void conElimEps(double eps)
Changes the tolerance for the elimination of constraints by the slack criterion to eps.
Definition master.h:777
void _initializeLpParameters()
bool showAverageCutDistance_
If true then the average distance of the added cutting planes is output every iteration of the cuttin...
Definition master.h:1447
ogdf::StopwatchCPU lpTime_
The timer for the cpu time spent in the LP-interface.
Definition master.h:1477
bool eliminateFixedSet_
If true, then nonbasic fixed and set variables are eliminated.
Definition master.h:1432
void fixSetByRedCost(bool on)
Turns fixing and setting variables by reduced cost on or off.
Definition master.h:817
double tailOffPercent() const
Returns the minimal change of the dual bound for the tailing off analysis in percent.
Definition master.h:659
int conElimAge_
The number of iterations an elimination criterion must be satisfied until a constraint can be removed...
Definition master.h:1462
double conElimEps() const
Returns the zero tolerance for the elimination of constraints by the slack criterion.
Definition master.h:771
StandardPool< Variable, Constraint > * varPool_
The default pool with the variables of the problem formulation.
Definition master.h:1320
LpMasterOsi * lpMasterOsi_
Definition master.h:1310
bool objInteger_
true, if all objective function values of feasible solutions are assumed to be integer.
Definition master.h:1377
bool cutting() const
Definition master.h:432
void rootDualBound(double x)
Updates the final dual bound of the root node.
ogdf::StopwatchWallClock totalCowTime_
The timer for the total elapsed time.
Definition master.h:1471
double requiredGuarantee_
The guarantee in percent which should be reached when the optimization stops.
Definition master.h:1356
int64_t maxCowTime() const
Returns the maximal wall-clock time (in seconds) which can be used by the optimization.
Definition master.h:623
int pricingFreq_
The number of solved LPs between two additional pricing steps.
Definition master.h:1399
int tailOffNLp_
The number of LP-iterations for the tailing off analysis.
Definition master.h:1380
LpMasterOsi * lpMasterOsi() const
Definition master.h:542
virtual int equalSubCompare(const Sub *s1, const Sub *s2) const
Is called from the function bestFirstSearch() and from the function depthFirstSearch() if the subprob...
string problemName_
The name of the optimized problem.
Definition master.h:1276
int diveAndBestFirstSearch(const Sub *s1, const Sub *s2) const
Performs depth-first search until a feasible solution is found, then the search process is continued ...
OpenSub * openSub() const
Returns a pointer to the set of open subproblems.
Definition master.h:449
int maxVarBuffered() const
Returns the size of the buffer for the variables generated in the column generation algorithm.
Definition master.h:863
VBCMODE VbcLog_
Ouput for the Tree Interface is generated depending on the value of this variable.
Definition master.h:1347
void treeInterfaceNodeBounds(int id, double lb, double ub)
Updates the node information in the node with number id by writing the lower bound lb and the upper b...
const Master & operator=(const Master &rhs)
int breadthFirstSearch(const Sub *s1, const Sub *s2) const
Implements the breadth first search enumeration strategy, i.e., the subproblem with minimum level is ...
void printLP(bool on)
Turns the output of the linear program in every iteration on or off.
Definition master.h:830
PRIMALBOUNDMODE pbMode() const
Returns the mode of the primal bound initialization.
Definition master.h:710
double upperBound() const
Returns the value of the global upper bound.
Definition master.h:1531
bool check() const
Can be used to control the correctness of the optimization if the value of the optimum solution has b...
bool guaranteed() const
Can be used to check if the guarantee requirements are fulfilled.
const OptSense * optSense() const
Returns a pointer to the object holding the optimization sense of the problem.
Definition master.h:443
void showAverageCutDistance(bool on)
Turns the output of the average distance of the added cuts from the fractional solution on or off.
Definition master.h:936
void treeInterfacePaintNode(int id, int color) const
Assigns the color to the subproblem sub in the Tree Interface.
std::ostream * treeStream_
A pointer to the log stream for the VBC-Tool.
Definition master.h:1350
const ogdf::StopwatchCPU * improveTime() const
Returns a pointer to the timer measuring the cpu time spent in the heuristics for the computation of ...
Definition master.h:498
void vbcLog(VBCMODE mode)
Changes the mode of output for the Vbc-Tool to mode.
Definition master.h:948
int nSub_
The number of generated subproblems.
Definition master.h:1494
void maxIterations(int max)
Changes the default value for the maximal number of iterations of the optimization of a subproblem.
Definition master.h:887
int maxVarAdd_
The maximal number of added variables per iteration of the column generation algorithm.
Definition master.h:1423
double dualBound() const
Returns the value of the dual bound.
Definition master.h:294
int conElimAge() const
Returns the age for the elimination of constraints.
Definition master.h:798
void pbMode(PRIMALBOUNDMODE mode)
Sets the mode of the primal bound initialization to mode.
Definition master.h:716
virtual void initializeOptimization()
The default implementation of initializeOptimization() does nothing.
Definition master.h:1131
bool solveApprox() const
True, if an approximative solver should be used.
Definition master.h:483
VBCMODE vbcLog() const
Returns the mode of output for the Vbc-Tool.
Definition master.h:939
int nLp() const
Returns the number of optimized linear programs (only LP-relaxations).
Definition master.h:510
bool solveApprox_
If true, then an approximative solver is used to solve linear programs.
Definition master.h:1341
void countLp()
Increments the counter for linear programs and should be called in each optimization call of the LP-r...
Definition master.h:1234
int64_t maxCowTime_
The maximal available wall-clock time.
Definition master.h:1374
int maxLevel_
The maximal level in enumeration tree.
Definition master.h:1362
void newSub(int level)
Registers a new subproblem which is on level level in enumeration tree.
int pricingFreq() const
Returns the number of linear programs being solved between two additional pricing steps.
Definition master.h:726
int highestLevel() const
Returns the highest level in the tree which has been reached during the implicit enumeration.
Definition master.h:513
void eliminateFixedSet(bool turnOn)
Turns the elimination of fixed and set variables on or off.
Definition master.h:900
int nSubSelected_
The number of subproblems already selected from the list of open subproblems.
Definition master.h:1344
ogdf::StopwatchCPU separationTime_
The timer for the cpu time spent in the separation.
Definition master.h:1482
STATUS status() const
Returns the status of the Master.
Definition master.h:474
STATUS optimize()
Performs the optimization by branch-and-bound.
int nNewRoot_
The number of changes of the root of the remaining branch-and-bound tree.
Definition master.h:1518
int maxConAdd_
The maximal number of added constraints per iteration of the cutting plane algorithm.
Definition master.h:1417
PRIMALBOUNDMODE
This enumeration provides various methods for the initialization of the primal bound.
Definition master.h:139
@ Optimum
The primal bound is initialized with the value of the optimum solution.
Definition master.h:142
int tailOffNLp() const
Returns the number of linear programs considered in the tailing off analysis.
Definition master.h:647
ENUMSTRAT
The enumeration defining the different enumeration strategies for the branch and bound algorithm.
Definition master.h:104
@ DepthFirst
Depth-first search, i.e., select the subproblem with maximal level in the enumeration tree.
Definition master.h:109
@ BreadthFirst
Breadth-first search, i.e., select the subproblem with minimal level in the enumeration tree.
Definition master.h:108
const ogdf::StopwatchCPU * branchingTime() const
Returns a pointer to the timer measuring the cpu time spent in finding and selecting the branching ru...
Definition master.h:504
int depthFirstSearch(const Sub *s1, const Sub *s2) const
Implements the depth first search enumeration strategy, i.e., the subproblem with maximum level is se...
void initializeOptSense(OptSense::SENSE sense)
Can be used to initialize the sense of the optimization in derived classes, if this has not been alre...
Definition master.h:1024
VBCMODE
This enumeration defines what kind of output can be generated for the VBCTOOL.
Definition master.h:193
@ NoVbc
No output for the tree interface.
Definition master.h:194
@ File
Output for the tree interface is written to a file.
Definition master.h:195
bool pricing_
If true, then variables are generated in the optimization.
Definition master.h:1338
void tailOffNLp(int n)
Sets the number of linear programs considered in the tailing off analysis to n.
Definition master.h:656
ogdf::StopwatchCPU totalTime_
The timer for the total cpu time for the optimization.
Definition master.h:1474
int nBranchingVariableCandidates() const
Returns the number of variables that should be tested for the selection of the branching variable.
Definition master.h:545
int64_t maxCpuTime_
The maximal available cpu time.
Definition master.h:1371
int skipFactor_
The frequency constraints or variables are generated depending on the skipping mode.
Definition master.h:1402
bool printLP_
If true, then the linear program is output every iteration.
Definition master.h:1414
string maxCowTimeAsString() const
Returns the maximal wall-clock time (as string hh:mm:ss) which can be used by the optimization.
double varElimEps() const
Returns the zero tolerance for the elimination of variables by the reduced cost criterion.
Definition master.h:780
string optimumFileName_
The name of a file storing a list of optimum solutions of problem instances.
Definition master.h:1441
void maxCowTime(const string &t)
Sets the maximally allowed wall-clock time for the optimization to t.
Sub * rRoot() const
Definition master.h:471
StandardPool< Variable, Constraint > * varPool() const
Returns a pointer to the default pool storing the variables.
Definition master.h:458
BRANCHINGSTRAT branchingStrategy() const
Returns the branching strategy.
Definition master.h:525
double conElimEps_
The tolerance for the elimination of constraints by the mode NonBinding/.
Definition master.h:1456
ogdf::StopwatchCPU pricingTime_
The timer for the cpu time spent in pricing.
Definition master.h:1488
virtual int enumerationStrategy(const Sub *s1, const Sub *s2)
Analyzes the enumeration strategy set in the parameter file .abacus and calls the corresponding compa...
bool objInteger() const
If true then we assume that all feasible solutions have integral objective function values.
Definition master.h:638
void objInteger(bool b)
Sets the assumption that the objective function values of all feasible solutions are integer.
Definition master.h:644
int nRemVars_
The total number of removed variables.
Definition master.h:1515
void treeInterfaceLowerBound(double lb) const
Passes the new lower bound lb to the Tree Interface.
void printGuarantee() const
Writes the guarantee nicely formated on the output stream associated with this object.
int skipFactor() const
Returns the frequency of subproblems in which constraints or variables should be generated.
Definition master.h:735
OSISOLVER defaultLpSolver_
The default LP-Solver.
Definition master.h:1308
void maxCpuTime(int64_t seconds)
Sets the maximally allowed cpu time to seconds.
Definition master.h:617
virtual void initializePools(ArrayBuffer< Constraint * > &constraints, ArrayBuffer< Constraint * > &cuts, ArrayBuffer< Variable * > &variables, int varPoolSize, int cutPoolSize, bool dynamicCutPool=false)
Is overloaded such that also a first set of cutting planes can be inserted into the cutting plane poo...
int maxConAdd() const
Returns the maximal number of constraints which should be added in every iteration of the cutting pla...
Definition master.h:833
bool showAverageCutDistance() const
Definition master.h:930
void addCons(int n)
Increments the counter for the total number of added constraints by n.
Definition master.h:1240
void printParameters() const
Writes all parameters of the class Master together with their values to the global output stream.
void _outputLpStatistics() const
Prints the LP solver specific statistics.
const ogdf::StopwatchWallClock * totalCowTime() const
Returns a pointer to the timer measuring the total wall clock time.
Definition master.h:480
int varElimAge_
The number of iterations an elimination criterion must be satisfied until a variable can be removed.
Definition master.h:1465
int nAddVars_
The total number of added variables.
Definition master.h:1512
void treeInterfaceUpperBound(double ub) const
Passes the new upper bound ub to the Tree Interface.
void maxVarBuffered(int max)
Changes the maximal number of variables that are buffered in an iteration of the subproblem optimizat...
Definition master.h:872
int nSub() const
returns the number of generated subproblems.
Definition master.h:507
bool eliminateFixedSet() const
Definition master.h:893
virtual void initializeParameters()
Is only a dummy.
Definition master.h:1115
bool cutting_
If true, then constraints are generated in the optimization.
Definition master.h:1335
void maxCpuTime(const string &t)
Sets the maximally allowed cpu time for the optimization to t.
int dbThreshold() const
Returns the number of optimizations of a subproblem until sons are created.
Definition master.h:694
VARELIMMODE varElimMode_
The way variables are automatically eliminated in the column generation algorithm.
Definition master.h:1453
void newRootReOptimize(bool on)
Turns the reoptimization of new root nodes of the remaining branch and bound tree on or off.
Definition master.h:913
double rootDualBound_
The best known dual bound at the end of the optimization of the root node.
Definition master.h:1329
OSISOLVER defaultLpSolver() const
returns the Lp Solver.
Definition master.h:534
string maxCpuTimeAsString() const
Returns the maximal cpu time (as string hh:mm:ss) which can be used by the optimization.
OpenSub * openSub_
The set of open subproblems.
Definition master.h:1290
int nAddCons_
The total number of added constraints.
Definition master.h:1506
bool readParamFromFile_
Definition master.h:1278
int dbThreshold_
The number of optimizations of an Sub until branching is performed.
Definition master.h:1386
virtual void output() const
Does nothing but can be redefined in derived classes for output before the timing statistics.
Definition master.h:424
SKIPPINGMODE skippingMode() const
Returns the skipping strategy.
Definition master.h:750
SKIPPINGMODE skippingMode_
Either constraints are generated only every skipFactor_ subproblem (SkipByNode) only every skipFactor...
Definition master.h:1408
void requiredGuarantee(double g)
Changes the guarantee specification tp g.
const string & problemName() const
Returns the name of the instance being optimized (as specified in the constructor of this class).
Definition master.h:477
virtual Sub * firstSub()=0
Should return a pointer to the first subproblem of the optimization, i.e., the root node of the enume...
int nFixed_
The total number of fixed variables.
Definition master.h:1503
bool fixSetByRedCost_
If true, then variables are fixed and set by reduced cost criteria.
Definition master.h:1411
void skippingMode(SKIPPINGMODE mode)
Sets the skipping strategy to mode.
Definition master.h:747
virtual void terminateOptimization()
The default implementation of terminateOptimization() does nothing.
Definition master.h:1139
SKIPPINGMODE
The way nodes are skipped for the generation of cuts.
Definition master.h:154
void _createLpMasters()
void _printLpParameters() const
Prints the LP solver specific parameters.
Sub * root() const
Can be used to access the root node of the branch-and-bound tree.
Definition master.h:464
Maintains open subproblems.
Definition opensub.h:50
Sense of optimization.
Definition optsense.h:45
SENSE
The enumeration defining the sense of optimization.
Definition optsense.h:49
bool max() const
Returns true if it is maximization problem,, false otherwise.
Definition optsense.h:91
Standard pools.
The subproblem.
Definition sub.h:69
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition ArrayBuffer.h:64
Implements a stopwatch measuring CPU time.
Definition Stopwatch.h:157
Implements a stopwatch measuring wall-clock time.
Definition Stopwatch.h:183
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF dynamic library (shared object / DLL),...
Definition config.h:117
global.
hash table.
sense of optimization.