|
|||
|
|
|
|||
|
|
Master problem of Steiner tree branch&cut algorithm More...
#include <ogdf/graphalg/MinSteinerTreeDirectedCut.h>
Inheritance diagram for ogdf::MinSteinerTreeDirectedCut< T >::Master:Public Member Functions | |
| Master (const EdgeWeightedGraph< T > &wG, const List< node > &terminals, const NodeArray< bool > &isTerminal, double eps, bool relaxed=false) | |
| Constructor of the master problem. | |
| virtual | ~Master () |
| destructor | |
| double * | bestSolution () const |
| the best found solution | |
| bool | callPrimalHeuristic () const |
| parameter: call primal heuristic yes/no | |
| int | callPrimalHeuristicStrategy () const |
| strategy for calling primal heuristic (PH) | |
| const EdgeArray< double > & | capacities () const |
| edge costs | |
| double | capacities (edge e) const |
| costs for edge e | |
| void | checkSetMaxPoolSize () |
| checks if current pool size is maximum and sets it if necessary | |
| bool | computeBackCuts () const |
| parameter: back cut computation | |
| bool | computeNestedCuts () const |
| parameter: nested cut computation | |
| abacus::NonDuplPool< abacus::Constraint, abacus::Variable > * | cutPool () |
| the non-duplicate cutpool for the separated Steiner cuts | |
| edge | edgeGToWgPH (edge e) const |
| edge mapping m_pGraph -> m_pWeightedGraphPH | |
| int | edgeID (edge e) const |
| edge -> id of lp variable | |
| const EdgeArray< int > & | edgeIDs () const |
| lp variable ids of edges | |
| edge | edgeWgToGPH (edge e) const |
| edge mapping m_pWeightedGraphPH -> m_pGraph | |
| virtual abacus::Sub * | firstSub () override |
| generates the first subproblem | |
| edge | getEdge (int i) const |
| id -> edge | |
| MaxFlowModule< double > * | getMaxFlowModule () |
| Get the maximum flow module used by separation algorithm. | |
| node | getNode (int i) const |
| id -> node | |
| std::unique_ptr< MinSteinerTreeModule< double > > & | getPrimalHeuristic () |
| the primal heuristic module | |
| EdgeVariable * | getVar (edge e) const |
| returns the variable assigned to edge e | |
| EdgeVariable * | getVarTwin (edge e) const |
| returns the variable assigned to the twin of edge e | |
| const Graph & | graph () const |
| the directed graph, i.e., the bidirection of the input graph | |
| void | incNrCutsTotal () |
| increases the number of separated directed cuts by 1 | |
| void | incNrCutsTotal (int val) |
| increases the number of separated directed cuts | |
| bool | isSolutionEdge (edge e) const |
| returns true iff original edge is contained in optimum solution | |
| const NodeArray< bool > | isTerminal () const |
| boolean array of terminal status | |
| bool | isTerminal (node n) const |
| true if n is a terminal | |
| const NodeArray< bool > & | isTerminalPH () const |
| terminal yes/no (in m_pWeightedGraphPH) | |
| int | maxNrAddedCuttingPlanes () const |
| maximum nr of cutting planes | |
| int | maxPoolSize () const |
| the maximum pool size during the algorithm | |
| bool | minCardinalityCuts () const |
| parameter: compute minimum cardinality cuts | |
| int | nEdges () const |
| returns the number of edges | |
| int | nEdgesU () const |
| returns number of undirected edges, i.e., nEdges()/2 | |
| int | nNodes () const |
| number of nodes of the graph | |
| int | nodeID (node n) const |
| npde -> id of lp variable | |
| const NodeArray< int > & | nodeIDs () const |
| lp variable ids of nodes | |
| node * | nodes () const |
| nodes of the graph | |
| int | nrCutsTotal () const |
| total number of separated directed cuts | |
| int | nTerminals () const |
| number of terminals | |
| int | poolSizeInit () const |
| initial pool size | |
| StopwatchWallClock * | primalHeuristicTimer () |
| timer for primal heuristics | |
| bool | relaxed () const |
| solve relaxed LP or ILP | |
| node | rootNode () const |
| the designated root node (special terminal) | |
| node | rootNodePH () const |
| root node (in m_pWeightedGraphPH) | |
| int | saturationStrategy () const |
| strategy for saturating edges during separation; Only relevant for nested cuts | |
| int | separationStrategy () const |
| strategy for separating directed Steiner cuts; Only relevant for nested cuts | |
| StopwatchWallClock * | separationTimer () |
| timer for separation | |
| void | setConfigFile (const char *filename) |
| Set the config file to use that overrides all other settings. | |
| void | setMaxFlowModule (MaxFlowModule< double > *module) |
| Set the maximum flow module to be used for separation. | |
| void | setMaxNumberAddedCuttingPlanes (int b) |
| Set maximum number of added cutting planes per iteration. | |
| void | setNIterRoot (int val) |
| nr of iterations in the root node | |
| void | setPoolSizeInitFactor (int b) |
| Set factor for the initial size of the cutting pool. | |
| void | setPrimalHeuristic (MinSteinerTreeModule< double > *pMinSteinerTreeModule) |
| Set the module option for the primal heuristic. | |
| void | setPrimalHeuristicCallStrategy (int b) |
| Set primal heuristic call strategy. | |
| void | setRelaxedSolValue (double val) |
| solution value of the root | |
| void | setSaturationStrategy (int b) |
| Set saturation strategy for nested cuts. | |
| void | setSeparationStrategy (int b) |
| Set separation strategy for nested cuts. | |
| bool | shuffleTerminals () const |
| shuffle ordering of terminals before each separation routine | |
| double | solutionValue () const |
| solution value after solving the problem, i.e., returns final primal bound | |
| node | terminal (int i) const |
| get terminal with index i | |
| const List< node > & | terminalListPH () const |
| list of terminals (in m_pWeightedGraphPH) | |
| const node * | terminals () const |
| terminals in an array | |
| StopwatchWallClock * | timerMinSTCut () |
| timer for minimum st-cut computations. Measures updates + algorithm | |
| edge | twin (edge e) const |
| the twin edge, i.e. twin[(u,v)] = (v,u) | |
| const EdgeArray< edge > & | twins () const |
| void | updateBestSolution (double *values) |
| updates best found solution | |
| void | updateBestSolutionByEdges (const List< edge > &sol) |
| updates best found solution by list of edges | |
| void | useBackCuts (bool b) |
| Switch computation of back-cuts on or off. | |
| void | useDegreeConstraints (bool b) |
| Switch usage of degree constraints (like indeg <= 1) on or off. | |
| void | useFlowBalanceConstraints (bool b) |
| Switch usage of flow balance constraints on or off. | |
| void | useGSEC2Constraints (bool b) |
| Switch usage of constraints x_uv + x_vu <= 1 on or off. | |
| void | useIndegreeEdgeConstraints (bool b) |
| Switch usage of indegree edge constraints (indeg(v) >= outgoing edge(v,x) for all x) on or off. | |
| void | useMinCardinalityCuts (bool b) |
| Switch usage of the cardinality heuristic (minimum-cardinality cuts) on or off. | |
| void | useNestedCuts (bool b) |
| Switch computation of nested cuts on or off. | |
| void | useTerminalShuffle (bool b) |
| Switch terminal shuffling before separation on or off. | |
| EdgeWeightedGraph< double > & | weightedGraphPH () |
| Public Member Functions inherited from 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. | |
| 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. | |
| 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. | |
| Public Member Functions inherited from ogdf::Logger | |
| Logger () | |
| creates a new Logger-object with LogMode::Global and local log-level equal globalLogLevel | |
| Logger (Level level) | |
| creates a new Logger-object with LogMode::Global and given local log-level | |
| Logger (LogMode m) | |
| creates a new Logger-object with given log-mode and local log-level equal globalLogLevel | |
| Logger (LogMode m, Level level) | |
| creates a new Logger-object with given log-mode and given local log-level | |
| bool | is_lout (Level level=Level::Default) const |
| returns true if such an lout command will result in text being printed | |
| std::ostream & | lout (Level level=Level::Default) const |
| stream for logging-output (local) | |
| std::ostream & | sout () const |
| stream for statistic-output (local) | |
| std::ostream & | fout () const |
| stream for forced output (local) | |
| Level | localLogLevel () const |
| gives the local log-level | |
| void | localLogLevel (Level level) |
| sets the local log-level | |
| LogMode | localLogMode () const |
| gives the local log-mode | |
| void | localLogMode (LogMode m) |
| sets the local log-mode | |
| Level | effectiveLogLevel () const |
| obtain the effective log-level for the Logger-object (i.e., resolve the dependencies on the global settings) | |
| bool | effectiveStatisticMode () const |
| returns true if the Logger-object is effectively in statistic-mode (as this might be depending on the global settings) | |
Protected Member Functions | |
| virtual void | initializeOptimization () override |
| insert variables and base constraints | |
| virtual void | initializeParameters () override |
| read/set parameters from file | |
| virtual void | terminateOptimization () override |
| store solution in EdgeArray | |
| Protected Member Functions inherited from abacus::Master | |
| 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. | |
| 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 | 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. | |
Private Member Functions | |
| Master (const Master &rhs) | |
| const Master & | operator= (const Master &rhs) |
Private Attributes | |
| bool | m_addDegreeConstraints |
| parameter: add constraints concerning the indegree of a node, like: indeg <= 1 for all vertices | |
| bool | m_addFlowBalanceConstraints |
| parameter: add flow balance constraints for Steiner nodes n: outdeg(n) >= indeg(n) | |
| bool | m_addGSEC2Constraints |
| parameter: add GSEC2 constraints yes/no, i.e. x_uv + x_vu <= 1 | |
| bool | m_addIndegreeEdgeConstraints |
| add constraints concerning the indegree of a node w.r.t. one outgoing edge: indeg(v) >= outgoing edge(v,x) for all x | |
| bool | m_backCutComputation |
| parameter: compute back cuts yes/no i.e., outgoing edges of the root-set | |
| double * | m_bestSolution |
| best found solution | |
| int | m_callPrimalHeuristic |
| parameter: primal heuristic (PH) call strategy | |
| EdgeArray< double > | m_capacities |
| edge costs | |
| const char * | m_configfile |
| problem dependent config file | |
| EdgeArray< int > | m_edgeIDs |
| edge -> id | |
| edge * | m_edges |
| id -> edge | |
| EdgeArray< edge > | m_edgesGToWgPH |
| edge mapping m_pGraph -> m_pWeightedGraphPH | |
| EdgeArray< edge > | m_edgesWgToGPH |
| edge mapping m_pWeightedGraphPH -> m_pGraph | |
| EdgeArray< EdgeVariable * > | m_edgeToVar |
| edge -> lp variable | |
| EdgeArray< bool > | m_isSolutionEdge |
| NodeArray< bool > | m_isTerminal |
| node is terminal yes/no | |
| NodeArray< bool > | m_isTerminalPH |
| is terminal yes/no (in m_pWeightedGraphPH) | |
| EdgeArray< edge > | m_mapToBidirectedGraph1 |
| the first directed arc in m_pGraph for an original edge | |
| EdgeArray< edge > | m_mapToBidirectedGraph2 |
| the second directed arc in m_pGraph for an original edge | |
| EdgeArray< edge > | m_mapToOrigGraph |
| the undirected edge in the original graph for each arc in m_pGraph | |
| MaxFlowModule< double > * | m_maxFlowModule |
| int | m_maxNrAddedCuttingPlanes |
| parameter: maximum nr of cutting planes per iteration | |
| int | m_maxPoolSize |
| statistic number of cuts in pool | |
| bool | m_minCardinalityCuts |
| parameter: compute minimum cardinality cuts | |
| int | m_nEdgesU |
| number of undirected edges | |
| bool | m_nestedCutComputation |
| parameter: compute nested cuts yes/no i.e., saturate all cut edges and recompute the mincut | |
| int | m_nIterRoot |
| statistics: nr of iterations in the root node of the b&b tree | |
| NodeArray< int > | m_nodeIDs |
| node -> id | |
| node * | m_nodes |
| id -> node | |
| NodeArray< node > | m_nodesGToWgPH |
| node mapping m_pGraph -> m_pWeightedGraphPH | |
| int | m_nrCutsTotal |
| total number of separated directed cuts | |
| int | m_nTerminals |
| nr of terminals | |
| abacus::NonDuplPool< abacus::Constraint, abacus::Variable > * | m_pCutPool |
| the non-duplicate cut pool for the directed Steiner cuts | |
| Graph * | m_pGraph |
| the bidirected graph | |
| int | m_poolSizeInit |
| size of initial pool | |
| int | m_poolSizeInitFactor |
| parameter: factor for the initial size of the cutting pool | |
| int | m_poolSizeMax |
| maximal size of the pool | |
| std::unique_ptr< MinSteinerTreeModule< double > > | m_primalHeuristic |
| Algorithm used for the primal heuristic. | |
| StopwatchWallClock | m_primalHeuristicTimer |
| timer for primal heuristics | |
| EdgeWeightedGraph< double > * | m_pWeightedGraphPH |
| edge weighted bidirected graph; used and modified for primal heuristics | |
| bool | m_relaxed |
| parameter: indicates whether we solve the relaxed problem (LP) or the ILP | |
| double | m_relaxedSolValue |
| statistics: solution value of the relaxed master problem | |
| node | m_root |
| the virtual root of our graph. This node is a terminal. | |
| node | m_rootPH |
| root node in m_pWeightedGraphPH | |
| int | m_saturationStrategy |
| parameter: saturation strategy, only important if nested cuts are computed | |
| int | m_separationStrategy |
| parameter: separation strategy, only important if nested cuts are computed | |
| StopwatchWallClock | m_separationTimer |
| timer for separation | |
| bool | m_shuffleTerminals |
| parameter: shuffle the list of terminals right before separation | |
| List< node > | m_terminalListPH |
| list of terminal nodes (in m_pWeightedGraphPH) | |
| node * | m_terminals |
| terminal index -> terminal node | |
| StopwatchWallClock | m_timerMinSTCut |
| timer for minimum st-cut computations. Measures updates + algorithm | |
| EdgeArray< edge > | m_twin |
| the twin edges (u,v) <-> (v,u) | |
| const EdgeWeightedGraph< T > & | m_wG |
| the original weighted graph | |
Additional Inherited Members | |
| Public Types inherited from abacus::Master | |
| 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 Types inherited from ogdf::Logger | |
| enum class | Level { Minor , Medium , Default , High , Alarm , Force } |
| supported log-levels from lowest to highest importance More... | |
| enum class | LogMode { Global , GlobalLog , Log , Statistic } |
| Local log-modes. More... | |
| 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". | |
| Static Public Member Functions inherited from ogdf::Logger | |
| static bool | is_slout (Level level=Level::Default) |
| returns true if such an slout command will result in text being printed | |
| static std::ostream & | slout (Level level=Level::Default) |
| stream for logging-output (global) | |
| static std::ostream & | ssout () |
| stream for statistic-output (global) | |
| static std::ostream & | sfout () |
| stream for forced output (global) | |
| static bool | is_ilout (Level level=Level::Default) |
| stream for logging-output (global; used by internal libraries, e.g. Abacus) returns true if such an ilout command will result in text being printed | |
| static std::ostream & | ilout (Level level=Level::Default) |
| static std::ostream & | ifout () |
| stream for forced output (global; used by internal libraries, e.g. Abacus) | |
| static Level | globalLogLevel () |
| gives the global log-level | |
| static void | globalLogLevel (Level level) |
| sets the global log-level | |
| static Level | globalInternalLibraryLogLevel () |
| gives the internal-library log-level | |
| static void | globalInternalLibraryLogLevel (Level level) |
| sets the internal-library log-level | |
| static Level | globalMinimumLogLevel () |
| gives the globally minimally required log-level | |
| static void | globalMinimumLogLevel (Level level) |
| sets the globally minimally required log-level | |
| static bool | globalStatisticMode () |
| returns true if we are globally in statistic mode | |
| static void | globalStatisticMode (bool s) |
| sets whether we are globally in statistic mode | |
| static void | setWorldStream (std::ostream &o) |
change the stream to which allowed output is written (by default: std::cout) | |
| Static Public Attributes inherited from abacus::Master | |
| 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. | |
Master problem of Steiner tree branch&cut algorithm
Definition at line 193 of file MinSteinerTreeDirectedCut.h.
| ogdf::MinSteinerTreeDirectedCut< T >::Master::Master | ( | const EdgeWeightedGraph< T > & | wG, |
| const List< node > & | terminals, | ||
| const NodeArray< bool > & | isTerminal, | ||
| double | eps, | ||
| bool | relaxed = false |
||
| ) |
Constructor of the master problem.
| wG | the underlying undirected edge weighted graph. Since we work on the bidirection we construct a new graph. |
| terminals | list of terminals |
| isTerminal | boolean array indicating whether a node is a terminal |
| eps | epsilon precision |
| relaxed | true if the relaxed problem should be solved |
Definition at line 973 of file MinSteinerTreeDirectedCut.h.
|
inlinevirtual |
destructor
Reimplemented from abacus::Master.
Definition at line 208 of file MinSteinerTreeDirectedCut.h.
|
private |
|
inline |
the best found solution
Definition at line 390 of file MinSteinerTreeDirectedCut.h.
|
inline |
parameter: call primal heuristic yes/no
Definition at line 416 of file MinSteinerTreeDirectedCut.h.
|
inline |
strategy for calling primal heuristic (PH)
Definition at line 419 of file MinSteinerTreeDirectedCut.h.
|
inline |
edge costs
Definition at line 366 of file MinSteinerTreeDirectedCut.h.
|
inline |
costs for edge e
Definition at line 369 of file MinSteinerTreeDirectedCut.h.
|
inline |
checks if current pool size is maximum and sets it if necessary
Definition at line 434 of file MinSteinerTreeDirectedCut.h.
|
inline |
parameter: back cut computation
Definition at line 410 of file MinSteinerTreeDirectedCut.h.
|
inline |
parameter: nested cut computation
Definition at line 407 of file MinSteinerTreeDirectedCut.h.
|
inline |
the non-duplicate cutpool for the separated Steiner cuts
Definition at line 303 of file MinSteinerTreeDirectedCut.h.
|
inline |
edge mapping m_pGraph -> m_pWeightedGraphPH
Definition at line 472 of file MinSteinerTreeDirectedCut.h.
|
inline |
edge -> id of lp variable
Definition at line 345 of file MinSteinerTreeDirectedCut.h.
|
inline |
lp variable ids of edges
Definition at line 357 of file MinSteinerTreeDirectedCut.h.
|
inline |
edge mapping m_pWeightedGraphPH -> m_pGraph
Definition at line 475 of file MinSteinerTreeDirectedCut.h.
|
inlineoverridevirtual |
generates the first subproblem
Implements abacus::Master.
Definition at line 306 of file MinSteinerTreeDirectedCut.h.
|
inline |
id -> edge
Definition at line 360 of file MinSteinerTreeDirectedCut.h.
|
inline |
Get the maximum flow module used by separation algorithm.
Definition at line 235 of file MinSteinerTreeDirectedCut.h.
|
inline |
id -> node
Definition at line 363 of file MinSteinerTreeDirectedCut.h.
|
inline |
the primal heuristic module
Definition at line 298 of file MinSteinerTreeDirectedCut.h.
|
inline |
returns the variable assigned to edge e
Definition at line 378 of file MinSteinerTreeDirectedCut.h.
|
inline |
returns the variable assigned to the twin of edge e
Definition at line 381 of file MinSteinerTreeDirectedCut.h.
|
inline |
the directed graph, i.e., the bidirection of the input graph
Definition at line 315 of file MinSteinerTreeDirectedCut.h.
|
inline |
increases the number of separated directed cuts by 1
Definition at line 447 of file MinSteinerTreeDirectedCut.h.
|
inline |
increases the number of separated directed cuts
Definition at line 444 of file MinSteinerTreeDirectedCut.h.
|
overrideprotectedvirtual |
insert variables and base constraints
Reimplemented from abacus::Master.
Definition at line 1190 of file MinSteinerTreeDirectedCut.h.
|
overrideprotectedvirtual |
read/set parameters from file
Reimplemented from abacus::Master.
Definition at line 1128 of file MinSteinerTreeDirectedCut.h.
|
inline |
returns true iff original edge is contained in optimum solution
Definition at line 309 of file MinSteinerTreeDirectedCut.h.
|
inline |
boolean array of terminal status
Definition at line 342 of file MinSteinerTreeDirectedCut.h.
|
inline |
true if n is a terminal
Definition at line 339 of file MinSteinerTreeDirectedCut.h.
|
inline |
terminal yes/no (in m_pWeightedGraphPH)
Definition at line 466 of file MinSteinerTreeDirectedCut.h.
|
inline |
maximum nr of cutting planes
Definition at line 404 of file MinSteinerTreeDirectedCut.h.
|
inline |
the maximum pool size during the algorithm
Definition at line 431 of file MinSteinerTreeDirectedCut.h.
|
inline |
parameter: compute minimum cardinality cuts
Definition at line 413 of file MinSteinerTreeDirectedCut.h.
|
inline |
returns the number of edges
Definition at line 321 of file MinSteinerTreeDirectedCut.h.
|
inline |
returns number of undirected edges, i.e., nEdges()/2
Definition at line 324 of file MinSteinerTreeDirectedCut.h.
|
inline |
number of nodes of the graph
Definition at line 318 of file MinSteinerTreeDirectedCut.h.
|
inline |
npde -> id of lp variable
Definition at line 348 of file MinSteinerTreeDirectedCut.h.
|
inline |
lp variable ids of nodes
Definition at line 354 of file MinSteinerTreeDirectedCut.h.
|
inline |
nodes of the graph
Definition at line 351 of file MinSteinerTreeDirectedCut.h.
|
inline |
total number of separated directed cuts
Definition at line 450 of file MinSteinerTreeDirectedCut.h.
|
inline |
number of terminals
Definition at line 330 of file MinSteinerTreeDirectedCut.h.
|
private |
|
inline |
initial pool size
Definition at line 441 of file MinSteinerTreeDirectedCut.h.
|
inline |
timer for primal heuristics
Definition at line 487 of file MinSteinerTreeDirectedCut.h.
|
inline |
solve relaxed LP or ILP
Definition at line 384 of file MinSteinerTreeDirectedCut.h.
|
inline |
the designated root node (special terminal)
Definition at line 327 of file MinSteinerTreeDirectedCut.h.
|
inline |
root node (in m_pWeightedGraphPH)
Definition at line 469 of file MinSteinerTreeDirectedCut.h.
|
inline |
strategy for saturating edges during separation; Only relevant for nested cuts
Definition at line 425 of file MinSteinerTreeDirectedCut.h.
|
inline |
strategy for separating directed Steiner cuts; Only relevant for nested cuts
Definition at line 422 of file MinSteinerTreeDirectedCut.h.
|
inline |
timer for separation
Definition at line 481 of file MinSteinerTreeDirectedCut.h.
|
inline |
Set the config file to use that overrides all other settings.
Definition at line 219 of file MinSteinerTreeDirectedCut.h.
|
inline |
Set the maximum flow module to be used for separation.
Definition at line 232 of file MinSteinerTreeDirectedCut.h.
|
inline |
Set maximum number of added cutting planes per iteration.
Definition at line 250 of file MinSteinerTreeDirectedCut.h.
|
inline |
nr of iterations in the root node
Definition at line 401 of file MinSteinerTreeDirectedCut.h.
|
inline |
Set factor for the initial size of the cutting pool.
Definition at line 290 of file MinSteinerTreeDirectedCut.h.
|
inline |
Set the module option for the primal heuristic.
Definition at line 293 of file MinSteinerTreeDirectedCut.h.
|
inline |
Set primal heuristic call strategy.
Definition at line 283 of file MinSteinerTreeDirectedCut.h.
|
inline |
solution value of the root
Definition at line 398 of file MinSteinerTreeDirectedCut.h.
|
inline |
Set saturation strategy for nested cuts.
Definition at line 273 of file MinSteinerTreeDirectedCut.h.
|
inline |
Set separation strategy for nested cuts.
Definition at line 266 of file MinSteinerTreeDirectedCut.h.
|
inline |
shuffle ordering of terminals before each separation routine
Definition at line 428 of file MinSteinerTreeDirectedCut.h.
|
inline |
solution value after solving the problem, i.e., returns final primal bound
Definition at line 387 of file MinSteinerTreeDirectedCut.h.
|
inline |
get terminal with index i
Definition at line 336 of file MinSteinerTreeDirectedCut.h.
|
inline |
list of terminals (in m_pWeightedGraphPH)
Definition at line 463 of file MinSteinerTreeDirectedCut.h.
|
inline |
terminals in an array
Definition at line 333 of file MinSteinerTreeDirectedCut.h.
|
overrideprotectedvirtual |
store solution in EdgeArray
Reimplemented from abacus::Master.
Definition at line 1340 of file MinSteinerTreeDirectedCut.h.
|
inline |
timer for minimum st-cut computations. Measures updates + algorithm
Definition at line 484 of file MinSteinerTreeDirectedCut.h.
|
inline |
the twin edge, i.e. twin[(u,v)] = (v,u)
Definition at line 372 of file MinSteinerTreeDirectedCut.h.
|
inline |
Definition at line 375 of file MinSteinerTreeDirectedCut.h.
| void ogdf::MinSteinerTreeDirectedCut< T >::Master::updateBestSolution | ( | double * | values | ) |
updates best found solution
Definition at line 1410 of file MinSteinerTreeDirectedCut.h.
| void ogdf::MinSteinerTreeDirectedCut< T >::Master::updateBestSolutionByEdges | ( | const List< edge > & | sol | ) |
updates best found solution by list of edges
Definition at line 1425 of file MinSteinerTreeDirectedCut.h.
|
inline |
Switch computation of back-cuts on or off.
Definition at line 260 of file MinSteinerTreeDirectedCut.h.
|
inline |
Switch usage of degree constraints (like indeg <= 1) on or off.
Definition at line 238 of file MinSteinerTreeDirectedCut.h.
|
inline |
Switch usage of flow balance constraints on or off.
Definition at line 247 of file MinSteinerTreeDirectedCut.h.
|
inline |
Switch usage of constraints x_uv + x_vu <= 1 on or off.
Definition at line 244 of file MinSteinerTreeDirectedCut.h.
|
inline |
Switch usage of indegree edge constraints (indeg(v) >= outgoing edge(v,x) for all x) on or off.
Definition at line 241 of file MinSteinerTreeDirectedCut.h.
|
inline |
Switch usage of the cardinality heuristic (minimum-cardinality cuts) on or off.
Definition at line 280 of file MinSteinerTreeDirectedCut.h.
|
inline |
Switch computation of nested cuts on or off.
Definition at line 263 of file MinSteinerTreeDirectedCut.h.
|
inline |
Switch terminal shuffling before separation on or off.
Definition at line 257 of file MinSteinerTreeDirectedCut.h.
|
inline |
Definition at line 460 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: add constraints concerning the indegree of a node, like: indeg <= 1 for all vertices
Definition at line 594 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: add flow balance constraints for Steiner nodes n: outdeg(n) >= indeg(n)
Definition at line 598 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: add GSEC2 constraints yes/no, i.e. x_uv + x_vu <= 1
Definition at line 592 of file MinSteinerTreeDirectedCut.h.
|
private |
add constraints concerning the indegree of a node w.r.t. one outgoing edge: indeg(v) >= outgoing edge(v,x) for all x
Definition at line 596 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: compute back cuts yes/no i.e., outgoing edges of the root-set
Definition at line 605 of file MinSteinerTreeDirectedCut.h.
|
private |
best found solution
Definition at line 557 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: primal heuristic (PH) call strategy
Definition at line 637 of file MinSteinerTreeDirectedCut.h.
|
private |
edge costs
Definition at line 531 of file MinSteinerTreeDirectedCut.h.
|
private |
problem dependent config file
Definition at line 501 of file MinSteinerTreeDirectedCut.h.
|
private |
edge -> id
Definition at line 526 of file MinSteinerTreeDirectedCut.h.
|
private |
id -> edge
Definition at line 524 of file MinSteinerTreeDirectedCut.h.
|
private |
edge mapping m_pGraph -> m_pWeightedGraphPH
Definition at line 572 of file MinSteinerTreeDirectedCut.h.
|
private |
edge mapping m_pWeightedGraphPH -> m_pGraph
Definition at line 574 of file MinSteinerTreeDirectedCut.h.
|
private |
edge -> lp variable
Definition at line 533 of file MinSteinerTreeDirectedCut.h.
|
private |
Definition at line 558 of file MinSteinerTreeDirectedCut.h.
|
private |
node is terminal yes/no
Definition at line 547 of file MinSteinerTreeDirectedCut.h.
|
private |
is terminal yes/no (in m_pWeightedGraphPH)
Definition at line 568 of file MinSteinerTreeDirectedCut.h.
|
private |
the first directed arc in m_pGraph for an original edge
Definition at line 538 of file MinSteinerTreeDirectedCut.h.
|
private |
the second directed arc in m_pGraph for an original edge
Definition at line 540 of file MinSteinerTreeDirectedCut.h.
|
private |
the undirected edge in the original graph for each arc in m_pGraph
Definition at line 536 of file MinSteinerTreeDirectedCut.h.
|
private |
Definition at line 498 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: maximum nr of cutting planes per iteration
Definition at line 601 of file MinSteinerTreeDirectedCut.h.
|
private |
statistic number of cuts in pool
Definition at line 587 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: compute minimum cardinality cuts
Definition at line 629 of file MinSteinerTreeDirectedCut.h.
|
private |
number of undirected edges
Definition at line 522 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: compute nested cuts yes/no i.e., saturate all cut edges and recompute the mincut
Definition at line 607 of file MinSteinerTreeDirectedCut.h.
|
private |
statistics: nr of iterations in the root node of the b&b tree
Definition at line 513 of file MinSteinerTreeDirectedCut.h.
|
private |
node -> id
Definition at line 545 of file MinSteinerTreeDirectedCut.h.
|
private |
id -> node
Definition at line 543 of file MinSteinerTreeDirectedCut.h.
|
private |
node mapping m_pGraph -> m_pWeightedGraphPH
Definition at line 570 of file MinSteinerTreeDirectedCut.h.
|
private |
total number of separated directed cuts
Definition at line 589 of file MinSteinerTreeDirectedCut.h.
|
private |
nr of terminals
Definition at line 549 of file MinSteinerTreeDirectedCut.h.
|
private |
the non-duplicate cut pool for the directed Steiner cuts
Definition at line 579 of file MinSteinerTreeDirectedCut.h.
|
private |
the bidirected graph
Definition at line 519 of file MinSteinerTreeDirectedCut.h.
|
private |
size of initial pool
Definition at line 583 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: factor for the initial size of the cutting pool
Definition at line 581 of file MinSteinerTreeDirectedCut.h.
|
private |
maximal size of the pool
Definition at line 585 of file MinSteinerTreeDirectedCut.h.
|
private |
Algorithm used for the primal heuristic.
Definition at line 504 of file MinSteinerTreeDirectedCut.h.
|
private |
timer for primal heuristics
Definition at line 644 of file MinSteinerTreeDirectedCut.h.
|
private |
edge weighted bidirected graph; used and modified for primal heuristics
Definition at line 564 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: indicates whether we solve the relaxed problem (LP) or the ILP
Definition at line 507 of file MinSteinerTreeDirectedCut.h.
|
private |
statistics: solution value of the relaxed master problem
Definition at line 510 of file MinSteinerTreeDirectedCut.h.
|
private |
the virtual root of our graph. This node is a terminal.
Definition at line 554 of file MinSteinerTreeDirectedCut.h.
|
private |
root node in m_pWeightedGraphPH
Definition at line 576 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: saturation strategy, only important if nested cuts are computed
Definition at line 623 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: separation strategy, only important if nested cuts are computed
Definition at line 616 of file MinSteinerTreeDirectedCut.h.
|
private |
timer for separation
Definition at line 640 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: shuffle the list of terminals right before separation
Definition at line 603 of file MinSteinerTreeDirectedCut.h.
|
private |
list of terminal nodes (in m_pWeightedGraphPH)
Definition at line 566 of file MinSteinerTreeDirectedCut.h.
|
private |
terminal index -> terminal node
Definition at line 551 of file MinSteinerTreeDirectedCut.h.
|
private |
timer for minimum st-cut computations. Measures updates + algorithm
Definition at line 642 of file MinSteinerTreeDirectedCut.h.
|
private |
the twin edges (u,v) <-> (v,u)
Definition at line 528 of file MinSteinerTreeDirectedCut.h.
|
private |
the original weighted graph
Definition at line 516 of file MinSteinerTreeDirectedCut.h.
