|
|||
|
|
|
|||
|
|
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. | |
| virtual | ~Master () |
| The destructor. | |
| BRANCHINGSTRAT | branchingStrategy () const |
| Returns the branching strategy. | |
| void | branchingStrategy (BRANCHINGSTRAT strat) |
| Changes the branching strategy to strat. | |
| const ogdf::StopwatchCPU * | branchingTime () const |
| Returns a pointer to the timer measuring the cpu time spent in finding and selecting the branching rules. | |
| bool | check () const |
| Can be used to control the correctness of the optimization if the value of the optimum solution has been loaded. | |
| int | conElimAge () const |
| Returns the age for the elimination of constraints. | |
| void | conElimAge (int age) |
| Changes the age for the elimination of constraints to age. | |
| double | conElimEps () const |
| Returns the zero tolerance for the elimination of constraints by the slack criterion. | |
| void | conElimEps (double eps) |
| Changes the tolerance for the elimination of constraints by the slack criterion to eps. | |
| CONELIMMODE | conElimMode () const |
| Returns the mode for the elimination of constraints. | |
| void | conElimMode (CONELIMMODE mode) |
| Changes the constraint elimination mode to mode. | |
| StandardPool< Constraint, Variable > * | conPool () const |
| Returns a pointer to the default pool storing the constraints of the problem formulation. | |
| StandardPool< Constraint, Variable > * | cutPool () const |
| Returns a pointer to the default pool for the generated cutting planes. | |
| bool | cutting () const |
| int | dbThreshold () const |
| Returns the number of optimizations of a subproblem until sons are created. | |
| void | dbThreshold (int threshold) |
| Sets the number of optimizations of a subproblem until sons are created in Sub::branching(). | |
| OSISOLVER | defaultLpSolver () const |
| returns the Lp Solver. | |
| void | defaultLpSolver (OSISOLVER osiSolver) |
| Changes the default Lp solver to osiSolver. | |
| bool | delayedBranching (int nOpt) const |
| Returns true if the number of optimizations nOpt of a subproblem exceeds the delayed branching threshold, false otherwise. | |
| bool | eliminateFixedSet () const |
| void | eliminateFixedSet (bool turnOn) |
| Turns the elimination of fixed and set variables on or off. | |
| ENUMSTRAT | enumerationStrategy () const |
| Returns the enumeration strategy. | |
| 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. | |
| void | enumerationStrategy (ENUMSTRAT strat) |
| Changes the enumeration strategy to strat. | |
| bool | fixSetByRedCost () const |
| void | fixSetByRedCost (bool on) |
| Turns fixing and setting variables by reduced cost on or off. | |
| double | guarantee () const |
| Can be used to access the guarantee which can be given for the best known feasible solution. | |
| bool | guaranteed () const |
| Can be used to check if the guarantee requirements are fulfilled. | |
| int | highestLevel () const |
| Returns the highest level in the tree which has been reached during the implicit enumeration. | |
| History * | history () const |
| Returns a pointer to the object storing the solution history of this branch and cut problem. | |
| 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. | |
| 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. | |
| LpMasterOsi * | lpMasterOsi () const |
| const ogdf::StopwatchCPU * | lpSolverTime () const |
| Return a pointer to the timer measuring the cpu time required by the LP solver. | |
| const ogdf::StopwatchCPU * | lpTime () const |
| Returns a pointer to the timer measuring the cpu time spent in members of the LP-interface. | |
| int | maxConAdd () const |
| Returns the maximal number of constraints which should be added in every iteration of the cutting plane algorithm. | |
| void | maxConAdd (int max) |
| Sets the maximal number of constraints that are added in an iteration of the cutting plane algorithm. | |
| int | maxConBuffered () const |
| Returns the size of the buffer for generated constraints in the cutting plane algorithm. | |
| void | maxConBuffered (int max) |
| Changes the maximal number of constraints that are buffered in an iteration of the cutting plane algorithm. | |
| int64_t | maxCowTime () const |
| Returns the maximal wall-clock time (in seconds) which can be used by the optimization. | |
| void | maxCowTime (const string &t) |
| Sets the maximally allowed wall-clock time for the optimization to t. | |
| void | maxCowTime (int64_t seconds) |
| Sets the maximally allowed wall-clock time to seconds. | |
| string | maxCowTimeAsString () const |
Returns the maximal wall-clock time (as string hh:mm:ss) which can be used by the optimization. | |
| int64_t | maxCpuTime () const |
| Returns the maximal cpu time (in seconds) which can be used by the optimization. | |
| void | maxCpuTime (const string &t) |
| Sets the maximally allowed cpu time for the optimization to t. | |
| void | maxCpuTime (int hour, int min, int sec) |
| Sets the maximally allowed cpu time for the optimization to hour, min, sec. | |
| void | maxCpuTime (int64_t seconds) |
| Sets the maximally allowed cpu time to seconds. | |
| string | maxCpuTimeAsString () const |
Returns the maximal cpu time (as string hh:mm:ss) which can be used by the optimization. | |
| int | maxIterations () const |
| Returns the maximal number of iterations per subproblem optimization (-1 means no iteration limit). | |
| void | maxIterations (int max) |
| Changes the default value for the maximal number of iterations of the optimization of a subproblem. | |
| int | maxLevel () const |
| Returns the maximal depth up to which the enumeration should be performed. | |
| void | maxLevel (int ml) |
| This version of the function maxLevel() changes the maximal enumeration depth. | |
| int | maxNSub () const |
| Returns the maximal number of subproblems to be processed. | |
| void | maxNSub (int ml) |
| Changes the maximal number of subproblems to ml. | |
| int | maxVarAdd () const |
| Returns the maximal number of variables which should be added in the column generation algorithm. | |
| void | maxVarAdd (int max) |
| Changes the maximal number of variables that are added in an iteration of the subproblem optimization. | |
| int | maxVarBuffered () const |
| Returns the size of the buffer for the variables generated in the column generation algorithm. | |
| void | maxVarBuffered (int max) |
| Changes the maximal number of variables that are buffered in an iteration of the subproblem optimization. | |
| int | minDormantRounds () const |
| Returns the maximal number of rounds, i.e., number of subproblem optimizations, a subproblem is dormant. | |
| void | minDormantRounds (int nRounds) |
| Sets the number of rounds a subproblem should stay dormant to nRounds. | |
| int | nBranchingVariableCandidates () const |
| Returns the number of variables that should be tested for the selection of the branching variable. | |
| void | nBranchingVariableCandidates (int n) |
| Sets the number of tested branching variable candidates to n. | |
| bool | newRootReOptimize () const |
| void | newRootReOptimize (bool on) |
| Turns the reoptimization of new root nodes of the remaining branch and bound tree on or off. | |
| int | nLp () const |
| Returns the number of optimized linear programs (only LP-relaxations). | |
| int | nNewRoot () const |
| Returns the number of root changes of the remaining branch-and-cut tree. | |
| int | nStrongBranchingIterations () const |
| The number of simplex iterations that are performed when testing candidates for branching variables within strong branching. | |
| void | nStrongBranchingIterations (int n) |
| Sets the number of simplex iterations that are performed when testing candidates for branching variables within strong branching. | |
| int | nSub () const |
| returns the number of generated subproblems. | |
| int | nSubSelected () const |
| Returns the number of subproblems which have already been selected from the set of open subproblems. | |
| bool | objInteger () const |
| If true then we assume that all feasible solutions have integral objective function values. | |
| void | objInteger (bool b) |
| Sets the assumption that the objective function values of all feasible solutions are integer. | |
| OpenSub * | openSub () const |
| Returns a pointer to the set of open subproblems. | |
| STATUS | optimize () |
| Performs the optimization by branch-and-bound. | |
| const string & | optimumFileName () const |
| Returns the name of the file that stores the optimum solutions. | |
| void | optimumFileName (const char *name) |
| Changes the name of the file in which the value of the optimum solution is searched. | |
| const OptSense * | optSense () const |
| Returns a pointer to the object holding the optimization sense of the problem. | |
| virtual void | output () const |
| Does nothing but can be redefined in derived classes for output before the timing statistics. | |
| PRIMALBOUNDMODE | pbMode () const |
| Returns the mode of the primal bound initialization. | |
| void | pbMode (PRIMALBOUNDMODE mode) |
| Sets the mode of the primal bound initialization to mode. | |
| bool | pricing () const |
| int | pricingFreq () const |
| Returns the number of linear programs being solved between two additional pricing steps. | |
| void | pricingFreq (int f) |
| Sets the number of linear programs being solved between two additional pricing steps to f. | |
| const ogdf::StopwatchCPU * | pricingTime () const |
| Returns a pointer to the timer measuring the cpu time spent in pricing. | |
| void | printGuarantee () const |
| Writes the guarantee nicely formated on the output stream associated with this object. | |
| bool | printLP () const |
| void | printLP (bool on) |
| Turns the output of the linear program in every iteration on or off. | |
| void | printParameters () const |
| Writes all parameters of the class Master together with their values to the global output stream. | |
| const string & | problemName () const |
| Returns the name of the instance being optimized (as specified in the constructor of this class). | |
| double | requiredGuarantee () const |
| The guarantee specification for the optimization. | |
| void | requiredGuarantee (double g) |
| Changes the guarantee specification tp g. | |
| Sub * | root () const |
| Can be used to access the root node of the branch-and-bound tree. | |
| 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. | |
| virtual bool | setSolverParameters (OsiSolverInterface *interface, bool solverIsApprox) |
| Sets solver specific parameters. | |
| 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. | |
| int | skipFactor () const |
| Returns the frequency of subproblems in which constraints or variables should be generated. | |
| void | skipFactor (int f) |
| Sets the frequency for constraint and variable generation to f. | |
| SKIPPINGMODE | skippingMode () const |
| Returns the skipping strategy. | |
| void | skippingMode (SKIPPINGMODE mode) |
| Sets the skipping strategy to mode. | |
| bool | solveApprox () const |
| True, if an approximative solver should be used. | |
| STATUS | status () const |
| Returns the status of the Master. | |
| int | tailOffNLp () const |
| Returns the number of linear programs considered in the tailing off analysis. | |
| void | tailOffNLp (int n) |
| Sets the number of linear programs considered in the tailing off analysis to n. | |
| double | tailOffPercent () const |
| Returns the minimal change of the dual bound for the tailing off analysis in percent. | |
| void | tailOffPercent (double p) |
| Sets the minimal change of the dual bound for the tailing off analysis to p. | |
| const ogdf::StopwatchWallClock * | totalCowTime () const |
| Returns a pointer to the timer measuring the total wall clock time. | |
| const ogdf::StopwatchCPU * | totalTime () const |
| returns a pointer to the timer measuring the total cpu time for the optimization. | |
| int | varElimAge () const |
| Returns the age for the elimination of variables by the reduced cost criterion. | |
| void | varElimAge (int age) |
| Changes the age for the elimination of variables by the reduced cost criterion to age. | |
| double | varElimEps () const |
| Returns the zero tolerance for the elimination of variables by the reduced cost criterion. | |
| void | varElimEps (double eps) |
| Changes the tolerance for the elimination of variables by the reduced cost criterion to eps. | |
| VARELIMMODE | varElimMode () const |
| Returns the mode for the elimination of variables. | |
| void | varElimMode (VARELIMMODE mode) |
| Changes the variable elimination mode to mode. | |
| StandardPool< Variable, Constraint > * | varPool () const |
| Returns a pointer to the default pool storing the variables. | |
| VBCMODE | vbcLog () const |
| Returns the mode of output for the Vbc-Tool. | |
| void | vbcLog (VBCMODE mode) |
| Changes the mode of output for the Vbc-Tool to mode. | |
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. | |
| double | upperBound () const |
| Returns the value of the global upper bound. | |
| double | primalBound () const |
| Returns the value of the primal bound. | |
| void | primalBound (double x) |
| Sets the primal bound to x and makes a new entry in the solution history. | |
| double | dualBound () const |
| Returns the value of the dual bound. | |
| void | dualBound (double x) |
| Sets the dual bound to x and makes a new entry in the solution history. | |
| bool | betterDual (double x) const |
| Returns true if x is better than the best known dual bound; false otherwise. | |
| bool | primalViolated (double x) const |
| Can be used to compare a value with the one of the best known primal bound. | |
| bool | betterPrimal (double x) const |
| Can be used to check if a value is better than the best know primal bound. | |
| double | rootDualBound () const |
| Returns the dual bound at the root node. | |
| bool | feasibleFound () const |
| We use this function, e.g., to adapt the enumeration strategy in the DiveAndBest-Strategy. | |
| Public Member Functions inherited from abacus::AbacusGlobal | |
| AbacusGlobal (double eps=1.0e-4, double machineEps=1.0e-7, double infinity=1.0e32) | |
| The constructor. | |
| virtual | ~AbacusGlobal () |
| The destructor. | |
| void | assignParameter (bool ¶m, const char *name) const |
| See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. | |
| void | assignParameter (bool ¶m, const char *name, bool defVal) const |
| See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. | |
| void | assignParameter (char ¶m, const char *name, const char *feasible, char defVal) const |
| See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. | |
| void | assignParameter (char ¶m, const char *name, const char *feasible=nullptr) const |
| See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. | |
| void | assignParameter (double ¶m, const char *name, double minVal, double maxVal) const |
| See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. | |
| void | assignParameter (double ¶m, const char *name, double minVal, double maxVal, double defVal) const |
| See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. | |
| void | assignParameter (int ¶m, const char *name, int minVal, int maxVal) const |
| Searches for parameter name in the parameter table and returns its value in param. | |
| void | assignParameter (int ¶m, const char *name, int minVal, int maxVal, int defVal) const |
| See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. | |
| void | assignParameter (string ¶m, const char *name, unsigned nFeasible, const char *feasible[], const char *defVal) const |
| See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. | |
| void | assignParameter (string ¶m, const char *name, unsigned nFeasible=0, const char *feasible[]=nullptr) const |
| See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. | |
| void | assignParameter (unsigned ¶m, const char *name, unsigned minVal, unsigned maxVal) const |
| See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. | |
| void | assignParameter (unsigned ¶m, const char *name, unsigned minVal, unsigned maxVal, unsigned defVal) const |
| See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. | |
| double | eps () const |
| Returns the zero tolerance. | |
| void | eps (double e) |
| Sets the zero tolerance to e. | |
| bool | equal (double x, double y) const |
| Returns whether the absolute difference between x and y is less than the machine dependent zero tolerance. | |
| int | findParameter (const char *name, const char *feasible) const |
| See AbacusGlobal::findParameter(const char *name, unsigned nFeasible, const int *feasible) for description. | |
| int | findParameter (const char *name, unsigned nFeasible, const char *feasible[]) const |
| See AbacusGlobal::findParameter(const char *name, unsigned nFeasible, const int *feasible) for description. | |
| int | findParameter (const char *name, unsigned nFeasible, const int *feasible) const |
| Searches for parameter name in the parameter table. | |
| int | getParameter (const char *name, bool ¶m) const |
| int | getParameter (const char *name, char ¶m) const |
| int | getParameter (const char *name, double ¶m) const |
| int | getParameter (const char *name, int ¶m) const |
| Searches for parameter name in the parameter table and returns its value in param. | |
| int | getParameter (const char *name, string ¶m) const |
| int | getParameter (const char *name, unsigned int ¶m) const |
| double | infinity () const |
| Provides a floating point value of "infinite" size. | |
| void | infinity (double x) |
| Sets the "infinite value" to x. | |
| void | insertParameter (const char *name, const char *value) |
| Inserts parameter name with value value into the parameter table. | |
| bool | isInfinity (double x) const |
| Returns true if x is regarded as "infinite" large, false otherwise. | |
| bool | isInteger (double x) const |
| Returns whether the value x differs at most by the machine dependent zero tolerance from an integer value. | |
| bool | isInteger (double x, double eps) const |
| Returns whether the value x differs at most by eps from an integer value. | |
| bool | isMinusInfinity (double x) const |
| Returns true if x is regarded as infinite small, false otherwise. | |
| double | machineEps () const |
| Provides a machine dependent zero tolerance. | |
| void | machineEps (double e) |
| Sets the machine dependent zero tolerance to e. | |
| void | readParameters (const string &fileName) |
| Opens the parameter file fileName, reads all parameters, and inserts them in the parameter table. | |
| Public Member Functions inherited from abacus::AbacusRoot | |
| virtual | ~AbacusRoot () |
| The destructor. | |
Static Public Attributes | |
| static const char * | BRANCHINGSTRAT_ [] |
| Literal values for the enumerators of the corresponding enumeration type. | |
| static const char * | CONELIMMODE_ [] |
| Literal values for the enumerators of the corresponding enumeration type. | |
| static const char * | ENUMSTRAT_ [] |
| Literal values for the enumerators of the corresponding enumeration type. | |
| static const char * | OSISOLVER_ [] |
| Array for the literal values for possible Osi solvers. | |
| static const char * | PRIMALBOUNDMODE_ [] |
| Literal values for the enumerators of the corresponding enumeration type. | |
| static const char * | SKIPPINGMODE_ [] |
| Literal values for the enumerators of the corresponding enumeration type. | |
| static const char * | STATUS_ [] |
| Literal values for the enumerators of the corresponding enumeration type. | |
| static const char * | VARELIMMODE_ [] |
| Literal values for the enumerators of the corresponding enumeration type. | |
| static const char * | VBCMODE_ [] |
| Literal values for the enumerators of the corresponding enumeration type. | |
Protected Member Functions | |
| virtual void | assignParameters () |
| Assigns the parameters that were read from a file to the member variables of the master. | |
| int | bestFirstSearch (const Sub *s1, const Sub *s2) const |
| Implements the best first search enumeration. | |
| 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. | |
| 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. | |
| 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. | |
| 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. | |
| virtual Sub * | firstSub ()=0 |
| Should return a pointer to the first subproblem of the optimization, i.e., the root node of the enumeration tree. | |
| virtual void | initializeOptimization () |
| The default implementation of initializeOptimization() does nothing. | |
| 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. | |
| virtual void | initializeParameters () |
| Is only a dummy. | |
| 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. | |
| 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. | |
| virtual void | terminateOptimization () |
| The default implementation of terminateOptimization() does nothing. | |
Private Member Functions | |
| Master (const Master &rhs) | |
| void | _createLpMasters () |
| void | _deleteLpMasters () |
| void | _initializeLpParameters () |
| void | _initializeParameters () |
Reads the parameter-file .abacus. | |
| void | _outputLpStatistics () const |
| Prints the LP solver specific statistics. | |
| void | _printLpParameters () const |
| Prints the LP solver specific parameters. | |
| void | _setDefaultLpParameters () |
Initializes the LP solver specific default parameters if they are not read from .abacus. | |
| void | addCons (int n) |
| Increments the counter for the total number of added constraints by n. | |
| void | addVars (int n) |
| Increments the counter for the total number of added variables by n. | |
| void | countLp () |
| Increments the counter for linear programs and should be called in each optimization call of the LP-relaxation. | |
| FixCand * | fixCand () const |
| Returns a pointer to the object storing the variables which are candidates for being fixed. | |
| int | initLP () |
| void | newFixed (int n) |
| Increments the counter of the number of fixed variables by n. | |
| void | newSub (int level) |
| Registers a new subproblem which is on level level in enumeration tree. | |
| const Master & | operator= (const Master &rhs) |
| void | removeCons (int n) |
| Increments the counter for the total number of removed constraints by n. | |
| void | removeVars (int n) |
| Increments the counter for the total number of removed variables by n. | |
| void | rootDualBound (double x) |
| Updates the final dual bound of the root node. | |
| void | rRoot (Sub *newRoot, bool reoptimize) |
| Sets the root of the remaining branch-and-cut tree to newRoot. | |
| Sub * | select () |
| Returns a pointer to an open subproblem for further processing. | |
| void | status (STATUS stat) |
| Sets the status of the Master. | |
| void | theFuture () |
| void | treeInterfaceLowerBound (double lb) const |
| Passes the new lower bound lb to the Tree Interface. | |
| 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. | |
| 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. | |
| void | treeInterfacePaintNode (int id, int color) const |
| Assigns the color to the subproblem sub in the Tree Interface. | |
| void | treeInterfaceUpperBound (double ub) const |
| Passes the new upper bound ub to the Tree Interface. | |
| void | writeTreeInterface (const string &info, bool time=true) const |
| Writes the string info to the stream associated with the Tree Interface. | |
Private Attributes | |
| BRANCHINGSTRAT | branchingStrategy_ |
| The branching strategy. | |
| ogdf::StopwatchCPU | branchingTime_ |
| The timer for the cpu time spent in determining the branching rules. | |
| int | conElimAge_ |
| The number of iterations an elimination criterion must be satisfied until a constraint can be removed. | |
| double | conElimEps_ |
| The tolerance for the elimination of constraints by the mode NonBinding/. | |
| CONELIMMODE | conElimMode_ |
| The way constraints are automatically eliminated in the cutting plane algorithm. | |
| StandardPool< Constraint, Variable > * | conPool_ |
| The default pool with the constraints of the problem formulation. | |
| StandardPool< Constraint, Variable > * | cutPool_ |
| The default pool of dynamically generated constraints. | |
| bool | cutting_ |
| If true, then constraints are generated in the optimization. | |
| int | dbThreshold_ |
| The number of optimizations of an Sub until branching is performed. | |
| OSISOLVER | defaultLpSolver_ |
| The default LP-Solver. | |
| double | dualBound_ |
| The best known dual bound. | |
| bool | eliminateFixedSet_ |
| If true, then nonbasic fixed and set variables are eliminated. | |
| ENUMSTRAT | enumerationStrategy_ |
| The enumeration strategy. | |
| FixCand * | fixCand_ |
| The variables which are candidates for being fixed. | |
| bool | fixSetByRedCost_ |
| If true, then variables are fixed and set by reduced cost criteria. | |
| int | highestLevel_ |
| The highest level which has been reached in the enumeration tree. | |
| History * | history_ |
| The solution history. | |
| ogdf::StopwatchCPU | improveTime_ |
| The timer for the cpu time spent in the heuristics for the computation of feasible solutions. | |
| LpMasterOsi * | lpMasterOsi_ |
| ogdf::StopwatchCPU | lpSolverTime_ |
| ogdf::StopwatchCPU | lpTime_ |
| The timer for the cpu time spent in the LP-interface. | |
| int | maxConAdd_ |
| The maximal number of added constraints per iteration of the cutting plane algorithm. | |
| int | maxConBuffered_ |
| The size of the buffer for generated cutting planes. | |
| int64_t | maxCowTime_ |
| The maximal available wall-clock time. | |
| int64_t | maxCpuTime_ |
| The maximal available cpu time. | |
| int | maxIterations_ |
| The maximal number of iterations of the cutting plane/column generation algorithm in the subproblem. | |
| int | maxLevel_ |
| The maximal level in enumeration tree. | |
| int | maxNSub_ |
| The maximal number of subproblems to be processed. | |
| int | maxVarAdd_ |
| The maximal number of added variables per iteration of the column generation algorithm. | |
| int | maxVarBuffered_ |
| The size of the buffer for generated variables. | |
| 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. | |
| int | nAddCons_ |
| The total number of added constraints. | |
| int | nAddVars_ |
| The total number of added variables. | |
| int | nBranchingVariableCandidates_ |
| The number of candidates that are evaluated for branching on variables. | |
| 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. | |
| int | nFixed_ |
| The total number of fixed variables. | |
| int | nLp_ |
| The number of solved LPs. | |
| int | nNewRoot_ |
| The number of changes of the root of the remaining branch-and-bound tree. | |
| int | nRemCons_ |
| The total number of removed constraints. | |
| int | nRemVars_ |
| The total number of removed variables. | |
| int | nStrongBranchingIterations_ |
| The number of simplex iterations that are performed when testing a branching variable candidate within strong branching. | |
| int | nSub_ |
| The number of generated subproblems. | |
| int | nSubSelected_ |
| The number of subproblems already selected from the list of open subproblems. | |
| bool | objInteger_ |
| true, if all objective function values of feasible solutions are assumed to be integer. | |
| OpenSub * | openSub_ |
| The set of open subproblems. | |
| string | optimumFileName_ |
| The name of a file storing a list of optimum solutions of problem instances. | |
| OptSense | optSense_ |
| The sense of the objective function. | |
| PRIMALBOUNDMODE | pbMode_ |
| The mode of the primal bound initialization. | |
| bool | pricing_ |
| If true, then variables are generated in the optimization. | |
| int | pricingFreq_ |
| The number of solved LPs between two additional pricing steps. | |
| ogdf::StopwatchCPU | pricingTime_ |
| The timer for the cpu time spent in pricing. | |
| double | primalBound_ |
| The best known primal bound. | |
| bool | printLP_ |
| If true, then the linear program is output every iteration. | |
| string | problemName_ |
| The name of the optimized problem. | |
| bool | readParamFromFile_ |
| double | requiredGuarantee_ |
| The guarantee in percent which should be reached when the optimization stops. | |
| Sub * | root_ |
| The root node of the enumeration tree. | |
| double | rootDualBound_ |
| The best known dual bound at the end of the optimization of the root node. | |
| Sub * | rRoot_ |
| The root node of the remaining enumeration tree. | |
| ogdf::StopwatchCPU | separationTime_ |
| The timer for the cpu time spent in the separation. | |
| bool | showAverageCutDistance_ |
| If true then the average distance of the added cutting planes is output every iteration of the cutting plane algorithm. | |
| int | skipFactor_ |
| The frequency constraints or variables are generated depending on the skipping mode. | |
| SKIPPINGMODE | skippingMode_ |
| Either constraints are generated only every skipFactor_ subproblem (SkipByNode) only every skipFactor_ level (SkipByLevel). | |
| bool | solveApprox_ |
| If true, then an approximative solver is used to solve linear programs. | |
| STATUS | status_ |
| The current status of the optimization. | |
| int | tailOffNLp_ |
| The number of LP-iterations for the tailing off analysis. | |
| double | tailOffPercent_ |
| The minimal change of the LP-value on the tailing off analysis. | |
| ogdf::StopwatchWallClock | totalCowTime_ |
| The timer for the total elapsed time. | |
| ogdf::StopwatchCPU | totalTime_ |
| The timer for the total cpu time for the optimization. | |
| std::ostream * | treeStream_ |
| A pointer to the log stream for the VBC-Tool. | |
| int | varElimAge_ |
| The number of iterations an elimination criterion must be satisfied until a variable can be removed. | |
| double | varElimEps_ |
| The tolerance for the elimination of variables by the mode ReducedCost. | |
| VARELIMMODE | varElimMode_ |
| The way variables are automatically eliminated in the column generation algorithm. | |
| StandardPool< Variable, Constraint > * | varPool_ |
| The default pool with the variables of the problem formulation. | |
| VBCMODE | VbcLog_ |
| Ouput for the Tree Interface is generated depending on the value of this variable. | |
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. | |
| static bool | endsWith (const string &str, const string &end) |
| Returns true if str ends with end, false otherwise. | |
| static double | fracPart (double x) |
| Returns the absolute value of the fractional part of x. | |
| static const char * | onOff (bool value) |
| Converts a boolean variable to the strings "on" and "off". | |
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.
This enumeration defines the two currently implemented branching variable selection strategies.
The enumeration defining the different enumeration strategies for the branch and bound algorithm.
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 | |
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.
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(). |
| 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().
| 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). |
|
virtual |
The destructor.
Reimplemented in ogdf::MinSteinerTreeDirectedCut< T >::Master.
|
private |
|
private |
|
private |
|
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
|
private |
Prints the LP solver specific statistics.
This function is implemented in the file lpif.cc.
|
private |
Prints the LP solver specific parameters.
This function is implemented in the file lpif.cc.
|
private |
Initializes the LP solver specific default parameters if they are not read from .abacus.
This function is implemented in the file lpif.cc.
Assigns the parameters that were read from a file to the member variables of the master.
Implements the best first search enumeration.
If the bounds of both subproblems are equal, then the subproblems are compared with the function equalSubCompare().
| s1 | A subproblem. |
| s2 | A subproblem. |
Returns true if x is better than the best known dual bound; false otherwise.
| x | The value being compared with the best know dual bound. |
Can be used to check if a value is better than the best know primal bound.
| x | The value compared with the primal bound. |
|
inline |
|
inline |
|
inline |
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.
| s1 | The first subproblem. |
| s2 | The second subproblem. |
| 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.
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inlineprivate |
|
inline |
|
inline |
|
inline |
Returns the number of optimizations of a subproblem until sons are created.
For further detatails we refer to dbThreshold(int).
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.
| threshold | The new value of the delayed branching threshold. |
|
inline |
Returns true if the number of optimizations nOpt of a subproblem exceeds the delayed branching threshold, false otherwise.
| nOpt | The number of optimizations of a subproblem. |
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().
| s1 | The first subproblem. |
| s2 | The second subproblem. |
Performs depth-first search until a feasible solution is found, then the search process is continued with best-first search.
| s1 | The first subproblem. |
| s2 | The second subproblem. |
|
inline |
Returns the value of the dual bound.
I.e., the upperBound() for a maximization problem and the lowerBound() for a minimization problem, respectively.
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
| x | The new value of the dual bound. |
|
inline |
|
inline |
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.
| s1 | A pointer to a subproblem. |
| s2 | A pointer to a subproblem. |
|
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.
| s1 | A subproblem. |
| s2 | A subproblem. |
| bool abacus::Master::feasibleFound | ( | ) | const |
We use this function, e.g., to adapt the enumeration strategy in the DiveAndBest-Strategy.
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::cluster_planarity::CPlanarityMaster, ogdf::cluster_planarity::MaxCPlanarMaster, and ogdf::MinSteinerTreeDirectedCut< T >::Master.
|
inlineprivate |
|
inline |
| 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.
| 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.
|
inline |
|
inline |
|
inline |
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::CPlanarityMaster, ogdf::cluster_planarity::MaxCPlanarMaster, ogdf::MinSteinerTreeDirectedCut< T >::Master, and ogdf::cluster_planarity::CP_MasterBase.
|
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.
| sense | The sense of the optimization (OptSense::Min or OptSense::Max). |
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.
|
protectedvirtual |
Is overloaded such that also a first set of cutting planes can be inserted into the cutting plane pool.
| 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. |
|
protectedvirtual |
Sets up the default pools for variables, constraints, and cutting planes.
| 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. |
|
private |
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.
| 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. |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
Changes the maximal number of constraints that are buffered in an iteration of the cutting plane algorithm.
| max | The new maximal number of buffered constraints. |
|
inline |
Sets the maximally allowed wall-clock time for the optimization to t.
| t | The new value of the maximal cpu time in the form hh:mm:ss. |
| string abacus::Master::maxCowTimeAsString | ( | ) | const |
Returns the maximal wall-clock time (as string hh:mm:ss) which can be used by the optimization.
|
inline |
Sets the maximally allowed cpu time for the optimization to t.
| t | The new value of the maximal cpu time in the form hh:mm:ss. |
Sets the maximally allowed cpu time for the optimization to hour, min, sec.
| string abacus::Master::maxCpuTimeAsString | ( | ) | const |
Returns the maximal cpu time (as string hh:mm:ss) which can be used by the optimization.
|
inline |
Changes the default value for the maximal number of iterations of the optimization of a subproblem.
| max | The new maximal number of iterations of the subproblem optimization (-1 means no limit). |
|
inline |
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.
| ml | The new value of the maximal enumeration level. |
|
inline |
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.
| ml | The new value of the maximal enumeration level. |
|
inline |
|
inline |
Changes the maximal number of variables that are buffered in an iteration of the subproblem optimization.
| max | The new maximal number of buffered variables. |
|
inline |
|
inline |
Sets the number of tested branching variable candidates to n.
| n | The new value of the number of tested variables for becoming branching variable. |
|
inline |
Registers a new subproblem which is on level level in enumeration tree.
It is called each time a new subproblem is generated.
|
inline |
|
inline |
|
inline |
Sets the number of simplex iterations that are performed when testing candidates for branching variables within strong branching.
| n | The new value of the number of simplex iterations. |
|
inline |
|
inline |
|
inline |
|
inline |
| STATUS abacus::Master::optimize | ( | ) |
Performs the optimization by branch-and-bound.
|
inline |
|
inline |
|
inline |
|
inline |
|
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.
Sets the number of linear programs being solved between two additional pricing steps to f.
| f | The pricing frequency. |
|
inline |
|
inline |
Returns the value of the primal bound.
I.e., the lowerBound() for a maximization problem and the upperBound() for a minimization problem, respectively.
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.
| x | The new value of the primal bound. |
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.
| x | The value being compared with the primal bound. |
| 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.
|
inline |
| void abacus::Master::printParameters | ( | ) | const |
Writes all parameters of the class Master together with their values to the global output stream.
|
inline |
|
inline |
Changes the guarantee specification tp g.
| 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. |
|
inline |
|
inline |
Updates the final dual bound of the root node.
This function should be only called at the end of the root node optimization.
|
inline |
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().
|
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.
|
inline |
|
virtual |
Sets solver specific parameters.
The default does nothing.
|
inline |
|
inline |
Sets the frequency for constraint and variable generation to f.
| f | The new value of the frequency. |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
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.
| p | The new value for the tailing off analysis. |
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::cluster_planarity::CP_MasterBase, ogdf::cluster_planarity::CPlanarityMaster, ogdf::cluster_planarity::MaxCPlanarMaster, and ogdf::MinSteinerTreeDirectedCut< T >::Master.
|
private |
|
inline |
|
inline |
Passes the new lower bound lb to the Tree Interface.
Adds the subproblem sub to the stream storing information for graphical output of the enumeration tree if this logging is turned on.
Updates the node information in the node with number id by writing the lower bound lb and the upper bound ub to the node.
Assigns the color to the subproblem sub in the Tree Interface.
Passes the new upper bound ub to the Tree Interface.
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |
|
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().
| mode | The new mode. |
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.
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
