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

BRANCHINGSTRAT	branchingStrategy () const
	Returns the branching strategy. More...

void	branchingStrategy (BRANCHINGSTRAT strat)
	Changes the branching strategy to strat. More...

const ogdf::StopwatchCPU *	branchingTime () const
	Returns a pointer to the timer measuring the cpu time spent in finding and selecting the branching rules. 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...

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

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

CONELIMMODE	conElimMode () const
	Returns the mode for the elimination of constraints. More...

void	conElimMode (CONELIMMODE mode)
	Changes the constraint elimination mode to mode. 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...

bool	cutting () const

int	dbThreshold () const
	Returns the number of optimizations of a subproblem until sons are created. More...

void	dbThreshold (int threshold)
	Sets the number of optimizations of a subproblem until sons are created in Sub::branching(). More...

OSISOLVER	defaultLpSolver () const
	returns the Lp Solver. More...

void	defaultLpSolver (OSISOLVER osiSolver)
	Changes the default Lp solver to osiSolver. 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...

bool	eliminateFixedSet () const

void	eliminateFixedSet (bool turnOn)
	Turns the elimination of fixed and set variables on or off. More...

ENUMSTRAT	enumerationStrategy () const
	Returns the enumeration strategy. 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...

void	enumerationStrategy (ENUMSTRAT strat)
	Changes the enumeration strategy to strat. More...

bool	fixSetByRedCost () const

void	fixSetByRedCost (bool on)
	Turns fixing and setting variables by reduced cost on or off. More...

double	guarantee () const
	Can be used to access the guarantee which can be given for the best known feasible solution. More...

bool	guaranteed () const
	Can be used to check if the guarantee requirements are fulfilled. More...

int	highestLevel () const
	Returns the highest level in the tree which has been reached during the implicit enumeration. More...

History *	history () const
	Returns a pointer to the object storing the solution history of this branch and cut problem. More...

const ogdf::StopwatchCPU *	improveTime () const
	Returns a pointer to the timer measuring the cpu time spent in the heuristics for the computation of feasible solutions. 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...

LpMasterOsi *	lpMasterOsi () const

const ogdf::StopwatchCPU *	lpSolverTime () const
	Return a pointer to the timer measuring the cpu time required by the LP solver. More...

const ogdf::StopwatchCPU *	lpTime () const
	Returns a pointer to the timer measuring the cpu time spent in members of the LP-interface. More...

int	maxConAdd () const
	Returns the maximal number of constraints which should be added in every iteration of the cutting plane algorithm. More...

void	maxConAdd (int max)
	Sets the maximal number of constraints that are added in an iteration of the cutting plane algorithm. More...

int	maxConBuffered () const
	Returns the size of the buffer for generated constraints in the cutting plane algorithm. More...

void	maxConBuffered (int max)
	Changes the maximal number of constraints that are buffered in an iteration of the cutting plane algorithm. More...

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

void	maxCowTime (const string &t)
	Sets the maximally allowed wall-clock time for the optimization to t. More...

void	maxCowTime (int64_t seconds)
	Sets the maximally allowed wall-clock time to seconds. More...

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

int64_t	maxCpuTime () const
	Returns the maximal cpu time (in seconds) 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 (int hour, int min, int sec)
	Sets the maximally allowed cpu time for the optimization to hour, min, sec. More...

void	maxCpuTime (int64_t seconds)
	Sets the maximally allowed cpu time to seconds. More...

string	maxCpuTimeAsString () const
	Returns the maximal cpu time (as string `hh:mm:ss`) which can be used by the 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...

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

int	maxVarAdd () const
	Returns the maximal number of variables which should be added in the column generation algorithm. More...

void	maxVarAdd (int max)
	Changes the maximal number of variables that are added in an iteration of the subproblem optimization. More...

int	maxVarBuffered () const
	Returns the size of the buffer for the variables generated in the column generation algorithm. More...

void	maxVarBuffered (int max)
	Changes the maximal number of variables that are buffered in an iteration of the subproblem optimization. More...

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

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

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

int	nLp () const
	Returns the number of optimized linear programs (only LP-relaxations). More...

int	nNewRoot () const
	Returns the number of root changes of the remaining branch-and-cut tree. 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...

int	nSub () const
	returns the number of generated subproblems. More...

int	nSubSelected () const
	Returns the number of subproblems which have already been selected from the set of open subproblems. 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...

OpenSub *	openSub () const
	Returns a pointer to the set of open subproblems. More...

STATUS	optimize ()
	Performs the optimization by branch-and-bound. 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...

const OptSense *	optSense () const
	Returns a pointer to the object holding the optimization sense of the problem. More...

virtual void	output () const
	Does nothing but can be redefined in derived classes for output before the timing statistics. 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...

bool	pricing () const

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

const ogdf::StopwatchCPU *	pricingTime () const
	Returns a pointer to the timer measuring the cpu time spent in pricing. More...

void	printGuarantee () const
	Writes the guarantee nicely formated on the output stream associated with this object. More...

bool	printLP () const

void	printLP (bool on)
	Turns the output of the linear program in every iteration on or off. More...

void	printParameters () const
	Writes all parameters of the class Master together with their values to the global output stream. More...

const string &	problemName () const
	Returns the name of the instance being optimized (as specified in the constructor of this class). More...

double	requiredGuarantee () const
	The guarantee specification for the optimization. More...

void	requiredGuarantee (double g)
	Changes the guarantee specification tp g. More...

Sub *	root () const
	Can be used to access the root node of the branch-and-bound tree. More...

Sub *	rRoot () const

const ogdf::StopwatchCPU *	separationTime () const
	Returns a pointer to the timer measuring the cpu time spent in the separation of cutting planes. More...

virtual bool	setSolverParameters (OsiSolverInterface *interface, bool solverIsApprox)
	Sets solver specific parameters. 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...

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

SKIPPINGMODE	skippingMode () const
	Returns the skipping strategy. More...

void	skippingMode (SKIPPINGMODE mode)
	Sets the skipping strategy to mode. More...

bool	solveApprox () const
	True, if an approximative solver should be used. More...

STATUS	status () const
	Returns the status of the Master. 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...

const ogdf::StopwatchWallClock *	totalCowTime () const
	Returns a pointer to the timer measuring the total wall clock time. More...

const ogdf::StopwatchCPU *	totalTime () const
	returns a pointer to the timer measuring the total cpu time for the optimization. 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...

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

VARELIMMODE	varElimMode () const
	Returns the mode for the elimination of variables. More...

void	varElimMode (VARELIMMODE mode)
	Changes the variable elimination mode to mode. More...

StandardPool< Variable, Constraint > *	varPool () const
	Returns a pointer to the default pool storing the variables. 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...

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

Public Member Functions inherited from abacus::AbacusGlobal
	AbacusGlobal (double eps=1.0e-4, double machineEps=1.0e-7, double infinity=1.0e32)
	The constructor. More...

virtual	~AbacusGlobal ()
	The destructor. More...

void	assignParameter (bool &param, const char *name) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (bool &param, const char *name, bool defVal) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (char &param, const char name, const char feasible, char defVal) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (char &param, const char name, const char feasible=nullptr) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (double &param, const char *name, double minVal, double maxVal) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (double &param, const char *name, double minVal, double maxVal, double defVal) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (int &param, const char *name, int minVal, int maxVal) const
	Searches for parameter name in the parameter table and returns its value in param. More...

void	assignParameter (int &param, const char *name, int minVal, int maxVal, int defVal) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (string &param, const char name, unsigned nFeasible, const char feasible[], const char *defVal) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (string &param, const char name, unsigned nFeasible=0, const char feasible[]=nullptr) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (unsigned &param, const char *name, unsigned minVal, unsigned maxVal) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

void	assignParameter (unsigned &param, const char *name, unsigned minVal, unsigned maxVal, unsigned defVal) const
	See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More...

double	eps () const
	Returns the zero tolerance. More...

void	eps (double e)
	Sets the zero tolerance to e. More...

bool	equal (double x, double y) const
	Returns whether the absolute difference between x and y is less than the machine dependent zero tolerance. More...

int	findParameter (const char name, const char feasible) const
	See AbacusGlobal::findParameter(const char name, unsigned nFeasible, const int feasible) for description. More...

int	findParameter (const char name, unsigned nFeasible, const char feasible[]) const
	See AbacusGlobal::findParameter(const char name, unsigned nFeasible, const int feasible) for description. More...

int	findParameter (const char name, unsigned nFeasible, const int feasible) const
	Searches for parameter name in the parameter table. More...

int	getParameter (const char *name, bool &param) const

int	getParameter (const char *name, char &param) const

int	getParameter (const char *name, double &param) const

int	getParameter (const char *name, int &param) const
	Searches for parameter name in the parameter table and returns its value in param. More...

int	getParameter (const char *name, string &param) const

int	getParameter (const char *name, unsigned int &param) const

double	infinity () const
	Provides a floating point value of "infinite" size. More...

void	infinity (double x)
	Sets the "infinite value" to x. More...

void	insertParameter (const char name, const char value)
	Inserts parameter name with value value into the parameter table. More...

bool	isInfinity (double x) const
	Returns true if x is regarded as "infinite" large, false otherwise. More...

bool	isInteger (double x) const
	Returns whether the value x differs at most by the machine dependent zero tolerance from an integer value. More...

bool	isInteger (double x, double eps) const
	Returns whether the value x differs at most by eps from an integer value. More...

bool	isMinusInfinity (double x) const
	Returns true if x is regarded as infinite small, false otherwise. More...

double	machineEps () const
	Provides a machine dependent zero tolerance. More...

void	machineEps (double e)
	Sets the machine dependent zero tolerance to e. More...

void	readParameters (const string &fileName)
	Opens the parameter file fileName, reads all parameters, and inserts them in the parameter table. More...

Public Member Functions inherited from abacus::AbacusRoot
virtual	~AbacusRoot ()
	The destructor. More...

Static Public Attributes
static const char *	BRANCHINGSTRAT_ []
	Literal values for the enumerators of the corresponding enumeration type. More...

static const char *	CONELIMMODE_ []
	Literal values for the enumerators of the corresponding enumeration type. More...

static const char *	ENUMSTRAT_ []
	Literal values for the enumerators of the corresponding enumeration type. More...

static const char *	OSISOLVER_ []
	Array for the literal values for possible Osi solvers. More...

static const char *	PRIMALBOUNDMODE_ []
	Literal values for the enumerators of the corresponding enumeration type. More...

static const char *	SKIPPINGMODE_ []
	Literal values for the enumerators of the corresponding enumeration type. More...

static const char *	STATUS_ []
	Literal values for the enumerators of the corresponding enumeration type. More...

static const char *	VARELIMMODE_ []
	Literal values for the enumerators of the corresponding enumeration type. More...

static const char *	VBCMODE_ []
	Literal values for the enumerators of the corresponding enumeration type. More...

Protected Member Functions
virtual void	assignParameters ()
	Assigns the parameters that were read from a file to the member variables of the master. More...

int	bestFirstSearch (const Sub s1, const Sub s2) const
	Implements the best first search enumeration. 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	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	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 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...

virtual Sub *	firstSub ()=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...

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

virtual void	initializeParameters ()
	Is only a dummy. 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...

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	terminateOptimization ()
	The default implementation of terminateOptimization() does nothing. More...

Private Member Functions
	Master (const Master &rhs)

void	_createLpMasters ()

void	_deleteLpMasters ()

void	_initializeLpParameters ()

void	_initializeParameters ()
	Reads the parameter-file `.abacus`. More...

void	_outputLpStatistics () const
	Prints the LP solver specific statistics. More...

void	_printLpParameters () const
	Prints the LP solver specific parameters. More...

void	_setDefaultLpParameters ()
	Initializes the LP solver specific default parameters if they are not read from `.abacus`. More...

void	addCons (int n)
	Increments the counter for the total number of added constraints by n. More...

void	addVars (int n)
	Increments the counter for the total number of added variables by n. More...

void	countLp ()
	Increments the counter for linear programs and should be called in each optimization call of the LP-relaxation. More...

FixCand *	fixCand () const
	Returns a pointer to the object storing the variables which are candidates for being fixed. More...

int	initLP ()

void	newFixed (int n)
	Increments the counter of the number of fixed variables by n. More...

void	newSub (int level)
	Registers a new subproblem which is on level level in enumeration tree. More...

const Master &	operator= (const Master &rhs)

void	removeCons (int n)
	Increments the counter for the total number of removed constraints by n. More...

void	removeVars (int n)
	Increments the counter for the total number of removed variables by n. More...

void	rootDualBound (double x)
	Updates the final dual bound of the root node. More...

void	rRoot (Sub *newRoot, bool reoptimize)
	Sets the root of the remaining branch-and-cut tree to newRoot. More...

Sub *	select ()
	Returns a pointer to an open subproblem for further processing. More...

void	status (STATUS stat)
	Sets the status of the Master. More...

void	theFuture ()

void	treeInterfaceLowerBound (double lb) const
	Passes the new lower bound lb to 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	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	treeInterfacePaintNode (int id, int color) const
	Assigns the color to the subproblem sub in the Tree Interface. More...

void	treeInterfaceUpperBound (double ub) const
	Passes the new upper bound ub to the Tree Interface. More...

void	writeTreeInterface (const string &info, bool time=true) const
	Writes the string info to the stream associated with the Tree Interface. More...

Private Attributes
BRANCHINGSTRAT	branchingStrategy_
	The branching strategy. More...

ogdf::StopwatchCPU	branchingTime_
	The timer for the cpu time spent in determining the branching rules. More...

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

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

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

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

bool	cutting_
	If true, then constraints are generated in the optimization. More...

int	dbThreshold_
	The number of optimizations of an Sub until branching is performed. More...

OSISOLVER	defaultLpSolver_
	The default LP-Solver. More...

double	dualBound_
	The best known dual bound. More...

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

ENUMSTRAT	enumerationStrategy_
	The enumeration strategy. More...

FixCand *	fixCand_
	The variables which are candidates for being fixed. More...

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

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

History *	history_
	The solution history. More...

ogdf::StopwatchCPU	improveTime_
	The timer for the cpu time spent in the heuristics for the computation of feasible solutions. More...

LpMasterOsi *	lpMasterOsi_

ogdf::StopwatchCPU	lpSolverTime_

ogdf::StopwatchCPU	lpTime_
	The timer for the cpu time spent in the LP-interface. More...

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

int	maxConBuffered_
	The size of the buffer for generated cutting planes. More...

int64_t	maxCowTime_
	The maximal available wall-clock time. More...

int64_t	maxCpuTime_
	The maximal available cpu time. More...

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

int	maxLevel_
	The maximal level in enumeration tree. More...

int	maxNSub_
	The maximal number of subproblems to be processed. More...

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

int	maxVarBuffered_
	The size of the buffer for generated variables. More...

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

int	nAddCons_
	The total number of added constraints. More...

int	nAddVars_
	The total number of added variables. More...

int	nBranchingVariableCandidates_
	The number of candidates that are evaluated for branching on variables. 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...

int	nFixed_
	The total number of fixed variables. More...

int	nLp_
	The number of solved LPs. More...

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

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

int	nRemVars_
	The total number of removed variables. More...

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

int	nSub_
	The number of generated subproblems. More...

int	nSubSelected_
	The number of subproblems already selected from the list of open subproblems. More...

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

OpenSub *	openSub_
	The set of open subproblems. More...

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

OptSense	optSense_
	The sense of the objective function. More...

PRIMALBOUNDMODE	pbMode_
	The mode of the primal bound initialization. More...

bool	pricing_
	If true, then variables are generated in the optimization. More...

int	pricingFreq_
	The number of solved LPs between two additional pricing steps. More...

ogdf::StopwatchCPU	pricingTime_
	The timer for the cpu time spent in pricing. More...

double	primalBound_
	The best known primal bound. More...

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

string	problemName_
	The name of the optimized problem. More...

bool	readParamFromFile_

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

Sub *	root_
	The root node of the enumeration tree. More...

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

Sub *	rRoot_
	The root node of the remaining enumeration tree. More...

ogdf::StopwatchCPU	separationTime_
	The timer for the cpu time spent in the separation. More...

bool	showAverageCutDistance_
	If true then the average distance of the added cutting planes is output every iteration of the cutting plane algorithm. 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	solveApprox_
	If true, then an approximative solver is used to solve linear programs. More...

STATUS	status_
	The current status of the optimization. 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...

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

std::ostream *	treeStream_
	A pointer to the log stream for the VBC-Tool. More...

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

double	varElimEps_
	The tolerance for the elimination of variables by the mode ReducedCost. More...

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

StandardPool< Variable, Constraint > *	varPool_
	The default pool with the variables of the problem formulation. More...

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

Friends
class	FixCand

class	Sub

Additional Inherited Members
Static Public Member Functions inherited from abacus::AbacusRoot
static bool	ascii2bool (const string &str)
	Converts the string str to a boolean value. More...

static bool	endsWith (const string &str, const string &end)
	Returns true if str ends with end, false otherwise. More...

static double	fracPart (double x)
	Returns the absolute value of the fractional part of x. More...

static const char *	onOff (bool value)
	Converts a boolean variable to the strings "on" and "off". More...

Detailed Description

The master of the optimization.

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

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

Definition at line 69 of file master.h.

Member Enumeration Documentation

◆ BRANCHINGSTRAT

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

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

enum abacus::Master::ENUMSTRAT

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

Enumerator
BestFirst	Best-first search, i.e., select the subproblem with best dual bound, i.e., the subproblem having minimal dual bound for a minimization problem, or the subproblem having maximal dual bound for a maximization problem.
BreadthFirst	Breadth-first search, i.e., select the subproblem with minimal level in the enumeration tree.
DepthFirst	Depth-first search, i.e., select the subproblem with maximal level in the enumeration tree.
DiveAndBest	As long as no primal feasible solution is known the next subproblem is selected according to the depth-first search strategy, otherwise the best-first search strategy is applied.

Definition at line 103 of file master.h.

◆ OSISOLVER

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

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

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

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

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

enum abacus::Master::VBCMODE

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

Enumerator
NoVbc	No output for the tree interface.
File	Output for the tree interface is written to a file.
Pipe	Output for the tree interface is pipeed to the standard output.

Definition at line 192 of file master.h.

Constructor & Destructor Documentation

◆ Master() [1/2]

abacus::Master::Master	(	const char *	problemName,
		bool	cutting,
		bool	pricing,
		OptSense::SENSE	optSense = `OptSense::Unknown`,
		double	eps = `1.0e-4`,
		double	machineEps = `1.0e-7`,
		double	infinity = `1.0e30`,
		bool	readParamFromFile = `false`
	)

The constructor.

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

Parameters

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

Member Function Documentation

◆ _createLpMasters()

void abacus::Master::_createLpMasters ( )

private

◆ _deleteLpMasters()

void abacus::Master::_deleteLpMasters ( )

private

◆ _initializeLpParameters()

void abacus::Master::_initializeLpParameters ( )

private

◆ _initializeParameters()

void abacus::Master::_initializeParameters ( )

private

Reads the parameter-file .abacus.

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

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

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

◆ _outputLpStatistics()

void abacus::Master::_outputLpStatistics ( ) const

private

Prints the LP solver specific statistics.

This function is implemented in the file lpif.cc.

◆ _printLpParameters()

void abacus::Master::_printLpParameters ( ) const

private

Prints the LP solver specific parameters.

This function is implemented in the file lpif.cc.

◆ _setDefaultLpParameters()

void abacus::Master::_setDefaultLpParameters ( )

private

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

This function is implemented in the file lpif.cc.

◆ addCons()

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

inlineprivate

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

Definition at line 1239 of file master.h.

◆ addVars()

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

inlineprivate

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

Definition at line 1245 of file master.h.

◆ assignParameters()

virtual void abacus::Master::assignParameters ( )

protectedvirtual

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

◆ bestFirstSearch()

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

protected

Implements the best first search enumeration.

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

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

Parameters

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.

◆ breadthFirstSearch()

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

protected

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

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

Returns: -1 If subproblem s1 has higher priority,; 0 if both subproblems have equal priority,; 1 otherwise.

Parameters

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<Constraint, Variable>* abacus::Master::conPool ( ) const

inline

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

Definition at line 451 of file master.h.

◆ countLp()

void abacus::Master::countLp ( )

inlineprivate

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

Definition at line 1233 of file master.h.

◆ cutPool()

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

inline

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

Definition at line 454 of file master.h.

◆ cutting()

bool abacus::Master::cutting ( ) const

inline

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

Definition at line 431 of file master.h.

◆ dbThreshold() [1/2]

int abacus::Master::dbThreshold ( ) const

inline

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

For further detatails we refer to dbThreshold(int).

Definition at line 693 of file master.h.

◆ dbThreshold() [2/2]

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

inline

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

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

Parameters

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.

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

◆ fixCand()

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

inlineprivate

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

Definition at line 1251 of file master.h.

◆ fixSetByRedCost() [1/2]

bool abacus::Master::fixSetByRedCost ( ) const

inline

Returns: true Then variables are fixed and set by reduced cost criteria.; false Then no variables are fixed or set by reduced cost criteria.

Definition at line 809 of file master.h.

◆ fixSetByRedCost() [2/2]

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

inline

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

Parameters

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.

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

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.

◆ maxConAdd() [1/2]

int abacus::Master::maxConAdd ( ) const

inline

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

Definition at line 832 of file master.h.

◆ maxConAdd() [2/2]

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

inline

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

Definition at line 838 of file master.h.

◆ maxConBuffered() [1/2]

int abacus::Master::maxConBuffered ( ) const

inline

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

Definition at line 841 of file master.h.

◆ maxConBuffered() [2/2]

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

inline

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

Note: This function changes only the default value for subproblems that are activated after its call.

Parameters

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.

◆ maxVarAdd() [1/2]

int abacus::Master::maxVarAdd ( ) const

inline

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

Definition at line 853 of file master.h.

◆ maxVarAdd() [2/2]

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

inline

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

Parameters

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.

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

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<Variable, Constraint>* abacus::Master::varPool ( ) const

inline

Returns a pointer to the default pool storing the variables.

Definition at line 457 of file master.h.

◆ vbcLog() [1/2]

VBCMODE abacus::Master::vbcLog ( ) const

inline

Returns the mode of output for the Vbc-Tool.

Definition at line 938 of file master.h.

◆ vbcLog() [2/2]

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

inline

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

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

Parameters

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.

Friends And Related Function Documentation

◆ FixCand

friend class FixCand

friend

Definition at line 72 of file master.h.

◆ Sub

friend class Sub

friend

Definition at line 71 of file master.h.

Member Data Documentation

◆ BRANCHINGSTRAT_

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

static

Literal values for the enumerators of the corresponding enumeration type.

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

Definition at line 130 of file master.h.

◆ branchingStrategy_

BRANCHINGSTRAT abacus::Master::branchingStrategy_

private

The branching strategy.

Definition at line 1298 of file master.h.

◆ branchingTime_

ogdf::StopwatchCPU abacus::Master::branchingTime_

private

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

Definition at line 1490 of file master.h.

◆ conElimAge_

int abacus::Master::conElimAge_

private

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

Definition at line 1461 of file master.h.

◆ conElimEps_

double abacus::Master::conElimEps_

private

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

Definition at line 1455 of file master.h.

◆ CONELIMMODE_

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

static

Literal values for the enumerators of the corresponding enumeration type.

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

Definition at line 177 of file master.h.

◆ conElimMode_

CONELIMMODE abacus::Master::conElimMode_

private

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

Definition at line 1449 of file master.h.

◆ conPool_

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

private

The default pool with the constraints of the problem formulation.

Definition at line 1312 of file master.h.

◆ cutPool_

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

private

The default pool of dynamically generated constraints.

Definition at line 1316 of file master.h.

◆ cutting_

bool abacus::Master::cutting_

private

If true, then constraints are generated in the optimization.

Definition at line 1334 of file master.h.

◆ dbThreshold_

int abacus::Master::dbThreshold_

private

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

Definition at line 1385 of file master.h.

◆ defaultLpSolver_

OSISOLVER abacus::Master::defaultLpSolver_

private

The default LP-Solver.

Definition at line 1307 of file master.h.

◆ dualBound_

double abacus::Master::dualBound_

private

The best known dual bound.

Definition at line 1325 of file master.h.

◆ eliminateFixedSet_

bool abacus::Master::eliminateFixedSet_

private

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

Definition at line 1431 of file master.h.

◆ enumerationStrategy_

ENUMSTRAT abacus::Master::enumerationStrategy_

private

The enumeration strategy.

Definition at line 1295 of file master.h.

◆ ENUMSTRAT_

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

static

Literal values for the enumerators of the corresponding enumeration type.

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

Definition at line 117 of file master.h.

◆ fixCand_

FixCand* abacus::Master::fixCand_

private

The variables which are candidates for being fixed.

Definition at line 1331 of file master.h.

◆ fixSetByRedCost_

bool abacus::Master::fixSetByRedCost_

private

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

Definition at line 1410 of file master.h.

◆ highestLevel_

int abacus::Master::highestLevel_

private

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

Definition at line 1499 of file master.h.

◆ history_

History* abacus::Master::history_

private

The solution history.

Definition at line 1292 of file master.h.

◆ improveTime_

ogdf::StopwatchCPU abacus::Master::improveTime_

private

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

Definition at line 1484 of file master.h.

◆ lpMasterOsi_

LpMasterOsi* abacus::Master::lpMasterOsi_

private

Definition at line 1309 of file master.h.

◆ lpSolverTime_

ogdf::StopwatchCPU abacus::Master::lpSolverTime_

private

Definition at line 1478 of file master.h.

◆ lpTime_

ogdf::StopwatchCPU abacus::Master::lpTime_

private

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

Definition at line 1476 of file master.h.

◆ maxConAdd_

int abacus::Master::maxConAdd_

private

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

Definition at line 1416 of file master.h.

◆ maxConBuffered_

int abacus::Master::maxConBuffered_

private

The size of the buffer for generated cutting planes.

Definition at line 1419 of file master.h.

◆ maxCowTime_

int64_t abacus::Master::maxCowTime_

private

The maximal available wall-clock time.

Definition at line 1373 of file master.h.

◆ maxCpuTime_

int64_t abacus::Master::maxCpuTime_

private

The maximal available cpu time.

Definition at line 1370 of file master.h.

◆ maxIterations_

int abacus::Master::maxIterations_

private

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

Definition at line 1428 of file master.h.

◆ maxLevel_

int abacus::Master::maxLevel_

private

The maximal level in enumeration tree.

Up to this level subproblems are considered in the enumeration.

Definition at line 1361 of file master.h.

◆ maxNSub_

int abacus::Master::maxNSub_

private

The maximal number of subproblems to be processed.

Up to this number subproblems are considered in the enumeration.

Definition at line 1367 of file master.h.

◆ maxVarAdd_

int abacus::Master::maxVarAdd_

private

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

Definition at line 1422 of file master.h.

◆ maxVarBuffered_

int abacus::Master::maxVarBuffered_

private

The size of the buffer for generated variables.

Definition at line 1425 of file master.h.

◆ minDormantRounds_

int abacus::Master::minDormantRounds_

private

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

Definition at line 1392 of file master.h.

◆ nAddCons_

int abacus::Master::nAddCons_

private

The total number of added constraints.

Definition at line 1505 of file master.h.

◆ nAddVars_

int abacus::Master::nAddVars_

private

The total number of added variables.

Definition at line 1511 of file master.h.

◆ nBranchingVariableCandidates_

int abacus::Master::nBranchingVariableCandidates_

private

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

Definition at line 1301 of file master.h.

◆ newRootReOptimize_

bool abacus::Master::newRootReOptimize_

private

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

Definition at line 1437 of file master.h.

◆ nFixed_

int abacus::Master::nFixed_

private

The total number of fixed variables.

Definition at line 1502 of file master.h.

◆ nLp_

int abacus::Master::nLp_

private

The number of solved LPs.

Definition at line 1496 of file master.h.

◆ nNewRoot_

int abacus::Master::nNewRoot_

private

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

Definition at line 1517 of file master.h.

◆ nRemCons_

int abacus::Master::nRemCons_

private

The total number of removed constraints.

Definition at line 1508 of file master.h.

◆ nRemVars_

int abacus::Master::nRemVars_

private

The total number of removed variables.

Definition at line 1514 of file master.h.

◆ nStrongBranchingIterations_

int abacus::Master::nStrongBranchingIterations_

private

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

Definition at line 1304 of file master.h.

◆ nSub_

int abacus::Master::nSub_

private

The number of generated subproblems.

Definition at line 1493 of file master.h.

◆ nSubSelected_

int abacus::Master::nSubSelected_

private

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

Definition at line 1343 of file master.h.

◆ objInteger_

bool abacus::Master::objInteger_

private

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

Definition at line 1376 of file master.h.

◆ openSub_

OpenSub* abacus::Master::openSub_

private

The set of open subproblems.

Definition at line 1289 of file master.h.

◆ optimumFileName_

string abacus::Master::optimumFileName_

private

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

Definition at line 1440 of file master.h.

◆ optSense_

OptSense abacus::Master::optSense_

private

The sense of the objective function.

Definition at line 1280 of file master.h.

◆ OSISOLVER_

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

static

Array for the literal values for possible Osi solvers.

Definition at line 212 of file master.h.

◆ pbMode_

PRIMALBOUNDMODE abacus::Master::pbMode_

private

The mode of the primal bound initialization.

Definition at line 1395 of file master.h.

◆ pricing_

bool abacus::Master::pricing_

private

If true, then variables are generated in the optimization.

Definition at line 1337 of file master.h.

◆ pricingFreq_

int abacus::Master::pricingFreq_

private

The number of solved LPs between two additional pricing steps.

Definition at line 1398 of file master.h.

◆ pricingTime_

ogdf::StopwatchCPU abacus::Master::pricingTime_

private

The timer for the cpu time spent in pricing.

Definition at line 1487 of file master.h.

◆ primalBound_

double abacus::Master::primalBound_

private

The best known primal bound.

Definition at line 1322 of file master.h.

◆ PRIMALBOUNDMODE_

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

static

Literal values for the enumerators of the corresponding enumeration type.

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

Definition at line 150 of file master.h.

◆ printLP_

bool abacus::Master::printLP_

private

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

Definition at line 1413 of file master.h.

◆ problemName_

string abacus::Master::problemName_

private

The name of the optimized problem.

Definition at line 1275 of file master.h.

◆ readParamFromFile_

bool abacus::Master::readParamFromFile_

private

Definition at line 1277 of file master.h.

◆ requiredGuarantee_

double abacus::Master::requiredGuarantee_

private

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

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

Definition at line 1355 of file master.h.

◆ root_

Sub* abacus::Master::root_

private

The root node of the enumeration tree.

Definition at line 1283 of file master.h.

◆ rootDualBound_

double abacus::Master::rootDualBound_

private

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

Definition at line 1328 of file master.h.

◆ rRoot_

Sub* abacus::Master::rRoot_

private

The root node of the remaining enumeration tree.

Definition at line 1286 of file master.h.

◆ separationTime_

ogdf::StopwatchCPU abacus::Master::separationTime_

private

The timer for the cpu time spent in the separation.

Definition at line 1481 of file master.h.

◆ showAverageCutDistance_

bool abacus::Master::showAverageCutDistance_

private

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

Definition at line 1446 of file master.h.

◆ skipFactor_

int abacus::Master::skipFactor_

private

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

Definition at line 1401 of file master.h.

◆ SKIPPINGMODE_

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

static

Literal values for the enumerators of the corresponding enumeration type.

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

Definition at line 163 of file master.h.

◆ skippingMode_

SKIPPINGMODE abacus::Master::skippingMode_

private

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

Definition at line 1407 of file master.h.

◆ solveApprox_

bool abacus::Master::solveApprox_

private

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

Definition at line 1340 of file master.h.

◆ STATUS_

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

static

Literal values for the enumerators of the corresponding enumeration type.

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

Definition at line 99 of file master.h.

◆ status_

STATUS abacus::Master::status_

private

The current status of the optimization.

Definition at line 1467 of file master.h.

◆ tailOffNLp_

int abacus::Master::tailOffNLp_

private

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

Definition at line 1379 of file master.h.

◆ tailOffPercent_

double abacus::Master::tailOffPercent_

private

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

Definition at line 1382 of file master.h.

◆ totalCowTime_

ogdf::StopwatchWallClock abacus::Master::totalCowTime_

private

The timer for the total elapsed time.

Definition at line 1470 of file master.h.

◆ totalTime_

ogdf::StopwatchCPU abacus::Master::totalTime_

private

The timer for the total cpu time for the optimization.

Definition at line 1473 of file master.h.

◆ treeStream_

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

private

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

Definition at line 1349 of file master.h.

◆ varElimAge_

int abacus::Master::varElimAge_

private

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

Definition at line 1464 of file master.h.

◆ varElimEps_

double abacus::Master::varElimEps_

private

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

Definition at line 1458 of file master.h.

◆ VARELIMMODE_

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

static

Literal values for the enumerators of the corresponding enumeration type.

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

Definition at line 189 of file master.h.

◆ varElimMode_

VARELIMMODE abacus::Master::varElimMode_

private

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

Definition at line 1452 of file master.h.

◆ varPool_

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

private

The default pool with the variables of the problem formulation.

Definition at line 1319 of file master.h.

◆ VbcLog_

VBCMODE abacus::Master::VbcLog_

private

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

Definition at line 1346 of file master.h.

◆ VBCMODE_

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

static

Literal values for the enumerators of the corresponding enumeration type.

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

Definition at line 202 of file master.h.

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

include/ogdf/lib/abacus/master.h

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.

OpenGraph DrawingFramework

Public Types

Public Member Functions

Static Public Attributes

Protected Member Functions

Private Member Functions

Private Attributes

Friends

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

◆ BRANCHINGSTRAT

◆ CONELIMMODE

◆ ENUMSTRAT

◆ OSISOLVER

◆ PRIMALBOUNDMODE

◆ SKIPPINGMODE

◆ STATUS

◆ VARELIMMODE

◆ VBCMODE

Constructor & Destructor Documentation

◆ Master() [1/2]

◆ ~Master()

◆ Master() [2/2]

Member Function Documentation

◆ _createLpMasters()

◆ _deleteLpMasters()

◆ _initializeLpParameters()

◆ _initializeParameters()

◆ _outputLpStatistics()

◆ _printLpParameters()

◆ _setDefaultLpParameters()

◆ addCons()

◆ addVars()

◆ assignParameters()

◆ bestFirstSearch()

◆ betterDual()

◆ betterPrimal()

◆ branchingStrategy() [1/2]

◆ branchingStrategy() [2/2]

◆ branchingTime()

◆ breadthFirstSearch()

◆ check()

◆ conElimAge() [1/2]

◆ conElimAge() [2/2]

◆ conElimEps() [1/2]

◆ conElimEps() [2/2]

◆ conElimMode() [1/2]

◆ conElimMode() [2/2]

◆ conPool()

◆ countLp()

◆ cutPool()

◆ cutting()

◆ dbThreshold() [1/2]

◆ dbThreshold() [2/2]

◆ defaultLpSolver() [1/2]

◆ defaultLpSolver() [2/2]

◆ delayedBranching()

◆ depthFirstSearch()

◆ diveAndBestFirstSearch()

◆ dualBound() [1/2]

◆ dualBound() [2/2]

◆ eliminateFixedSet() [1/2]

◆ eliminateFixedSet() [2/2]

◆ enumerationStrategy() [1/3]

◆ enumerationStrategy() [2/3]

◆ enumerationStrategy() [3/3]

◆ equalSubCompare()

◆ feasibleFound()

◆ firstSub()

◆ fixCand()

◆ fixSetByRedCost() [1/2]

◆ fixSetByRedCost() [2/2]

◆ guarantee()

◆ guaranteed()

◆ highestLevel()

◆ history()

◆ improveTime()

◆ initializeOptimization()

◆ initializeOptSense()

Open
Graph Drawing
Framework