Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

abacus::Master Class Referenceabstract

The master of the optimization. More...

#include <ogdf/lib/abacus/master.h>

+ Inheritance diagram for abacus::Master:

Public Types

enum  BRANCHINGSTRAT { CloseHalf, CloseHalfExpensive }
 This enumeration defines the two currently implemented branching variable selection strategies. More...
 
enum  CONELIMMODE { NoConElim, NonBinding, Basic }
 This enumeration defines the ways for automatic constraint elimination during the cutting plane phase. More...
 
enum  ENUMSTRAT { BestFirst, BreadthFirst, DepthFirst, DiveAndBest }
 The enumeration defining the different enumeration strategies for the branch and bound algorithm. More...
 
enum  OSISOLVER { Cbc, Clp, CPLEX, DyLP, FortMP, GLPK, MOSEK, OSL, SoPlex, SYMPHONY, XPRESS_MP, Gurobi, Csdp }
 This enumeration defines which solvers can be used to solve the LP-relaxations. More...
 
enum  PRIMALBOUNDMODE { NoPrimalBound, Optimum, OptimumOne }
 This enumeration provides various methods for the initialization of the primal bound. More...
 
enum  SKIPPINGMODE { SkipByNode, SkipByLevel }
 The way nodes are skipped for the generation of cuts. More...
 
enum  STATUS { Optimal, Error, OutOfMemory, Unprocessed, Processing, Guaranteed, MaxLevel, MaxCpuTime, MaxNSub, MaxCowTime, ExceptionFathom }
 The various statuses of the optimization process. More...
 
enum  VARELIMMODE { NoVarElim, ReducedCost }
 This enumeration defines the ways for automatic variable elimination during the column generation algorithm. More...
 
enum  VBCMODE { NoVbc, File, Pipe }
 This enumeration defines what kind of output can be generated for the VBCTOOL. More...
 

Public Member Functions

 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. More...
 
virtual ~Master ()
 The destructor. More...
 
STATUS optimize ()
 Performs the optimization by branch-and-bound. More...
 
- Public Member Functions inherited from abacus::AbacusGlobal
 AbacusGlobal (double eps=1.0e-4, double machineEps=1.0e-7, double infinity=1.0e32)
 The constructor. More...
 
virtual ~AbacusGlobal ()
 The destructor. More...
 
void assignParameter (bool &param, const char *name) const
 See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...
 
void assignParameter (bool &param, const char *name, bool defVal) const
 See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...
 
void assignParameter (char &param, const char *name, const char *feasible, char defVal) const
 See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...
 
void assignParameter (char &param, const char *name, const char *feasible=nullptr) const
 See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...
 
void assignParameter (double &param, const char *name, double minVal, double maxVal) const
 See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...
 
void assignParameter (double &param, const char *name, double minVal, double maxVal, double defVal) const
 See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...
 
void assignParameter (int &param, const char *name, int minVal, int maxVal) const
 Searches for parameter name in the parameter table and returns its value in param. More...
 
void assignParameter (int &param, const char *name, int minVal, int maxVal, int defVal) const
 See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...
 
void assignParameter (string &param, const char *name, unsigned nFeasible, const char *feasible[], const char *defVal) const
 See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...
 
void assignParameter (string &param, const char *name, unsigned nFeasible=0, const char *feasible[]=nullptr) const
 See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...
 
void assignParameter (unsigned &param, const char *name, unsigned minVal, unsigned maxVal) const
 See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...
 
void assignParameter (unsigned &param, const char *name, unsigned minVal, unsigned maxVal, unsigned defVal) const
 See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...
 
double eps () const
 Returns the zero tolerance. More...
 
void eps (double e)
 Sets the zero tolerance to e. More...
 
bool equal (double x, double y) const
 Returns whether the absolute difference between x and y is less than the machine dependent zero tolerance. More...
 
int findParameter (const char *name, const char *feasible) const
 See AbacusGlobal::findParameter(const char *name, unsigned nFeasible, const int *feasible) for description. More...
 
int findParameter (const char *name, unsigned nFeasible, const char *feasible[]) const
 See AbacusGlobal::findParameter(const char *name, unsigned nFeasible, const int *feasible) for description. More...
 
int findParameter (const char *name, unsigned nFeasible, const int *feasible) const
 Searches for parameter name in the parameter table. More...
 
int getParameter (const char *name, bool &param) const
 
int getParameter (const char *name, char &param) const
 
int getParameter (const char *name, double &param) const
 
int getParameter (const char *name, int &param) const
 Searches for parameter name in the parameter table and returns its value in param. More...
 
int getParameter (const char *name, string &param) const
 
int getParameter (const char *name, unsigned int &param) const
 
double infinity () const
 Provides a floating point value of "infinite" size. More...
 
void infinity (double x)
 Sets the "infinite value" to x. More...
 
void insertParameter (const char *name, const char *value)
 Inserts parameter name with value value into the parameter table. More...
 
bool isInfinity (double x) const
 Returns true if x is regarded as "infinite" large, false otherwise. More...
 
bool isInteger (double x) const
 Returns whether the value x differs at most by the machine dependent zero tolerance from an integer value. More...
 
bool isInteger (double x, double eps) const
 Returns whether the value x differs at most by eps from an integer value. More...
 
bool isMinusInfinity (double x) const
 Returns true if x is regarded as infinite small, false otherwise. More...
 
double machineEps () const
 Provides a machine dependent zero tolerance. More...
 
void machineEps (double e)
 Sets the machine dependent zero tolerance to e. More...
 
void readParameters (const string &fileName)
 Opens the parameter file fileName, reads all parameters, and inserts them in the parameter table. More...
 
- Public Member Functions inherited from abacus::AbacusRoot
virtual ~AbacusRoot ()
 The destructor. More...
 

Static Public Attributes

static const char * BRANCHINGSTRAT_ []
 Literal values for the enumerators of the corresponding enumeration type. More...
 
static const char * CONELIMMODE_ []
 Literal values for the enumerators of the corresponding enumeration type. More...
 
static const char * ENUMSTRAT_ []
 Literal values for the enumerators of the corresponding enumeration type. More...
 
static const char * OSISOLVER_ []
 Array for the literal values for possible Osi solvers. More...
 
static const char * PRIMALBOUNDMODE_ []
 Literal values for the enumerators of the corresponding enumeration type. More...
 
static const char * SKIPPINGMODE_ []
 Literal values for the enumerators of the corresponding enumeration type. More...
 
static const char * STATUS_ []
 Literal values for the enumerators of the corresponding enumeration type. More...
 
static const char * VARELIMMODE_ []
 Literal values for the enumerators of the corresponding enumeration type. More...
 
static const char * VBCMODE_ []
 Literal values for the enumerators of the corresponding enumeration type. More...
 

Friends

class FixCand
 
class Sub
 

Bounds

In order to embed both minimization and maximization problems in this system we work internally with primal bounds, i.e., a value which is worse than the best known solution (often a value of a feasible solution), and dual bounds, i.e., a bound which is better than the best known solution.

Primal and dual bounds are then interpreted as lower or upper bounds according to the sense of the optimization.

string problemName_
 The name of the optimized problem. More...
 
bool readParamFromFile_
 
OptSense optSense_
 The sense of the objective function. More...
 
Subroot_
 The root node of the enumeration tree. More...
 
SubrRoot_
 The root node of the remaining enumeration tree. More...
 
OpenSubopenSub_
 The set of open subproblems. More...
 
Historyhistory_
 The solution history. More...
 
ENUMSTRAT enumerationStrategy_
 The enumeration strategy. More...
 
BRANCHINGSTRAT branchingStrategy_
 The branching strategy. More...
 
int nBranchingVariableCandidates_
 The number of candidates that are evaluated for branching on variables. More...
 
int nStrongBranchingIterations_
 The number of simplex iterations that are performed when testing a branching variable candidate within strong branching. More...
 
OSISOLVER defaultLpSolver_
 The default LP-Solver. More...
 
LpMasterOsilpMasterOsi_
 
StandardPool< Constraint, Variable > * conPool_
 The default pool with the constraints of the problem formulation. More...
 
StandardPool< Constraint, Variable > * cutPool_
 The default pool of dynamically generated constraints. More...
 
StandardPool< Variable, Constraint > * varPool_
 The default pool with the variables of the problem formulation. More...
 
double primalBound_
 The best known primal bound. More...
 
double dualBound_
 The best known dual bound. More...
 
double rootDualBound_
 The best known dual bound at the end of the optimization of the root node. More...
 
FixCandfixCand_
 The variables which are candidates for being fixed. More...
 
bool cutting_
 If true, then constraints are generated in the optimization. More...
 
bool pricing_
 If true, then variables are generated in the optimization. More...
 
bool solveApprox_
 If true, then an approximative solver is used to solve linear programs. More...
 
int nSubSelected_
 The number of subproblems already selected from the list of open subproblems. More...
 
VBCMODE VbcLog_
 Ouput for the Tree Interface is generated depending on the value of this variable. More...
 
std::ostream * treeStream_
 A pointer to the log stream for the VBC-Tool. More...
 
double requiredGuarantee_
 The guarantee in percent which should be reached when the optimization stops. More...
 
int maxLevel_
 The maximal level in enumeration tree. More...
 
int maxNSub_
 The maximal number of subproblems to be processed. More...
 
int64_t maxCpuTime_
 The maximal available cpu time. More...
 
int64_t maxCowTime_
 The maximal available wall-clock time. More...
 
bool objInteger_
 true, if all objective function values of feasible solutions are assumed to be integer. More...
 
int tailOffNLp_
 The number of LP-iterations for the tailing off analysis. More...
 
double tailOffPercent_
 The minimal change of the LP-value on the tailing off analysis. More...
 
int dbThreshold_
 The number of optimizations of an Sub until branching is performed. More...
 
int minDormantRounds_
 The minimal number of rounds, i.e., number of subproblem optimizations, a subproblem is dormant, i.e., it is not selected from the set of open subproblem if its status is Dormant, if possible. More...
 
PRIMALBOUNDMODE pbMode_
 The mode of the primal bound initialization. More...
 
int pricingFreq_
 The number of solved LPs between two additional pricing steps. More...
 
int skipFactor_
 The frequency constraints or variables are generated depending on the skipping mode. More...
 
SKIPPINGMODE skippingMode_
 Either constraints are generated only every skipFactor_ subproblem (SkipByNode) only every skipFactor_ level (SkipByLevel). More...
 
bool fixSetByRedCost_
 If true, then variables are fixed and set by reduced cost criteria. More...
 
bool printLP_
 If true, then the linear program is output every iteration. More...
 
int maxConAdd_
 The maximal number of added constraints per iteration of the cutting plane algorithm. More...
 
int maxConBuffered_
 The size of the buffer for generated cutting planes. More...
 
int maxVarAdd_
 The maximal number of added variables per iteration of the column generation algorithm. More...
 
int maxVarBuffered_
 The size of the buffer for generated variables. More...
 
int maxIterations_
 The maximal number of iterations of the cutting plane/column generation algorithm in the subproblem. More...
 
bool eliminateFixedSet_
 If true, then nonbasic fixed and set variables are eliminated. More...
 
bool newRootReOptimize_
 If true, then an already earlier processed node is reoptimized if it becomes the new root of the remaining branch-and-bound tree. More...
 
string optimumFileName_
 The name of a file storing a list of optimum solutions of problem instances. More...
 
bool showAverageCutDistance_
 If true then the average distance of the added cutting planes is output every iteration of the cutting plane algorithm. More...
 
CONELIMMODE conElimMode_
 The way constraints are automatically eliminated in the cutting plane algorithm. More...
 
VARELIMMODE varElimMode_
 The way variables are automatically eliminated in the column generation algorithm. More...
 
double conElimEps_
 The tolerance for the elimination of constraints by the mode NonBinding/. More...
 
double varElimEps_
 The tolerance for the elimination of variables by the mode ReducedCost. More...
 
int conElimAge_
 The number of iterations an elimination criterion must be satisfied until a constraint can be removed. More...
 
int varElimAge_
 The number of iterations an elimination criterion must be satisfied until a variable can be removed. More...
 
STATUS status_
 The current status of the optimization. More...
 
ogdf::StopwatchWallClock totalCowTime_
 The timer for the total elapsed time. More...
 
ogdf::StopwatchCPU totalTime_
 The timer for the total cpu time for the optimization. More...
 
ogdf::StopwatchCPU lpTime_
 The timer for the cpu time spent in the LP-interface. More...
 
ogdf::StopwatchCPU lpSolverTime_
 
ogdf::StopwatchCPU separationTime_
 The timer for the cpu time spent in the separation. More...
 
ogdf::StopwatchCPU improveTime_
 The timer for the cpu time spent in the heuristics for the computation of feasible solutions. More...
 
ogdf::StopwatchCPU pricingTime_
 The timer for the cpu time spent in pricing. More...
 
ogdf::StopwatchCPU branchingTime_
 The timer for the cpu time spent in determining the branching rules. More...
 
int nSub_
 The number of generated subproblems. More...
 
int nLp_
 The number of solved LPs. More...
 
int highestLevel_
 The highest level which has been reached in the enumeration tree. More...
 
int nFixed_
 The total number of fixed variables. More...
 
int nAddCons_
 The total number of added constraints. More...
 
int nRemCons_
 The total number of removed constraints. More...
 
int nAddVars_
 The total number of added variables. More...
 
int nRemVars_
 The total number of removed variables. More...
 
int nNewRoot_
 The number of changes of the root of the remaining branch-and-bound tree. More...
 
double lowerBound () const
 Returns the value of the global lower bound. More...
 
double upperBound () const
 Returns the value of the global upper bound. More...
 
double primalBound () const
 Returns the value of the primal bound. More...
 
void primalBound (double x)
 Sets the primal bound to x and makes a new entry in the solution history. More...
 
double dualBound () const
 Returns the value of the dual bound. More...
 
void dualBound (double x)
 Sets the dual bound to x and makes a new entry in the solution history. More...
 
bool betterDual (double x) const
 Returns true if x is better than the best known dual bound; false otherwise. More...
 
bool primalViolated (double x) const
 Can be used to compare a value with the one of the best known primal bound. More...
 
bool betterPrimal (double x) const
 Can be used to check if a value is better than the best know primal bound. More...
 
double rootDualBound () const
 Returns the dual bound at the root node. More...
 
bool feasibleFound () const
 We use this function, e.g., to adapt the enumeration strategy in the DiveAndBest-Strategy. More...
 
ENUMSTRAT enumerationStrategy () const
 Returns the enumeration strategy. More...
 
void enumerationStrategy (ENUMSTRAT strat)
 Changes the enumeration strategy to strat. More...
 
virtual int enumerationStrategy (const Sub *s1, const Sub *s2)
 Analyzes the enumeration strategy set in the parameter file .abacus and calls the corresponding comparison function for the subproblems s1 and s2. More...
 
bool guaranteed () const
 Can be used to check if the guarantee requirements are fulfilled. More...
 
double guarantee () const
 Can be used to access the guarantee which can be given for the best known feasible solution. More...
 
void printGuarantee () const
 Writes the guarantee nicely formated on the output stream associated with this object. More...
 
bool check () const
 Can be used to control the correctness of the optimization if the value of the optimum solution has been loaded. More...
 
bool knownOptimum (double &optVal) const
 Opens the file specified with the parameter OptimumFileName in the configuration file .abacus and tries to find a line with the name of the problem instance (as specified in the constructor of Master) as first string. More...
 
virtual void output () const
 Does nothing but can be redefined in derived classes for output before the timing statistics. More...
 
bool cutting () const
 
bool pricing () const
 
const OptSenseoptSense () const
 Returns a pointer to the object holding the optimization sense of the problem. More...
 
Historyhistory () const
 Returns a pointer to the object storing the solution history of this branch and cut problem. More...
 
OpenSubopenSub () const
 Returns a pointer to the set of open subproblems. More...
 
StandardPool< Constraint, Variable > * conPool () const
 Returns a pointer to the default pool storing the constraints of the problem formulation. More...
 
StandardPool< Constraint, Variable > * cutPool () const
 Returns a pointer to the default pool for the generated cutting planes. More...
 
StandardPool< Variable, Constraint > * varPool () const
 Returns a pointer to the default pool storing the variables. More...
 
Subroot () const
 Can be used to access the root node of the branch-and-bound tree. More...
 
SubrRoot () const
 
STATUS status () const
 Returns the status of the Master. More...
 
const string & problemName () const
 Returns the name of the instance being optimized (as specified in the constructor of this class). More...
 
const ogdf::StopwatchWallClocktotalCowTime () const
 Returns a pointer to the timer measuring the total wall clock time. More...
 
bool solveApprox () const
 True, if an approximative solver should be used. More...
 
const ogdf::StopwatchCPUtotalTime () const
 returns a pointer to the timer measuring the total cpu time for the optimization. More...
 
const ogdf::StopwatchCPUlpTime () const
 Returns a pointer to the timer measuring the cpu time spent in members of the LP-interface. More...
 
const ogdf::StopwatchCPUlpSolverTime () const
 Return a pointer to the timer measuring the cpu time required by the LP solver. More...
 
const ogdf::StopwatchCPUseparationTime () const
 Returns a pointer to the timer measuring the cpu time spent in the separation of cutting planes. More...
 
const ogdf::StopwatchCPUimproveTime () const
 Returns a pointer to the timer measuring the cpu time spent in the heuristics for the computation of feasible solutions. More...
 
const ogdf::StopwatchCPUpricingTime () const
 Returns a pointer to the timer measuring the cpu time spent in pricing. More...
 
const ogdf::StopwatchCPUbranchingTime () const
 Returns a pointer to the timer measuring the cpu time spent in finding and selecting the branching rules. More...
 
int nSub () const
 returns the number of generated subproblems. More...
 
int nLp () const
 Returns the number of optimized linear programs (only LP-relaxations). More...
 
int highestLevel () const
 Returns the highest level in the tree which has been reached during the implicit enumeration. More...
 
int nNewRoot () const
 Returns the number of root changes of the remaining branch-and-cut tree. More...
 
int nSubSelected () const
 Returns the number of subproblems which have already been selected from the set of open subproblems. More...
 
void printParameters () const
 Writes all parameters of the class Master together with their values to the global output stream. More...
 
BRANCHINGSTRAT branchingStrategy () const
 Returns the branching strategy. More...
 
void branchingStrategy (BRANCHINGSTRAT strat)
 Changes the branching strategy to strat. More...
 
OSISOLVER defaultLpSolver () const
 returns the Lp Solver. More...
 
void defaultLpSolver (OSISOLVER osiSolver)
 Changes the default Lp solver to osiSolver. More...
 
LpMasterOsilpMasterOsi () const
 
int nBranchingVariableCandidates () const
 Returns the number of variables that should be tested for the selection of the branching variable. More...
 
void nBranchingVariableCandidates (int n)
 Sets the number of tested branching variable candidates to n. More...
 
int nStrongBranchingIterations () const
 The number of simplex iterations that are performed when testing candidates for branching variables within strong branching. More...
 
void nStrongBranchingIterations (int n)
 Sets the number of simplex iterations that are performed when testing candidates for branching variables within strong branching. More...
 
double requiredGuarantee () const
 The guarantee specification for the optimization. More...
 
void requiredGuarantee (double g)
 Changes the guarantee specification tp g. More...
 
int maxLevel () const
 Returns the maximal depth up to which the enumeration should be performed. More...
 
void maxLevel (int ml)
 This version of the function maxLevel() changes the maximal enumeration depth. More...
 
int maxNSub () const
 Returns the maximal number of subproblems to be processed. More...
 
void maxNSub (int ml)
 Changes the maximal number of subproblems to ml. More...
 
int64_t maxCpuTime () const
 Returns the maximal cpu time (in seconds) which can be used by the optimization. More...
 
string maxCpuTimeAsString () const
 Returns the maximal cpu time (as string hh:mm:ss) which can be used by the optimization. More...
 
void maxCpuTime (const string &t)
 Sets the maximally allowed cpu time for the optimization to t. More...
 
void maxCpuTime (int64_t seconds)
 Sets the maximally allowed cpu time to seconds. More...
 
void maxCpuTime (int hour, int min, int sec)
 Sets the maximally allowed cpu time for the optimization to hour, min, sec. More...
 
int64_t maxCowTime () const
 Returns the maximal wall-clock time (in seconds) which can be used by the optimization. More...
 
string maxCowTimeAsString () const
 Returns the maximal wall-clock time (as string hh:mm:ss) which can be used by the optimization. More...
 
void maxCowTime (int64_t seconds)
 Sets the maximally allowed wall-clock time to seconds. More...
 
void maxCowTime (const string &t)
 Sets the maximally allowed wall-clock time for the optimization to t. More...
 
bool objInteger () const
 If true then we assume that all feasible solutions have integral objective function values. More...
 
void objInteger (bool b)
 Sets the assumption that the objective function values of all feasible solutions are integer. More...
 
int tailOffNLp () const
 Returns the number of linear programs considered in the tailing off analysis. More...
 
void tailOffNLp (int n)
 Sets the number of linear programs considered in the tailing off analysis to n. More...
 
double tailOffPercent () const
 Returns the minimal change of the dual bound for the tailing off analysis in percent. More...
 
void tailOffPercent (double p)
 Sets the minimal change of the dual bound for the tailing off analysis to p. More...
 
bool delayedBranching (int nOpt) const
 Returns true if the number of optimizations nOpt of a subproblem exceeds the delayed branching threshold, false otherwise. More...
 
void dbThreshold (int threshold)
 Sets the number of optimizations of a subproblem until sons are created in Sub::branching(). More...
 
int dbThreshold () const
 Returns the number of optimizations of a subproblem until sons are created. More...
 
int minDormantRounds () const
 Returns the maximal number of rounds, i.e., number of subproblem optimizations, a subproblem is dormant. More...
 
void minDormantRounds (int nRounds)
 Sets the number of rounds a subproblem should stay dormant to nRounds. More...
 
PRIMALBOUNDMODE pbMode () const
 Returns the mode of the primal bound initialization. More...
 
void pbMode (PRIMALBOUNDMODE mode)
 Sets the mode of the primal bound initialization to mode. More...
 
int pricingFreq () const
 Returns the number of linear programs being solved between two additional pricing steps. More...
 
void pricingFreq (int f)
 Sets the number of linear programs being solved between two additional pricing steps to f. More...
 
int skipFactor () const
 Returns the frequency of subproblems in which constraints or variables should be generated. More...
 
void skipFactor (int f)
 Sets the frequency for constraint and variable generation to f. More...
 
void skippingMode (SKIPPINGMODE mode)
 Sets the skipping strategy to mode. More...
 
SKIPPINGMODE skippingMode () const
 Returns the skipping strategy. More...
 
CONELIMMODE conElimMode () const
 Returns the mode for the elimination of constraints. More...
 
void conElimMode (CONELIMMODE mode)
 Changes the constraint elimination mode to mode. More...
 
VARELIMMODE varElimMode () const
 Returns the mode for the elimination of variables. More...
 
void varElimMode (VARELIMMODE mode)
 Changes the variable elimination mode to mode. More...
 
double conElimEps () const
 Returns the zero tolerance for the elimination of constraints by the slack criterion. More...
 
void conElimEps (double eps)
 Changes the tolerance for the elimination of constraints by the slack criterion to eps. More...
 
double varElimEps () const
 Returns the zero tolerance for the elimination of variables by the reduced cost criterion. More...
 
void varElimEps (double eps)
 Changes the tolerance for the elimination of variables by the reduced cost criterion to eps. More...
 
int varElimAge () const
 Returns the age for the elimination of variables by the reduced cost criterion. More...
 
void varElimAge (int age)
 Changes the age for the elimination of variables by the reduced cost criterion to age. More...
 
int conElimAge () const
 Returns the age for the elimination of constraints. More...
 
void conElimAge (int age)
 Changes the age for the elimination of constraints to age. More...
 
bool fixSetByRedCost () const
 
void fixSetByRedCost (bool on)
 Turns fixing and setting variables by reduced cost on or off. More...
 
bool printLP () const
 
void printLP (bool on)
 Turns the output of the linear program in every iteration on or off. More...
 
int maxConAdd () const
 Returns the maximal number of constraints which should be added in every iteration of the cutting plane algorithm. More...
 
void maxConAdd (int max)
 Sets the maximal number of constraints that are added in an iteration of the cutting plane algorithm. More...
 
int maxConBuffered () const
 Returns the size of the buffer for generated constraints in the cutting plane algorithm. More...
 
void maxConBuffered (int max)
 Changes the maximal number of constraints that are buffered in an iteration of the cutting plane algorithm. More...
 
int maxVarAdd () const
 Returns the maximal number of variables which should be added in the column generation algorithm. More...
 
void maxVarAdd (int max)
 Changes the maximal number of variables that are added in an iteration of the subproblem optimization. More...
 
int maxVarBuffered () const
 Returns the size of the buffer for the variables generated in the column generation algorithm. More...
 
void maxVarBuffered (int max)
 Changes the maximal number of variables that are buffered in an iteration of the subproblem optimization. More...
 
int maxIterations () const
 Returns the maximal number of iterations per subproblem optimization (-1 means no iteration limit). More...
 
void maxIterations (int max)
 Changes the default value for the maximal number of iterations of the optimization of a subproblem. More...
 
bool eliminateFixedSet () const
 
void eliminateFixedSet (bool turnOn)
 Turns the elimination of fixed and set variables on or off. More...
 
bool newRootReOptimize () const
 
void newRootReOptimize (bool on)
 Turns the reoptimization of new root nodes of the remaining branch and bound tree on or off. More...
 
const string & optimumFileName () const
 Returns the name of the file that stores the optimum solutions. More...
 
void optimumFileName (const char *name)
 Changes the name of the file in which the value of the optimum solution is searched. More...
 
bool showAverageCutDistance () const
 
void showAverageCutDistance (bool on)
 Turns the output of the average distance of the added cuts from the fractional solution on or off. More...
 
VBCMODE vbcLog () const
 Returns the mode of output for the Vbc-Tool. More...
 
void vbcLog (VBCMODE mode)
 Changes the mode of output for the Vbc-Tool to mode. More...
 
virtual bool setSolverParameters (OsiSolverInterface *interface, bool solverIsApprox)
 Sets solver specific parameters. More...
 
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. More...
 
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 pool. More...
 
void initializeOptSense (OptSense::SENSE sense)
 Can be used to initialize the sense of the optimization in derived classes, if this has not been already performed when the constructor of Master has been called. More...
 
int bestFirstSearch (const Sub *s1, const Sub *s2) const
 Implements the best first search enumeration. More...
 
virtual int equalSubCompare (const Sub *s1, const Sub *s2) const
 Is called from the function bestFirstSearch() and from the function depthFirstSearch() if the subproblems s1 and s2 have the same priority. More...
 
int depthFirstSearch (const Sub *s1, const Sub *s2) const
 Implements the depth first search enumeration strategy, i.e., the subproblem with maximum level is selected. More...
 
int breadthFirstSearch (const Sub *s1, const Sub *s2) const
 Implements the breadth first search enumeration strategy, i.e., the subproblem with minimum level is selected. More...
 
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 with best-first search. More...
 
virtual void initializeParameters ()
 Is only a dummy. More...
 
virtual SubfirstSub ()=0
 Should return a pointer to the first subproblem of the optimization, i.e., the root node of the enumeration tree. More...
 
virtual void initializeOptimization ()
 The default implementation of initializeOptimization() does nothing. More...
 
virtual void terminateOptimization ()
 The default implementation of terminateOptimization() does nothing. More...
 
virtual void assignParameters ()
 Assigns the parameters that were read from a file to the member variables of the master. More...
 
void _initializeParameters ()
 Reads the parameter-file .abacus. More...
 
void _createLpMasters ()
 
void _deleteLpMasters ()
 
void _initializeLpParameters ()
 
void _setDefaultLpParameters ()
 Initializes the LP solver specific default parameters if they are not read from .abacus. More...
 
void _printLpParameters () const
 Prints the LP solver specific parameters. More...
 
void _outputLpStatistics () const
 Prints the LP solver specific statistics. More...
 
Subselect ()
 Returns a pointer to an open subproblem for further processing. More...
 
int initLP ()
 
void writeTreeInterface (const string &info, bool time=true) const
 Writes the string info to the stream associated with the Tree Interface. More...
 
void treeInterfaceNewNode (Sub *sub) const
 Adds the subproblem sub to the stream storing information for graphical output of the enumeration tree if this logging is turned on. More...
 
void treeInterfacePaintNode (int id, int color) const
 Assigns the color to the subproblem sub in the Tree Interface. More...
 
void treeInterfaceLowerBound (double lb) const
 Passes the new lower bound lb to the Tree Interface. More...
 
void treeInterfaceUpperBound (double ub) const
 Passes the new upper bound ub to the Tree Interface. More...
 
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 bound ub to the node. More...
 
void newSub (int level)
 Registers a new subproblem which is on level level in enumeration tree. More...
 
void countLp ()
 Increments the counter for linear programs and should be called in each optimization call of the LP-relaxation. More...
 
void newFixed (int n)
 Increments the counter of the number of fixed variables by n. More...
 
void addCons (int n)
 Increments the counter for the total number of added constraints by n. More...
 
void removeCons (int n)
 Increments the counter for the total number of removed constraints by n. More...
 
void addVars (int n)
 Increments the counter for the total number of added variables by n. More...
 
void removeVars (int n)
 Increments the counter for the total number of removed variables by n. More...
 
FixCandfixCand () const
 Returns a pointer to the object storing the variables which are candidates for being fixed. More...
 
void rRoot (Sub *newRoot, bool reoptimize)
 Sets the root of the remaining branch-and-cut tree to newRoot. More...
 
void status (STATUS stat)
 Sets the status of the Master. More...
 
void rootDualBound (double x)
 Updates the final dual bound of the root node. More...
 
void theFuture ()
 
 Master (const Master &rhs)
 
const Masteroperator= (const Master &rhs)
 

Additional Inherited Members

- Static Public Member Functions inherited from abacus::AbacusRoot
static bool ascii2bool (const string &str)
 Converts the string str to a boolean value. More...
 
static bool endsWith (const string &str, const string &end)
 Returns true if str ends with end, false otherwise. More...
 
static double fracPart (double x)
 Returns the absolute value of the fractional part of x. More...
 
static const char * onOff (bool value)
 Converts a boolean variable to the strings "on" and "off". More...
 

Detailed Description

The master of the optimization.

As the name already indicates, the class Master is the central object of the framework. The most important tasks of the class Master is the management of the implicit enumeration. Moreover, it provides already default implementations for constraints, cutting planes, and variables pools. The class Master also stores various parameter settings and compiles statistics about the solution process.

The class Master is an abstract class from which a problem specific master has to be derived.

Definition at line 69 of file master.h.

Member Enumeration Documentation

◆ BRANCHINGSTRAT

This enumeration defines the two currently implemented branching variable selection strategies.

Enumerator
CloseHalf 

Selects the variable with fractional part closest to 0.5.

CloseHalfExpensive 

Selects the variable with fractional part close to 0.5 (within some interval around 0.5) and has highest absolute objective function coefficient.

Definition at line 120 of file master.h.

◆ CONELIMMODE

This enumeration defines the ways for automatic constraint elimination during the cutting plane phase.

Enumerator
NoConElim 

No constraints are eliminated.

NonBinding 

Nonbinding constraints are eliminated.

Basic 

Constraints with basic slack variable are eliminated.

Definition at line 166 of file master.h.

◆ ENUMSTRAT

The enumeration defining the different enumeration strategies for the branch and bound algorithm.

Enumerator
BestFirst 

Best-first search, i.e., select the subproblem with best dual bound, i.e., the subproblem having minimal dual bound for a minimization problem, or the subproblem having maximal dual bound for a maximization problem.

BreadthFirst 

Breadth-first search, i.e., select the subproblem with minimal level in the enumeration tree.

DepthFirst 

Depth-first search, i.e., select the subproblem with maximal level in the enumeration tree.

DiveAndBest 

As long as no primal feasible solution is known the next subproblem is selected according to the depth-first search strategy, otherwise the best-first search strategy is applied.

Definition at line 103 of file master.h.

◆ OSISOLVER

This enumeration defines which solvers can be used to solve the LP-relaxations.

These are all solvers supported by OSI, see https://projects.coin-or.org/Osi .

Enumerator
Cbc 
Clp 
CPLEX 
DyLP 
FortMP 
GLPK 
MOSEK 
OSL 
SoPlex 
SYMPHONY 
XPRESS_MP 
Gurobi 
Csdp 

Definition at line 209 of file master.h.

◆ PRIMALBOUNDMODE

This enumeration provides various methods for the initialization of the primal bound.

The modes OptimalPrimalBound and OptimalOnePrimalBound can be useful in the testing phase. For these modes the value of an optimum solution must stored in the file given by the parameter OptimumFileName in the parameter file.

Enumerator
NoPrimalBound 

The primal bound is initialized with \(-\infty\) for maximization problems and \(\infty\) for minimization problems, respectively.

Optimum 

The primal bound is initialized with the value of the optimum solution.

OptimumOne 

The primal bound is initialized with the value of optimum solution minus 1 for maximization problems and with the value of the optimum solution plus one for minimization problems, respectively.

Definition at line 138 of file master.h.

◆ SKIPPINGMODE

The way nodes are skipped for the generation of cuts.

Enumerator
SkipByNode 

Cuts are only generated in every SkipFactor subproblem, where SkipFactor can be controlled with the parameter file .abacus.

SkipByLevel 

Cuts are only generated in every SkipFactor level of the enumeration tree.

Definition at line 153 of file master.h.

◆ STATUS

The various statuses of the optimization process.

Enumerator
Optimal 

The optimization terminated with an error and without reaching one of the resource limits.

If there is a feasible solution then the optimal solution has been computed.

Error 

An error occurred during the optimization process.

OutOfMemory 
Unprocessed 

The initial status, before the optimization starts.

Processing 

The status while the optimization is performed.

Guaranteed 

If the optimal solution is not determined but the required guarantee is reached, then the status is Guaranteed.

MaxLevel 

The status, if subproblems are ignored since the maximum enumeration level is exceeded.

MaxCpuTime 

The status, if the optimization terminates since the maximum cpu time is exceeded.

MaxNSub 

The status, if the optimization terminates since the maximum number of subproblems is reached.

MaxCowTime 

The status, if the optimization terminates since the maximum wall-clock time is exceeded.

ExceptionFathom 

The status, if at least one subproblem has been fathomed according to a problem specific criteria determined in the function Sub::exceptionFathom().

Definition at line 77 of file master.h.

◆ VARELIMMODE

This enumeration defines the ways for automatic variable elimination during the column generation algorithm.

Enumerator
NoVarElim 

No variables are eliminated.

ReducedCost 

Variables with high absolute reduced costs are eliminated.

Definition at line 180 of file master.h.

◆ VBCMODE

This enumeration defines what kind of output can be generated for the VBCTOOL.

Enumerator
NoVbc 

No output for the tree interface.

File 

Output for the tree interface is written to a file.

Pipe 

Output for the tree interface is pipeed to the standard output.

Definition at line 192 of file master.h.

Constructor & Destructor Documentation

◆ Master() [1/2]

abacus::Master::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.

The members primalBound_ and dualBound_ stay uninitialized since this can only be done when the sense of optimization (minimization or maximization) is known. The initialization is performed automatically in the function optimize().

Parameters
problemNameThe name of the problem being solved. Must not be a 0-pointer.
cuttingIf true, then cutting planes can be generated if the function Sub::separate() is redefined.
pricingIf true, then inactive variables are priced in, if the function Sub::pricing() is redefined.
optSenseThe sense of the optimization. The default value is OptSense::Unknown. If the sense is unknown when this constructor is called, e.g., if it is read from a file in the constructor of the derived class, then it must be initialized in the constructor of the derived class.
epsThe zero-tolerance used within all member functions of objects which have a pointer to this master (default value 1.0e-4).
machineEpsThe machine dependent zero tolerance (default value 1.0e-7).
infinityAll values greater than infinity are regarded as "infinite big", all values less than -infinity are regarded as "infinite small" (default value 1.0e30).
readParamFromFileIf true, then the parameter file .abacus is read, otherwise the parameters are initialized with default values (default true).

◆ ~Master()

virtual abacus::Master::~Master ( )
virtual

The destructor.

Reimplemented in ogdf::MinSteinerTreeDirectedCut< T >::Master.

◆ Master() [2/2]

abacus::Master::Master ( const Master rhs)
private

Member Function Documentation

◆ _createLpMasters()

void abacus::Master::_createLpMasters ( )
private

◆ _deleteLpMasters()

void abacus::Master::_deleteLpMasters ( )
private

◆ _initializeLpParameters()

void abacus::Master::_initializeLpParameters ( )
private

◆ _initializeParameters()

void abacus::Master::_initializeParameters ( )
private

Reads the parameter-file .abacus.

This file is searched in the directory given by the environment variable ABACUS_DIR, then the virtual function initializeParameters() is called which can initialize parameters of derived classes and overwrite parameters of this class.

All parameters are first inserted together with their values in a parameter table in the function readParameters(). If the virtual dummy function initializeParameters() is redefined in a derived class and also reads a parameter file with the function readParameters(), then already inserted parameters can be overwritten.

After all parameters are input we extract with the function assignParameter() all parameters. Problem specific parameters should be extracted in a redefined version of initializeParameters(). extracted from this table

◆ _outputLpStatistics()

void abacus::Master::_outputLpStatistics ( ) const
private

Prints the LP solver specific statistics.

This function is implemented in the file lpif.cc.

◆ _printLpParameters()

void abacus::Master::_printLpParameters ( ) const
private

Prints the LP solver specific parameters.

This function is implemented in the file lpif.cc.

◆ _setDefaultLpParameters()

void abacus::Master::_setDefaultLpParameters ( )
private

Initializes the LP solver specific default parameters if they are not read from .abacus.

This function is implemented in the file lpif.cc.

◆ addCons()

void abacus::Master::addCons ( int  n)
inlineprivate

Increments the counter for the total number of added constraints by n.

Definition at line 1239 of file master.h.

◆ addVars()

void abacus::Master::addVars ( int  n)
inlineprivate

Increments the counter for the total number of added variables by n.

Definition at line 1245 of file master.h.

◆ assignParameters()

virtual void abacus::Master::assignParameters ( )
protectedvirtual

Assigns the parameters that were read from a file to the member variables of the master.

◆ bestFirstSearch()

int abacus::Master::bestFirstSearch ( const Sub s1,
const Sub s2 
) const
protected

Implements the best first search enumeration.

If the bounds of both subproblems are equal, then the subproblems are compared with the function equalSubCompare().

Returns
-1 If subproblem s1 has a worse dual bound than s2, i.e., if it has a smaller dual bound for minimization or a larger dual bound for maximization problems.
1 If subproblem s2 has a worse dual bound than s1.
0 If both subproblems have the same priority in the enumeration strategy.
Parameters
s1A subproblem.
s2A subproblem.

◆ betterDual()

bool abacus::Master::betterDual ( double  x) const

Returns true if x is better than the best known dual bound; false otherwise.

Parameters
xThe value being compared with the best know dual bound.

◆ betterPrimal()

bool abacus::Master::betterPrimal ( double  x) const

Can be used to check if a value is better than the best know primal bound.

Parameters
xThe value compared with the primal bound.
Returns
true If x is better than the best known primal bound, false otherwise.

◆ branchingStrategy() [1/2]

BRANCHINGSTRAT abacus::Master::branchingStrategy ( ) const
inline

Returns the branching strategy.

Definition at line 524 of file master.h.

◆ branchingStrategy() [2/2]

void abacus::Master::branchingStrategy ( BRANCHINGSTRAT  strat)
inline

Changes the branching strategy to strat.

Parameters
stratThe new branching strategy.

Definition at line 530 of file master.h.

◆ branchingTime()

const ogdf::StopwatchCPU* abacus::Master::branchingTime ( ) const
inline

Returns a pointer to the timer measuring the cpu time spent in finding and selecting the branching rules.

Definition at line 503 of file master.h.

◆ breadthFirstSearch()

int abacus::Master::breadthFirstSearch ( const Sub s1,
const Sub s2 
) const
protected

Implements the breadth first search enumeration strategy, i.e., the subproblem with minimum level is selected.

If both subproblems have the same level, the smaller one is the one which has been generated earlier, i.e., the one with the smaller id.

Returns
-1 If subproblem s1 has higher priority,
0 if both subproblems have equal priority,
1 otherwise.
Parameters
s1The first subproblem.
s2The second subproblem.

◆ check()

bool abacus::Master::check ( ) const

Can be used to control the correctness of the optimization if the value of the optimum solution has been loaded.

This is done, if a file storing the optimum value is specified with the parameter OptimumFileName in the configuration file .abacus.

Returns
true If the optimum solution of the problem is known and equals the primal bound, false otherwise.

◆ conElimAge() [1/2]

int abacus::Master::conElimAge ( ) const
inline

Returns the age for the elimination of constraints.

Definition at line 797 of file master.h.

◆ conElimAge() [2/2]

void abacus::Master::conElimAge ( int  age)
inline

Changes the age for the elimination of constraints to age.

Parameters
ageThe new age.

Definition at line 803 of file master.h.

◆ conElimEps() [1/2]

double abacus::Master::conElimEps ( ) const
inline

Returns the zero tolerance for the elimination of constraints by the slack criterion.

Definition at line 770 of file master.h.

◆ conElimEps() [2/2]

void abacus::Master::conElimEps ( double  eps)
inline

Changes the tolerance for the elimination of constraints by the slack criterion to eps.

Parameters
epsThe new tolerance.

Definition at line 776 of file master.h.

◆ conElimMode() [1/2]

CONELIMMODE abacus::Master::conElimMode ( ) const
inline

Returns the mode for the elimination of constraints.

Definition at line 752 of file master.h.

◆ conElimMode() [2/2]

void abacus::Master::conElimMode ( CONELIMMODE  mode)
inline

Changes the constraint elimination mode to mode.

Parameters
modeThe new constraint elimination mode.

Definition at line 758 of file master.h.

◆ conPool()

StandardPool<Constraint, Variable>* abacus::Master::conPool ( ) const
inline

Returns a pointer to the default pool storing the constraints of the problem formulation.

Definition at line 451 of file master.h.

◆ countLp()

void abacus::Master::countLp ( )
inlineprivate

Increments the counter for linear programs and should be called in each optimization call of the LP-relaxation.

Definition at line 1233 of file master.h.

◆ cutPool()

StandardPool<Constraint, Variable>* abacus::Master::cutPool ( ) const
inline

Returns a pointer to the default pool for the generated cutting planes.

Definition at line 454 of file master.h.

◆ cutting()

bool abacus::Master::cutting ( ) const
inline
Returns
true If cutting has been set to true in the call of the constructor of the class Master, i.e., if cutting planes should be generated in the subproblem optimization; false otherwise.

Definition at line 431 of file master.h.

◆ dbThreshold() [1/2]

int abacus::Master::dbThreshold ( ) const
inline

Returns the number of optimizations of a subproblem until sons are created.

For further detatails we refer to dbThreshold(int).

Definition at line 693 of file master.h.

◆ dbThreshold() [2/2]

void abacus::Master::dbThreshold ( int  threshold)
inline

Sets the number of optimizations of a subproblem until sons are created in Sub::branching().

If this value is 0, then a branching step is performed at the end of the subproblem optimization as usually if the subproblem can be fathomed. Otherwise, if this value is strictly positive, the subproblem is put back for a later optimization. This can be advantageous if in the meantime good cutting planes or primal bounds can be generated. The number of times the subproblem is put back without branching is indicated by this value.

Parameters
thresholdThe new value of the delayed branching threshold.

Definition at line 687 of file master.h.

◆ defaultLpSolver() [1/2]

OSISOLVER abacus::Master::defaultLpSolver ( ) const
inline

returns the Lp Solver.

Definition at line 533 of file master.h.

◆ defaultLpSolver() [2/2]

void abacus::Master::defaultLpSolver ( OSISOLVER  osiSolver)
inline

Changes the default Lp solver to osiSolver.

Parameters
osiSolverThe new solver.

Definition at line 539 of file master.h.

◆ delayedBranching()

bool abacus::Master::delayedBranching ( int  nOpt) const

Returns true if the number of optimizations nOpt of a subproblem exceeds the delayed branching threshold, false otherwise.

Parameters
nOptThe number of optimizations of a subproblem.

◆ depthFirstSearch()

int abacus::Master::depthFirstSearch ( const Sub s1,
const Sub s2 
) const
protected

Implements the depth first search enumeration strategy, i.e., the subproblem with maximum level is selected.

If the level of both subproblems are equal, then the subproblems are compared with the function equalSubCompare().

Returns
-1 If subproblem s1 has higher priority,
0 if both subproblems have equal priority,
1 otherwise.
Parameters
s1The first subproblem.
s2The second subproblem.

◆ diveAndBestFirstSearch()

int abacus::Master::diveAndBestFirstSearch ( const Sub s1,
const Sub s2 
) const
protected

Performs depth-first search until a feasible solution is found, then the search process is continued with best-first search.

Returns
-1 If subproblem s1 has higher priority,
0 if both subproblems have equal priority,
1 otherwise.
Parameters
s1The first subproblem.
s2The second subproblem.

◆ dualBound() [1/2]

double abacus::Master::dualBound ( ) const
inline

Returns the value of the dual bound.

I.e., the upperBound() for a maximization problem and the lowerBound() for a minimization problem, respectively.

Definition at line 293 of file master.h.

◆ dualBound() [2/2]

void abacus::Master::dualBound ( double  x)

Sets the dual bound to x and makes a new entry in the solution history.

It is an error if the dual bound gets worse.L

Parameters
xThe new value of the dual bound.

◆ eliminateFixedSet() [1/2]

bool abacus::Master::eliminateFixedSet ( ) const
inline
Returns
true Then we try to eliminate fixed and set variables from the linear program;
false Fixed or set variables are not eliminated.

Definition at line 892 of file master.h.

◆ eliminateFixedSet() [2/2]

void abacus::Master::eliminateFixedSet ( bool  turnOn)
inline

Turns the elimination of fixed and set variables on or off.

Parameters
turnOnThe elimination is turned on if turnOn is true, otherwise it is turned off.

Definition at line 899 of file master.h.

◆ enumerationStrategy() [1/3]

ENUMSTRAT abacus::Master::enumerationStrategy ( ) const
inline

Returns the enumeration strategy.

Definition at line 342 of file master.h.

◆ enumerationStrategy() [2/3]

virtual int abacus::Master::enumerationStrategy ( const Sub s1,
const Sub s2 
)
virtual

Analyzes the enumeration strategy set in the parameter file .abacus and calls the corresponding comparison function for the subproblems s1 and s2.

This function should be redefined for application specific enumeration strategies.

Returns
1 If s1 has higher priority than s2;
-1 if s2 has higher priority it returns -1; and
0 if both subproblems have equal priority.
Parameters
s1A pointer to a subproblem.
s2A pointer to a subproblem.

◆ enumerationStrategy() [3/3]

void abacus::Master::enumerationStrategy ( ENUMSTRAT  strat)
inline

Changes the enumeration strategy to strat.

Parameters
stratThe new enumeration strategy.

Definition at line 348 of file master.h.

◆ equalSubCompare()

virtual int abacus::Master::equalSubCompare ( const Sub s1,
const Sub s2 
) const
protectedvirtual

Is called from the function bestFirstSearch() and from the function depthFirstSearch() if the subproblems s1 and s2 have the same priority.

If both subproblems were generated by setting a binary variable, then that subproblem has higher priority of which the branching variable is set to upper bound.

This function can be redefined to resolve equal subproblems according to problem specific criteria. As the root node is compared with itself and has no branching rule, we have to insert the first line of this function.

Parameters
s1A subproblem.
s2A subproblem.
Returns
0 If both subproblems were not generated by setting a variable, or the branching variable of both subproblems is set to the same bound.
1 If the branching variable of the first subproblem is set to the upper bound.
-1 If the branching variable of the second subproblem is set to the upper bound.

◆ feasibleFound()

bool abacus::Master::feasibleFound ( ) const

We use this function, e.g., to adapt the enumeration strategy in the DiveAndBest-Strategy.

◆ firstSub()

virtual Sub* abacus::Master::firstSub ( )
protectedpure virtual

Should return a pointer to the first subproblem of the optimization, i.e., the root node of the enumeration tree.

This is a pure virtual function since a pointer to a problem specific subproblem should be returned, which is derived from the class Sub.

Implemented in ogdf::MinSteinerTreeDirectedCut< T >::Master, ogdf::cluster_planarity::MaxCPlanarMaster, and ogdf::cluster_planarity::CPlanarityMaster.

◆ fixCand()

FixCand* abacus::Master::fixCand ( ) const
inlineprivate

Returns a pointer to the object storing the variables which are candidates for being fixed.

Definition at line 1251 of file master.h.

◆ fixSetByRedCost() [1/2]

bool abacus::Master::fixSetByRedCost ( ) const
inline
Returns
true Then variables are fixed and set by reduced cost criteria.
false Then no variables are fixed or set by reduced cost criteria.

Definition at line 809 of file master.h.

◆ fixSetByRedCost() [2/2]

void abacus::Master::fixSetByRedCost ( bool  on)
inline

Turns fixing and setting variables by reduced cost on or off.

Parameters
onIf true, then variable fixing and setting by reduced cost is turned on. Otherwise it is turned of.

Definition at line 816 of file master.h.

◆ guarantee()

double abacus::Master::guarantee ( ) const

Can be used to access the guarantee which can be given for the best known feasible solution.

It is an error to call this function if the lower bound is zero, but the upper bound is nonzero.

Returns
The guarantee for best known feasible solution in percent.

◆ guaranteed()

bool abacus::Master::guaranteed ( ) const

Can be used to check if the guarantee requirements are fulfilled.

I.e., the difference between upper bound and the lower bound in respect to the lowerBound is less than this guarantee value in percent.

If the lower bound is zero, but the upper bound is nonzero, we cannot give any guarantee.

Warning
A guarantee for a solution can only be given if the pricing problem is solved exactly or no column generation is performed at all.
Returns
true If the guarantee requirements are fulfilled, false otherwise.

◆ highestLevel()

int abacus::Master::highestLevel ( ) const
inline

Returns the highest level in the tree which has been reached during the implicit enumeration.

Definition at line 512 of file master.h.

◆ history()

History* abacus::Master::history ( ) const
inline

Returns a pointer to the object storing the solution history of this branch and cut problem.

Definition at line 445 of file master.h.

◆ improveTime()

const ogdf::StopwatchCPU* abacus::Master::improveTime ( ) const
inline

Returns a pointer to the timer measuring the cpu time spent in the heuristics for the computation of feasible solutions.

Definition at line 497 of file master.h.

◆ initializeOptimization()

virtual void abacus::Master::initializeOptimization ( )
inlineprotectedvirtual

The default implementation of initializeOptimization() does nothing.

This virtual function can be used as an entrance point to perform some initializations after optimize() is called.

Reimplemented in ogdf::cluster_planarity::CP_MasterBase, ogdf::MinSteinerTreeDirectedCut< T >::Master, ogdf::cluster_planarity::CPlanarityMaster, and ogdf::cluster_planarity::MaxCPlanarMaster.

Definition at line 1130 of file master.h.

◆ initializeOptSense()

void abacus::Master::initializeOptSense ( OptSense::SENSE  sense)
inlineprotected

Can be used to initialize the sense of the optimization in derived classes, if this has not been already performed when the constructor of Master has been called.

Parameters
senseThe sense of the optimization (OptSense::Min or OptSense::Max).

Definition at line 1023 of file master.h.

◆ initializeParameters()

virtual void abacus::Master::initializeParameters ( )
inlineprotectedvirtual

Is only a dummy.

This function can be used to initialize parameters of derived classes and to overwrite parameters read from the file .abacus by the function _initializeParameters().

Reimplemented in ogdf::MinSteinerTreeDirectedCut< T >::Master.

Definition at line 1114 of file master.h.

◆ initializePools() [1/2]

virtual void abacus::Master::initializePools ( ArrayBuffer< Constraint * > &  constraints,
ArrayBuffer< Constraint * > &  cuts,
ArrayBuffer< Variable * > &  variables,
int  varPoolSize,
int  cutPoolSize,
bool  dynamicCutPool = false 
)
protectedvirtual

Is overloaded such that also a first set of cutting planes can be inserted into the cutting plane pool.

Parameters
constraintsThe constraints of the problem formulation are inserted in the constraint pool. The size of the constraint pool equals the number of constraints.
cutsThe constraints that are inserted in the cutting plane pool. The number of constraints in the buffer must be less or equal than the size of the cutting plane pool cutPoolSize.
variablesThe variables of the problem formulation are inserted in the variable pool.
varPoolSizeThe size of the pool for the variables. If more variables are added the variable pool is automatically reallocated.
cutPoolSizeThe size of the pool for cutting planes.
dynamicCutPoolIf this argument is true, then the cut is automatically reallocated if more constraints are inserted than cutPoolSize. Otherwise, non-active constraints are removed if the pool becomes full. The default value is false.

◆ initializePools() [2/2]

virtual void abacus::Master::initializePools ( ArrayBuffer< Constraint * > &  constraints,
ArrayBuffer< Variable * > &  variables,
int  varPoolSize,
int  cutPoolSize,
bool  dynamicCutPool = false 
)
protectedvirtual

Sets up the default pools for variables, constraints, and cutting planes.

Parameters
constraintsThe constraints of the problem formulation are inserted in the constraint pool. The size of the constraint pool equals the number of constraints.
variablesThe variables of the problem formulation are inserted in the variable pool.
varPoolSizeThe size of the pool for the variables. If more variables are added the variable pool is automatically reallocated.
cutPoolSizeThe size of the pool for cutting planes.
dynamicCutPoolIf this argument is true, then the cut is automatically reallocated if more constraints are inserted than cutPoolSize. Otherwise, non-active constraints are removed if the pool becomes full. The default value is false.

◆ initLP()

int abacus::Master::initLP ( )
private

◆ knownOptimum()

bool abacus::Master::knownOptimum ( double &  optVal) const

Opens the file specified with the parameter OptimumFileName in the configuration file .abacus and tries to find a line with the name of the problem instance (as specified in the constructor of Master) as first string.

Parameters
optValIf the return value is true, then optVal holds the optimum value found in the line with the name of the problem instance as first string. Otherwise, optVal is undefined.
Returns
true If a line with problemName_ has been found, false otherwise.

◆ lowerBound()

double abacus::Master::lowerBound ( ) const
inline

Returns the value of the global lower bound.

Definition at line 1524 of file master.h.

◆ lpMasterOsi()

LpMasterOsi* abacus::Master::lpMasterOsi ( ) const
inline

Definition at line 541 of file master.h.

◆ lpSolverTime()

const ogdf::StopwatchCPU* abacus::Master::lpSolverTime ( ) const
inline

Return a pointer to the timer measuring the cpu time required by the LP solver.

Definition at line 491 of file master.h.

◆ lpTime()

const ogdf::StopwatchCPU* abacus::Master::lpTime ( ) const
inline

Returns a pointer to the timer measuring the cpu time spent in members of the LP-interface.

Definition at line 488 of file master.h.

◆ maxConAdd() [1/2]

int abacus::Master::maxConAdd ( ) const
inline

Returns the maximal number of constraints which should be added in every iteration of the cutting plane algorithm.

Definition at line 832 of file master.h.

◆ maxConAdd() [2/2]

void abacus::Master::maxConAdd ( int  max)
inline

Sets the maximal number of constraints that are added in an iteration of the cutting plane algorithm.

Definition at line 838 of file master.h.

◆ maxConBuffered() [1/2]

int abacus::Master::maxConBuffered ( ) const
inline

Returns the size of the buffer for generated constraints in the cutting plane algorithm.

Definition at line 841 of file master.h.

◆ maxConBuffered() [2/2]

void abacus::Master::maxConBuffered ( int  max)
inline

Changes the maximal number of constraints that are buffered in an iteration of the cutting plane algorithm.

Note
This function changes only the default value for subproblems that are activated after its call.
Parameters
maxThe new maximal number of buffered constraints.

Definition at line 850 of file master.h.

◆ maxCowTime() [1/3]

int64_t abacus::Master::maxCowTime ( ) const
inline

Returns the maximal wall-clock time (in seconds) which can be used by the optimization.

Definition at line 622 of file master.h.

◆ maxCowTime() [2/3]

void abacus::Master::maxCowTime ( const string &  t)

Sets the maximally allowed wall-clock time for the optimization to t.

Parameters
tThe new value of the maximal cpu time in the form hh:mm:ss.

◆ maxCowTime() [3/3]

void abacus::Master::maxCowTime ( int64_t  seconds)
inline

Sets the maximally allowed wall-clock time to seconds.

Definition at line 628 of file master.h.

◆ maxCowTimeAsString()

string abacus::Master::maxCowTimeAsString ( ) const

Returns the maximal wall-clock time (as string hh:mm:ss) which can be used by the optimization.

◆ maxCpuTime() [1/4]

int64_t abacus::Master::maxCpuTime ( ) const
inline

Returns the maximal cpu time (in seconds) which can be used by the optimization.

Definition at line 604 of file master.h.

◆ maxCpuTime() [2/4]

void abacus::Master::maxCpuTime ( const string &  t)

Sets the maximally allowed cpu time for the optimization to t.

Parameters
tThe new value of the maximal cpu time in the form hh:mm:ss.

◆ maxCpuTime() [3/4]

void abacus::Master::maxCpuTime ( int  hour,
int  min,
int  sec 
)

Sets the maximally allowed cpu time for the optimization to hour, min, sec.

◆ maxCpuTime() [4/4]

void abacus::Master::maxCpuTime ( int64_t  seconds)
inline

Sets the maximally allowed cpu time to seconds.

Definition at line 616 of file master.h.

◆ maxCpuTimeAsString()

string abacus::Master::maxCpuTimeAsString ( ) const

Returns the maximal cpu time (as string hh:mm:ss) which can be used by the optimization.

◆ maxIterations() [1/2]

int abacus::Master::maxIterations ( ) const
inline

Returns the maximal number of iterations per subproblem optimization (-1 means no iteration limit).

Definition at line 874 of file master.h.

◆ maxIterations() [2/2]

void abacus::Master::maxIterations ( int  max)
inline

Changes the default value for the maximal number of iterations of the optimization of a subproblem.

Note
This function changes only this value for subproblems that are constructed after this function call. For already constructed objects the value can be changed with the function Sub::maxIterations().
Parameters
maxThe new maximal number of iterations of the subproblem optimization (-1 means no limit).

Definition at line 886 of file master.h.

◆ maxLevel() [1/2]

int abacus::Master::maxLevel ( ) const
inline

Returns the maximal depth up to which the enumeration should be performed.

By default the maximal enumeration depth is INT_MAX.

Definition at line 579 of file master.h.

◆ maxLevel() [2/2]

void abacus::Master::maxLevel ( int  ml)

This version of the function maxLevel() changes the maximal enumeration depth.

If it is set to 1 the branch-and-cut algorithm becomes a pure cutting plane algorithm.

Parameters
mlThe new value of the maximal enumeration level.

◆ maxNSub() [1/2]

int abacus::Master::maxNSub ( ) const
inline

Returns the maximal number of subproblems to be processed.

By default this number is INT_MAX.

Definition at line 593 of file master.h.

◆ maxNSub() [2/2]

void abacus::Master::maxNSub ( int  ml)

Changes the maximal number of subproblems to ml.

If it is set to 1 the branch-and-cut algorithm becomes a pure cutting plane algorithm.

Parameters
mlThe new value of the maximal enumeration level.

◆ maxVarAdd() [1/2]

int abacus::Master::maxVarAdd ( ) const
inline

Returns the maximal number of variables which should be added in the column generation algorithm.

Definition at line 853 of file master.h.

◆ maxVarAdd() [2/2]

void abacus::Master::maxVarAdd ( int  max)
inline

Changes the maximal number of variables that are added in an iteration of the subproblem optimization.

Parameters
maxThe new maximal number of added variables.

Definition at line 859 of file master.h.

◆ maxVarBuffered() [1/2]

int abacus::Master::maxVarBuffered ( ) const
inline

Returns the size of the buffer for the variables generated in the column generation algorithm.

Definition at line 862 of file master.h.

◆ maxVarBuffered() [2/2]

void abacus::Master::maxVarBuffered ( int  max)
inline

Changes the maximal number of variables that are buffered in an iteration of the subproblem optimization.

Note
This function changes only the default value for subproblems that are activated after its call.
Parameters
maxThe new maximal number of buffered variables.

Definition at line 871 of file master.h.

◆ minDormantRounds() [1/2]

int abacus::Master::minDormantRounds ( ) const
inline

Returns the maximal number of rounds, i.e., number of subproblem optimizations, a subproblem is dormant.

I.e., it is not selected from the set of open subproblem if its status is Dormant, if possible.

Definition at line 700 of file master.h.

◆ minDormantRounds() [2/2]

void abacus::Master::minDormantRounds ( int  nRounds)
inline

Sets the number of rounds a subproblem should stay dormant to nRounds.

Parameters
nRoundsThe new minimal number of dormant rounds.

Definition at line 706 of file master.h.

◆ nBranchingVariableCandidates() [1/2]

int abacus::Master::nBranchingVariableCandidates ( ) const
inline

Returns the number of variables that should be tested for the selection of the branching variable.

Definition at line 544 of file master.h.

◆ nBranchingVariableCandidates() [2/2]

void abacus::Master::nBranchingVariableCandidates ( int  n)

Sets the number of tested branching variable candidates to n.

Parameters
nThe new value of the number of tested variables for becoming branching variable.

◆ newFixed()

void abacus::Master::newFixed ( int  n)
inlineprivate

Increments the counter of the number of fixed variables by n.

Definition at line 1236 of file master.h.

◆ newRootReOptimize() [1/2]

bool abacus::Master::newRootReOptimize ( ) const
inline
Returns
true Then a new root of the remaining branch-and-bound tree is reoptimized such that the associated reduced costs can be used for the fixing of variables;
false A new root is not reoptimized.

Definition at line 906 of file master.h.

◆ newRootReOptimize() [2/2]

void abacus::Master::newRootReOptimize ( bool  on)
inline

Turns the reoptimization of new root nodes of the remaining branch and bound tree on or off.

Parameters
onIf true, new root nodes are reoptimized.

Definition at line 912 of file master.h.

◆ newSub()

void abacus::Master::newSub ( int  level)
private

Registers a new subproblem which is on level level in enumeration tree.

It is called each time a new subproblem is generated.

◆ nLp()

int abacus::Master::nLp ( ) const
inline

Returns the number of optimized linear programs (only LP-relaxations).

Definition at line 509 of file master.h.

◆ nNewRoot()

int abacus::Master::nNewRoot ( ) const
inline

Returns the number of root changes of the remaining branch-and-cut tree.

Definition at line 515 of file master.h.

◆ nStrongBranchingIterations() [1/2]

int abacus::Master::nStrongBranchingIterations ( ) const
inline

The number of simplex iterations that are performed when testing candidates for branching variables within strong branching.

Definition at line 554 of file master.h.

◆ nStrongBranchingIterations() [2/2]

void abacus::Master::nStrongBranchingIterations ( int  n)

Sets the number of simplex iterations that are performed when testing candidates for branching variables within strong branching.

Parameters
nThe new value of the number of simplex iterations.

◆ nSub()

int abacus::Master::nSub ( ) const
inline

returns the number of generated subproblems.

Definition at line 506 of file master.h.

◆ nSubSelected()

int abacus::Master::nSubSelected ( ) const
inline

Returns the number of subproblems which have already been selected from the set of open subproblems.

Definition at line 518 of file master.h.

◆ objInteger() [1/2]

bool abacus::Master::objInteger ( ) const
inline

If true then we assume that all feasible solutions have integral objective function values.

Definition at line 637 of file master.h.

◆ objInteger() [2/2]

void abacus::Master::objInteger ( bool  b)
inline

Sets the assumption that the objective function values of all feasible solutions are integer.

Parameters
bThe new value of the assumption.

Definition at line 643 of file master.h.

◆ openSub()

OpenSub* abacus::Master::openSub ( ) const
inline

Returns a pointer to the set of open subproblems.

Definition at line 448 of file master.h.

◆ operator=()

const Master& abacus::Master::operator= ( const Master rhs)
private

◆ optimize()

STATUS abacus::Master::optimize ( )

Performs the optimization by branch-and-bound.

Returns
The status of the optimization.

◆ optimumFileName() [1/2]

const string& abacus::Master::optimumFileName ( ) const
inline

Returns the name of the file that stores the optimum solutions.

Definition at line 915 of file master.h.

◆ optimumFileName() [2/2]

void abacus::Master::optimumFileName ( const char *  name)
inline

Changes the name of the file in which the value of the optimum solution is searched.

Parameters
nameThe new name of the file.

Definition at line 921 of file master.h.

◆ optSense()

const OptSense* abacus::Master::optSense ( ) const
inline

Returns a pointer to the object holding the optimization sense of the problem.

Definition at line 442 of file master.h.

◆ output()

virtual void abacus::Master::output ( ) const
inlinevirtual

Does nothing but can be redefined in derived classes for output before the timing statistics.

Definition at line 423 of file master.h.

◆ pbMode() [1/2]

PRIMALBOUNDMODE abacus::Master::pbMode ( ) const
inline

Returns the mode of the primal bound initialization.

Definition at line 709 of file master.h.

◆ pbMode() [2/2]

void abacus::Master::pbMode ( PRIMALBOUNDMODE  mode)
inline

Sets the mode of the primal bound initialization to mode.

Parameters
modeThe new mode of the primal bound initialization.

Definition at line 715 of file master.h.

◆ pricing()

bool abacus::Master::pricing ( ) const
inline
Returns
true If pricing has been set to true in the call of the constructor of the class Master, i.e., if a columns should be generated in the subproblem optimization; false otherwise.

Definition at line 439 of file master.h.

◆ pricingFreq() [1/2]

int abacus::Master::pricingFreq ( ) const
inline

Returns the number of linear programs being solved between two additional pricing steps.

If no additional pricing steps should be executed this parameter has to be set to 0. The default value of the pricing frequency is 0. This parameter does not influence the execution of pricing steps which are required for the correctness of the algorithm.

Definition at line 725 of file master.h.

◆ pricingFreq() [2/2]

void abacus::Master::pricingFreq ( int  f)

Sets the number of linear programs being solved between two additional pricing steps to f.

Parameters
fThe pricing frequency.

◆ pricingTime()

const ogdf::StopwatchCPU* abacus::Master::pricingTime ( ) const
inline

Returns a pointer to the timer measuring the cpu time spent in pricing.

Definition at line 500 of file master.h.

◆ primalBound() [1/2]

double abacus::Master::primalBound ( ) const
inline

Returns the value of the primal bound.

I.e., the lowerBound() for a maximization problem and the upperBound() for a minimization problem, respectively.

Definition at line 278 of file master.h.

◆ primalBound() [2/2]

void abacus::Master::primalBound ( double  x)

Sets the primal bound to x and makes a new entry in the solution history.

It is an error if the primal bound gets worse.

Parameters
xThe new value of the primal bound.

◆ primalViolated()

bool abacus::Master::primalViolated ( double  x) const

Can be used to compare a value with the one of the best known primal bound.

If the objective function values of all feasible solutions are integer, then we do not have to be so carefully.

Parameters
xThe value being compared with the primal bound.
Returns
true If x is not better than the best known primal bound, false otherwise.

◆ printGuarantee()

void abacus::Master::printGuarantee ( ) const

Writes the guarantee nicely formated on the output stream associated with this object.

If no bounds are available, or the lower bound is zero, but the upper bound is nonzero, then we cannot give any guarantee.

◆ printLP() [1/2]

bool abacus::Master::printLP ( ) const
inline
Returns
true Then the linear program is output every iteration of the subproblem optimization;
false The linear program is not output.

Definition at line 822 of file master.h.

◆ printLP() [2/2]

void abacus::Master::printLP ( bool  on)
inline

Turns the output of the linear program in every iteration on or off.

Parameters
onIf true, then the linear program is output, otherwise it is not output.

Definition at line 829 of file master.h.

◆ printParameters()

void abacus::Master::printParameters ( ) const

Writes all parameters of the class Master together with their values to the global output stream.

◆ problemName()

const string& abacus::Master::problemName ( ) const
inline

Returns the name of the instance being optimized (as specified in the constructor of this class).

Definition at line 476 of file master.h.

◆ removeCons()

void abacus::Master::removeCons ( int  n)
inlineprivate

Increments the counter for the total number of removed constraints by n.

Definition at line 1242 of file master.h.

◆ removeVars()

void abacus::Master::removeVars ( int  n)
inlineprivate

Increments the counter for the total number of removed variables by n.

Definition at line 1248 of file master.h.

◆ requiredGuarantee() [1/2]

double abacus::Master::requiredGuarantee ( ) const
inline

The guarantee specification for the optimization.

Definition at line 563 of file master.h.

◆ requiredGuarantee() [2/2]

void abacus::Master::requiredGuarantee ( double  g)

Changes the guarantee specification tp g.

Parameters
gThe new guarantee specification (in percent). This must be a nonnative value. Note, if the guarantee specification is changed after a single node of the enumeration tree has been fathomed, then the overall guarantee might differ from the new value.

◆ root()

Sub* abacus::Master::root ( ) const
inline

Can be used to access the root node of the branch-and-bound tree.

Returns
A pointer to the root node of the enumeration tree.

Definition at line 463 of file master.h.

◆ rootDualBound() [1/2]

double abacus::Master::rootDualBound ( ) const
inline

Returns the dual bound at the root node.

Definition at line 329 of file master.h.

◆ rootDualBound() [2/2]

void abacus::Master::rootDualBound ( double  x)
private

Updates the final dual bound of the root node.

This function should be only called at the end of the root node optimization.

◆ rRoot() [1/2]

Sub* abacus::Master::rRoot ( ) const
inline
Returns
A pointer to the root of the remaining branch-and-bound tree, i.e., the subproblem which is an ancestor of all open subproblems and has highest level in the tree.

Definition at line 470 of file master.h.

◆ rRoot() [2/2]

void abacus::Master::rRoot ( Sub newRoot,
bool  reoptimize 
)
private

Sets the root of the remaining branch-and-cut tree to newRoot.

If reoptimize is true a reoptimization of the subproblem *newRoot is performed. This is controlled via a function argument since it might not be desirable when we find a new rRoot_ during the fathoming of a complete subtree Sub::FathomTheSubtree().

◆ select()

Sub* abacus::Master::select ( )
private

Returns a pointer to an open subproblem for further processing.

If the set of open subproblems is empty or one of the criteria for early termination of the optimization (maximal cpu time, maximal elapsed time, guarantee) is fulfilled 0 is returned.

◆ separationTime()

const ogdf::StopwatchCPU* abacus::Master::separationTime ( ) const
inline

Returns a pointer to the timer measuring the cpu time spent in the separation of cutting planes.

Definition at line 494 of file master.h.

◆ setSolverParameters()

virtual bool abacus::Master::setSolverParameters ( OsiSolverInterface *  interface,
bool  solverIsApprox 
)
virtual

Sets solver specific parameters.

The default does nothing.

Returns
true if an error has occured, false otherwise.

◆ showAverageCutDistance() [1/2]

bool abacus::Master::showAverageCutDistance ( ) const
inline
Returns
true Then the average distance of the fractional solution from all added cutting planes is output every iteration of the subproblem optimization.
false The average cut distance is not output.

Definition at line 929 of file master.h.

◆ showAverageCutDistance() [2/2]

void abacus::Master::showAverageCutDistance ( bool  on)
inline

Turns the output of the average distance of the added cuts from the fractional solution on or off.

Parameters
onIf true the output is turned on, otherwise it is turned off.

Definition at line 935 of file master.h.

◆ skipFactor() [1/2]

int abacus::Master::skipFactor ( ) const
inline

Returns the frequency of subproblems in which constraints or variables should be generated.

Definition at line 734 of file master.h.

◆ skipFactor() [2/2]

void abacus::Master::skipFactor ( int  f)

Sets the frequency for constraint and variable generation to f.

Parameters
fThe new value of the frequency.

◆ skippingMode() [1/2]

SKIPPINGMODE abacus::Master::skippingMode ( ) const
inline

Returns the skipping strategy.

Definition at line 749 of file master.h.

◆ skippingMode() [2/2]

void abacus::Master::skippingMode ( SKIPPINGMODE  mode)
inline

Sets the skipping strategy to mode.

Parameters
modeThe new skipping strategy.

Definition at line 746 of file master.h.

◆ solveApprox()

bool abacus::Master::solveApprox ( ) const
inline

True, if an approximative solver should be used.

Definition at line 482 of file master.h.

◆ status() [1/2]

STATUS abacus::Master::status ( ) const
inline

Returns the status of the Master.

Definition at line 473 of file master.h.

◆ status() [2/2]

void abacus::Master::status ( STATUS  stat)
inlineprivate

Sets the status of the Master.

Definition at line 1264 of file master.h.

◆ tailOffNLp() [1/2]

int abacus::Master::tailOffNLp ( ) const
inline

Returns the number of linear programs considered in the tailing off analysis.

Definition at line 646 of file master.h.

◆ tailOffNLp() [2/2]

void abacus::Master::tailOffNLp ( int  n)
inline

Sets the number of linear programs considered in the tailing off analysis to n.

This new value is only relevant for subproblems activated after the change of this value.

Parameters
nThe new number of LPs for the tailing off analysis.

Definition at line 655 of file master.h.

◆ tailOffPercent() [1/2]

double abacus::Master::tailOffPercent ( ) const
inline

Returns the minimal change of the dual bound for the tailing off analysis in percent.

Definition at line 658 of file master.h.

◆ tailOffPercent() [2/2]

void abacus::Master::tailOffPercent ( double  p)

Sets the minimal change of the dual bound for the tailing off analysis to p.

This change is only relevant for subproblems activated after calling this function.

Parameters
pThe new value for the tailing off analysis.

◆ terminateOptimization()

virtual void abacus::Master::terminateOptimization ( )
inlineprotectedvirtual

The default implementation of terminateOptimization() does nothing.

This virtual function can be used as an entrance point after the optimization process is finished.

Reimplemented in ogdf::MinSteinerTreeDirectedCut< T >::Master, ogdf::cluster_planarity::CPlanarityMaster, ogdf::cluster_planarity::CP_MasterBase, and ogdf::cluster_planarity::MaxCPlanarMaster.

Definition at line 1138 of file master.h.

◆ theFuture()

void abacus::Master::theFuture ( )
private

◆ totalCowTime()

const ogdf::StopwatchWallClock* abacus::Master::totalCowTime ( ) const
inline

Returns a pointer to the timer measuring the total wall clock time.

Definition at line 479 of file master.h.

◆ totalTime()

const ogdf::StopwatchCPU* abacus::Master::totalTime ( ) const
inline

returns a pointer to the timer measuring the total cpu time for the optimization.

Definition at line 485 of file master.h.

◆ treeInterfaceLowerBound()

void abacus::Master::treeInterfaceLowerBound ( double  lb) const
private

Passes the new lower bound lb to the Tree Interface.

◆ treeInterfaceNewNode()

void abacus::Master::treeInterfaceNewNode ( Sub sub) const
private

Adds the subproblem sub to the stream storing information for graphical output of the enumeration tree if this logging is turned on.

◆ treeInterfaceNodeBounds()

void abacus::Master::treeInterfaceNodeBounds ( int  id,
double  lb,
double  ub 
)
private

Updates the node information in the node with number id by writing the lower bound lb and the upper bound ub to the node.

◆ treeInterfacePaintNode()

void abacus::Master::treeInterfacePaintNode ( int  id,
int  color 
) const
private

Assigns the color to the subproblem sub in the Tree Interface.

◆ treeInterfaceUpperBound()

void abacus::Master::treeInterfaceUpperBound ( double  ub) const
private

Passes the new upper bound ub to the Tree Interface.

◆ upperBound()

double abacus::Master::upperBound ( ) const
inline

Returns the value of the global upper bound.

Definition at line 1530 of file master.h.

◆ varElimAge() [1/2]

int abacus::Master::varElimAge ( ) const
inline

Returns the age for the elimination of variables by the reduced cost criterion.

Definition at line 788 of file master.h.

◆ varElimAge() [2/2]

void abacus::Master::varElimAge ( int  age)
inline

Changes the age for the elimination of variables by the reduced cost criterion to age.

Parameters
ageThe new age.

Definition at line 794 of file master.h.

◆ varElimEps() [1/2]

double abacus::Master::varElimEps ( ) const
inline

Returns the zero tolerance for the elimination of variables by the reduced cost criterion.

Definition at line 779 of file master.h.

◆ varElimEps() [2/2]

void abacus::Master::varElimEps ( double  eps)
inline

Changes the tolerance for the elimination of variables by the reduced cost criterion to eps.

Parameters
epsThe new tolerance.

Definition at line 785 of file master.h.

◆ varElimMode() [1/2]

VARELIMMODE abacus::Master::varElimMode ( ) const
inline

Returns the mode for the elimination of variables.

Definition at line 761 of file master.h.

◆ varElimMode() [2/2]

void abacus::Master::varElimMode ( VARELIMMODE  mode)
inline

Changes the variable elimination mode to mode.

Parameters
modeThe new variable elimination mode.

Definition at line 767 of file master.h.

◆ varPool()

StandardPool<Variable, Constraint>* abacus::Master::varPool ( ) const
inline

Returns a pointer to the default pool storing the variables.

Definition at line 457 of file master.h.

◆ vbcLog() [1/2]

VBCMODE abacus::Master::vbcLog ( ) const
inline

Returns the mode of output for the Vbc-Tool.

Definition at line 938 of file master.h.

◆ vbcLog() [2/2]

void abacus::Master::vbcLog ( VBCMODE  mode)
inline

Changes the mode of output for the Vbc-Tool to mode.

This function should only be called before the optimization is started with the function Master::optimize().

Parameters
modeThe new mode.

Definition at line 947 of file master.h.

◆ writeTreeInterface()

void abacus::Master::writeTreeInterface ( const string &  info,
bool  time = true 
) const
private

Writes the string info to the stream associated with the Tree Interface.

A $ is preceded if the output is written to standard out for further pipelining. If time is true a time string is written in front of the information. The default value of time is true.

Friends And Related Function Documentation

◆ FixCand

friend class FixCand
friend

Definition at line 72 of file master.h.

◆ Sub

friend class Sub
friend

Definition at line 71 of file master.h.

Member Data Documentation

◆ BRANCHINGSTRAT_

const char* abacus::Master::BRANCHINGSTRAT_[]
static

Literal values for the enumerators of the corresponding enumeration type.

The order of the enumerators is preserved (e.g., BRANCHINGSTRAT_[0]=="CloseHalf").

Definition at line 130 of file master.h.

◆ branchingStrategy_

BRANCHINGSTRAT abacus::Master::branchingStrategy_
private

The branching strategy.

Definition at line 1298 of file master.h.

◆ branchingTime_

ogdf::StopwatchCPU abacus::Master::branchingTime_
private

The timer for the cpu time spent in determining the branching rules.

Definition at line 1490 of file master.h.

◆ conElimAge_

int abacus::Master::conElimAge_
private

The number of iterations an elimination criterion must be satisfied until a constraint can be removed.

Definition at line 1461 of file master.h.

◆ conElimEps_

double abacus::Master::conElimEps_
private

The tolerance for the elimination of constraints by the mode NonBinding/.

Definition at line 1455 of file master.h.

◆ CONELIMMODE_

const char* abacus::Master::CONELIMMODE_[]
static

Literal values for the enumerators of the corresponding enumeration type.

The order of the enumerators is preserved (e.g., CONELIMMODE_[0]=="None").

Definition at line 177 of file master.h.

◆ conElimMode_

CONELIMMODE abacus::Master::conElimMode_
private

The way constraints are automatically eliminated in the cutting plane algorithm.

Definition at line 1449 of file master.h.

◆ conPool_

StandardPool<Constraint, Variable>* abacus::Master::conPool_
private

The default pool with the constraints of the problem formulation.

Definition at line 1312 of file master.h.

◆ cutPool_

StandardPool<Constraint, Variable>* abacus::Master::cutPool_
private

The default pool of dynamically generated constraints.

Definition at line 1316 of file master.h.

◆ cutting_

bool abacus::Master::cutting_
private

If true, then constraints are generated in the optimization.

Definition at line 1334 of file master.h.

◆ dbThreshold_

int abacus::Master::dbThreshold_
private

The number of optimizations of an Sub until branching is performed.

Definition at line 1385 of file master.h.

◆ defaultLpSolver_

OSISOLVER abacus::Master::defaultLpSolver_
private

The default LP-Solver.

Definition at line 1307 of file master.h.

◆ dualBound_

double abacus::Master::dualBound_
private

The best known dual bound.

Definition at line 1325 of file master.h.

◆ eliminateFixedSet_

bool abacus::Master::eliminateFixedSet_
private

If true, then nonbasic fixed and set variables are eliminated.

Definition at line 1431 of file master.h.

◆ enumerationStrategy_

ENUMSTRAT abacus::Master::enumerationStrategy_
private

The enumeration strategy.

Definition at line 1295 of file master.h.

◆ ENUMSTRAT_

const char* abacus::Master::ENUMSTRAT_[]
static

Literal values for the enumerators of the corresponding enumeration type.

The order of the enumerators is preserved (e.g., ENUMSTRAT_[0]=="BestFirst").

Definition at line 117 of file master.h.

◆ fixCand_

FixCand* abacus::Master::fixCand_
private

The variables which are candidates for being fixed.

Definition at line 1331 of file master.h.

◆ fixSetByRedCost_

bool abacus::Master::fixSetByRedCost_
private

If true, then variables are fixed and set by reduced cost criteria.

Definition at line 1410 of file master.h.

◆ highestLevel_

int abacus::Master::highestLevel_
private

The highest level which has been reached in the enumeration tree.

Definition at line 1499 of file master.h.

◆ history_

History* abacus::Master::history_
private

The solution history.

Definition at line 1292 of file master.h.

◆ improveTime_

ogdf::StopwatchCPU abacus::Master::improveTime_
private

The timer for the cpu time spent in the heuristics for the computation of feasible solutions.

Definition at line 1484 of file master.h.

◆ lpMasterOsi_

LpMasterOsi* abacus::Master::lpMasterOsi_
private

Definition at line 1309 of file master.h.

◆ lpSolverTime_

ogdf::StopwatchCPU abacus::Master::lpSolverTime_
private

Definition at line 1478 of file master.h.

◆ lpTime_

ogdf::StopwatchCPU abacus::Master::lpTime_
private

The timer for the cpu time spent in the LP-interface.

Definition at line 1476 of file master.h.

◆ maxConAdd_

int abacus::Master::maxConAdd_
private

The maximal number of added constraints per iteration of the cutting plane algorithm.

Definition at line 1416 of file master.h.

◆ maxConBuffered_

int abacus::Master::maxConBuffered_
private

The size of the buffer for generated cutting planes.

Definition at line 1419 of file master.h.

◆ maxCowTime_

int64_t abacus::Master::maxCowTime_
private

The maximal available wall-clock time.

Definition at line 1373 of file master.h.

◆ maxCpuTime_

int64_t abacus::Master::maxCpuTime_
private

The maximal available cpu time.

Definition at line 1370 of file master.h.

◆ maxIterations_

int abacus::Master::maxIterations_
private

The maximal number of iterations of the cutting plane/column generation algorithm in the subproblem.

Definition at line 1428 of file master.h.

◆ maxLevel_

int abacus::Master::maxLevel_
private

The maximal level in enumeration tree.

Up to this level subproblems are considered in the enumeration.

Definition at line 1361 of file master.h.

◆ maxNSub_

int abacus::Master::maxNSub_
private

The maximal number of subproblems to be processed.

Up to this number subproblems are considered in the enumeration.

Definition at line 1367 of file master.h.

◆ maxVarAdd_

int abacus::Master::maxVarAdd_
private

The maximal number of added variables per iteration of the column generation algorithm.

Definition at line 1422 of file master.h.

◆ maxVarBuffered_

int abacus::Master::maxVarBuffered_
private

The size of the buffer for generated variables.

Definition at line 1425 of file master.h.

◆ minDormantRounds_

int abacus::Master::minDormantRounds_
private

The minimal number of rounds, i.e., number of subproblem optimizations, a subproblem is dormant, i.e., it is not selected from the set of open subproblem if its status is Dormant, if possible.

Definition at line 1392 of file master.h.

◆ nAddCons_

int abacus::Master::nAddCons_
private

The total number of added constraints.

Definition at line 1505 of file master.h.

◆ nAddVars_

int abacus::Master::nAddVars_
private

The total number of added variables.

Definition at line 1511 of file master.h.

◆ nBranchingVariableCandidates_

int abacus::Master::nBranchingVariableCandidates_
private

The number of candidates that are evaluated for branching on variables.

Definition at line 1301 of file master.h.

◆ newRootReOptimize_

bool abacus::Master::newRootReOptimize_
private

If true, then an already earlier processed node is reoptimized if it becomes the new root of the remaining branch-and-bound tree.

Definition at line 1437 of file master.h.

◆ nFixed_

int abacus::Master::nFixed_
private

The total number of fixed variables.

Definition at line 1502 of file master.h.

◆ nLp_

int abacus::Master::nLp_
private

The number of solved LPs.

Definition at line 1496 of file master.h.

◆ nNewRoot_

int abacus::Master::nNewRoot_
private

The number of changes of the root of the remaining branch-and-bound tree.

Definition at line 1517 of file master.h.

◆ nRemCons_

int abacus::Master::nRemCons_
private

The total number of removed constraints.

Definition at line 1508 of file master.h.

◆ nRemVars_

int abacus::Master::nRemVars_
private

The total number of removed variables.

Definition at line 1514 of file master.h.

◆ nStrongBranchingIterations_

int abacus::Master::nStrongBranchingIterations_
private

The number of simplex iterations that are performed when testing a branching variable candidate within strong branching.

Definition at line 1304 of file master.h.

◆ nSub_

int abacus::Master::nSub_
private

The number of generated subproblems.

Definition at line 1493 of file master.h.

◆ nSubSelected_

int abacus::Master::nSubSelected_
private

The number of subproblems already selected from the list of open subproblems.

Definition at line 1343 of file master.h.

◆ objInteger_

bool abacus::Master::objInteger_
private

true, if all objective function values of feasible solutions are assumed to be integer.

Definition at line 1376 of file master.h.

◆ openSub_

OpenSub* abacus::Master::openSub_
private

The set of open subproblems.

Definition at line 1289 of file master.h.

◆ optimumFileName_

string abacus::Master::optimumFileName_
private

The name of a file storing a list of optimum solutions of problem instances.

Definition at line 1440 of file master.h.

◆ optSense_

OptSense abacus::Master::optSense_
private

The sense of the objective function.

Definition at line 1280 of file master.h.

◆ OSISOLVER_

const char* abacus::Master::OSISOLVER_[]
static

Array for the literal values for possible Osi solvers.

Definition at line 212 of file master.h.

◆ pbMode_

PRIMALBOUNDMODE abacus::Master::pbMode_
private

The mode of the primal bound initialization.

Definition at line 1395 of file master.h.

◆ pricing_

bool abacus::Master::pricing_
private

If true, then variables are generated in the optimization.

Definition at line 1337 of file master.h.

◆ pricingFreq_

int abacus::Master::pricingFreq_
private

The number of solved LPs between two additional pricing steps.

Definition at line 1398 of file master.h.

◆ pricingTime_

ogdf::StopwatchCPU abacus::Master::pricingTime_
private

The timer for the cpu time spent in pricing.

Definition at line 1487 of file master.h.

◆ primalBound_

double abacus::Master::primalBound_
private

The best known primal bound.

Definition at line 1322 of file master.h.

◆ PRIMALBOUNDMODE_

const char* abacus::Master::PRIMALBOUNDMODE_[]
static

Literal values for the enumerators of the corresponding enumeration type.

The order of the enumerators is preserved (e.g., PRIMALBOUNDMODE_[0]=="None").

Definition at line 150 of file master.h.

◆ printLP_

bool abacus::Master::printLP_
private

If true, then the linear program is output every iteration.

Definition at line 1413 of file master.h.

◆ problemName_

string abacus::Master::problemName_
private

The name of the optimized problem.

Definition at line 1275 of file master.h.

◆ readParamFromFile_

bool abacus::Master::readParamFromFile_
private

Definition at line 1277 of file master.h.

◆ requiredGuarantee_

double abacus::Master::requiredGuarantee_
private

The guarantee in percent which should be reached when the optimization stops.

If this value is 0.0, then the optimum solution is determined.

Definition at line 1355 of file master.h.

◆ root_

Sub* abacus::Master::root_
private

The root node of the enumeration tree.

Definition at line 1283 of file master.h.

◆ rootDualBound_

double abacus::Master::rootDualBound_
private

The best known dual bound at the end of the optimization of the root node.

Definition at line 1328 of file master.h.

◆ rRoot_

Sub* abacus::Master::rRoot_
private

The root node of the remaining enumeration tree.

Definition at line 1286 of file master.h.

◆ separationTime_

ogdf::StopwatchCPU abacus::Master::separationTime_
private

The timer for the cpu time spent in the separation.

Definition at line 1481 of file master.h.

◆ showAverageCutDistance_

bool abacus::Master::showAverageCutDistance_
private

If true then the average distance of the added cutting planes is output every iteration of the cutting plane algorithm.

Definition at line 1446 of file master.h.

◆ skipFactor_

int abacus::Master::skipFactor_
private

The frequency constraints or variables are generated depending on the skipping mode.

Definition at line 1401 of file master.h.

◆ SKIPPINGMODE_

const char* abacus::Master::SKIPPINGMODE_[]
static

Literal values for the enumerators of the corresponding enumeration type.

The order of the enumerators is preserved (e.g., SKIPPINGMODE_[0]=="None").

Definition at line 163 of file master.h.

◆ skippingMode_

SKIPPINGMODE abacus::Master::skippingMode_
private

Either constraints are generated only every skipFactor_ subproblem (SkipByNode) only every skipFactor_ level (SkipByLevel).

Definition at line 1407 of file master.h.

◆ solveApprox_

bool abacus::Master::solveApprox_
private

If true, then an approximative solver is used to solve linear programs.

Definition at line 1340 of file master.h.

◆ STATUS_

const char* abacus::Master::STATUS_[]
static

Literal values for the enumerators of the corresponding enumeration type.

The order of the enumerators is preserved (e.g., STATUS_[0]=="Optimal").

Definition at line 99 of file master.h.

◆ status_

STATUS abacus::Master::status_
private

The current status of the optimization.

Definition at line 1467 of file master.h.

◆ tailOffNLp_

int abacus::Master::tailOffNLp_
private

The number of LP-iterations for the tailing off analysis.

Definition at line 1379 of file master.h.

◆ tailOffPercent_

double abacus::Master::tailOffPercent_
private

The minimal change of the LP-value on the tailing off analysis.

Definition at line 1382 of file master.h.

◆ totalCowTime_

ogdf::StopwatchWallClock abacus::Master::totalCowTime_
private

The timer for the total elapsed time.

Definition at line 1470 of file master.h.

◆ totalTime_

ogdf::StopwatchCPU abacus::Master::totalTime_
private

The timer for the total cpu time for the optimization.

Definition at line 1473 of file master.h.

◆ treeStream_

std::ostream* abacus::Master::treeStream_
private

A pointer to the log stream for the VBC-Tool.

Definition at line 1349 of file master.h.

◆ varElimAge_

int abacus::Master::varElimAge_
private

The number of iterations an elimination criterion must be satisfied until a variable can be removed.

Definition at line 1464 of file master.h.

◆ varElimEps_

double abacus::Master::varElimEps_
private

The tolerance for the elimination of variables by the mode ReducedCost.

Definition at line 1458 of file master.h.

◆ VARELIMMODE_

const char* abacus::Master::VARELIMMODE_[]
static

Literal values for the enumerators of the corresponding enumeration type.

The order of the enumerators is preserved (e.g., VARELIMMODE_[0]=="None").

Definition at line 189 of file master.h.

◆ varElimMode_

VARELIMMODE abacus::Master::varElimMode_
private

The way variables are automatically eliminated in the column generation algorithm.

Definition at line 1452 of file master.h.

◆ varPool_

StandardPool<Variable, Constraint>* abacus::Master::varPool_
private

The default pool with the variables of the problem formulation.

Definition at line 1319 of file master.h.

◆ VbcLog_

VBCMODE abacus::Master::VbcLog_
private

Ouput for the Tree Interface is generated depending on the value of this variable.

Definition at line 1346 of file master.h.

◆ VBCMODE_

const char* abacus::Master::VBCMODE_[]
static

Literal values for the enumerators of the corresponding enumeration type.

The order of the enumerators is preserved (e.g., VBCMODE_[0]=="None").

Definition at line 202 of file master.h.


The documentation for this class was generated from the following file: