# OpenGraph DrawingFramework

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...

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...

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...

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...

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...

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...

The total number of added constraints. More...

int nRemCons_
The total number of removed constraints. More...

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...

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

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...

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

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...

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...

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)

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.

## ◆ 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.

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.

## ◆ 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
 problemName The name of the problem being solved. Must not be a 0-pointer. cutting If true, then cutting planes can be generated if the function Sub::separate() is redefined. pricing If true, then inactive variables are priced in, if the function Sub::pricing() is redefined. optSense The 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. eps The zero-tolerance used within all member functions of objects which have a pointer to this master (default value 1.0e-4). machineEps The machine dependent zero tolerance (default value 1.0e-7). infinity All values greater than infinity are regarded as "infinite big", all values less than -infinity are regarded as "infinite small" (default value 1.0e30). readParamFromFile If 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

## ◆ _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.

 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.

 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
 s1 A subproblem. s2 A subproblem.

## ◆ betterDual()

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

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

Parameters
 x The 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
 x The 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
 strat The 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.

 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
 s1 The first subproblem. s2 The 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
 age The 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
 eps The 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
 mode The new constraint elimination mode.

Definition at line 758 of file master.h.

## ◆ conPool()

 StandardPool* 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* 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
 threshold The 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
 osiSolver The 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
 nOpt The 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
 s1 The first subproblem. s2 The 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
 s1 The first subproblem. s2 The 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
 x The 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
 turnOn The 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
 s1 A pointer to a subproblem. s2 A pointer to a subproblem.

## ◆ enumerationStrategy() [3/3]

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

Changes the enumeration strategy to strat.

Parameters
 strat The 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
 s1 A subproblem. s2 A 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.

## ◆ 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
 on If 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.

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
 sense The 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
 constraints The constraints of the problem formulation are inserted in the constraint pool. The size of the constraint pool equals the number of constraints. cuts The 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. variables The variables of the problem formulation are inserted in the variable pool. varPoolSize The size of the pool for the variables. If more variables are added the variable pool is automatically reallocated. cutPoolSize The size of the pool for cutting planes. dynamicCutPool If 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
 constraints The constraints of the problem formulation are inserted in the constraint pool. The size of the constraint pool equals the number of constraints. variables The variables of the problem formulation are inserted in the variable pool. varPoolSize The size of the pool for the variables. If more variables are added the variable pool is automatically reallocated. cutPoolSize The size of the pool for cutting planes. dynamicCutPool If 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
 optVal If 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.

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.

 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
 max The 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
 t The 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
 t The 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
 max The 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
 ml The 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
 ml The new value of the maximal enumeration level.

inline

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

Definition at line 853 of file master.h.

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

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

Parameters
 max The 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
 max The 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
 nRounds The 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
 n The 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
 on If 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
 n The 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
 b The 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
 name The 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
 mode The 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
 f The 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
 x The 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
 x The 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
 on If 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
 g The 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
 on If 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
 f The 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
 mode The 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
 n The 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
 p The 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.

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
 age The 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
 eps The 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
 mode The new variable elimination mode.

Definition at line 767 of file master.h.

## ◆ varPool()

 StandardPool* 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
 mode The 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.

## ◆ 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.

## ◆ 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* abacus::Master::conPool_
private

The default pool with the constraints of the problem formulation.

Definition at line 1312 of file master.h.

## ◆ cutPool_

 StandardPool* 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.

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.

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.

private

The total number of added constraints.

Definition at line 1505 of file master.h.

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.

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* 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: