|
|||
|
|
|
|||
|
|
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. More... | |
| virtual | ~Master () |
| destructor More... | |
| double * | bestSolution () const |
| the best found solution More... | |
| bool | callPrimalHeuristic () const |
| parameter: call primal heuristic yes/no More... | |
| int | callPrimalHeuristicStrategy () const |
| strategy for calling primal heuristic (PH) More... | |
| const EdgeArray< double > & | capacities () const |
| edge costs More... | |
| double | capacities (edge e) const |
| costs for edge e More... | |
| void | checkSetMaxPoolSize () |
| checks if current pool size is maximum and sets it if necessary More... | |
| bool | computeBackCuts () const |
| parameter: back cut computation More... | |
| bool | computeNestedCuts () const |
| parameter: nested cut computation More... | |
| abacus::NonDuplPool< abacus::Constraint, abacus::Variable > * | cutPool () |
| the non-duplicate cutpool for the separated Steiner cuts More... | |
| edge | edgeGToWgPH (edge e) const |
| edge mapping m_pGraph -> m_pWeightedGraphPH More... | |
| int | edgeID (edge e) const |
| edge -> id of lp variable More... | |
| const EdgeArray< int > & | edgeIDs () const |
| lp variable ids of edges More... | |
| edge | edgeWgToGPH (edge e) const |
| edge mapping m_pWeightedGraphPH -> m_pGraph More... | |
| virtual abacus::Sub * | firstSub () override |
| generates the first subproblem More... | |
| edge | getEdge (int i) const |
| id -> edge More... | |
| MaxFlowModule< double > * | getMaxFlowModule () |
| Get the maximum flow module used by separation algorithm. More... | |
| node | getNode (int i) const |
| id -> node More... | |
| std::unique_ptr< MinSteinerTreeModule< double > > & | getPrimalHeuristic () |
| the primal heuristic module More... | |
| EdgeVariable * | getVar (edge e) const |
| returns the variable assigned to edge e More... | |
| EdgeVariable * | getVarTwin (edge e) const |
| returns the variable assigned to the twin of edge e More... | |
| const Graph & | graph () const |
| the directed graph, i.e., the bidirection of the input graph More... | |
| void | incNrCutsTotal () |
| increases the number of separated directed cuts by 1 More... | |
| void | incNrCutsTotal (int val) |
| increases the number of separated directed cuts More... | |
| bool | isSolutionEdge (edge e) const |
| returns true iff original edge is contained in optimum solution More... | |
| const NodeArray< bool > | isTerminal () const |
| boolean array of terminal status More... | |
| bool | isTerminal (node n) const |
| true if n is a terminal More... | |
| const NodeArray< bool > & | isTerminalPH () const |
| terminal yes/no (in m_pWeightedGraphPH) More... | |
| int | maxNrAddedCuttingPlanes () const |
| maximum nr of cutting planes More... | |
| int | maxPoolSize () const |
| the maximum pool size during the algorithm More... | |
| bool | minCardinalityCuts () const |
| parameter: compute minimum cardinality cuts More... | |
| int | nEdges () const |
| returns the number of edges More... | |
| int | nEdgesU () const |
| returns number of undirected edges, i.e., nEdges()/2 More... | |
| int | nNodes () const |
| number of nodes of the graph More... | |
| int | nodeID (node n) const |
| npde -> id of lp variable More... | |
| const NodeArray< int > & | nodeIDs () const |
| lp variable ids of nodes More... | |
| node * | nodes () const |
| nodes of the graph More... | |
| int | nrCutsTotal () const |
| total number of separated directed cuts More... | |
| int | nTerminals () const |
| number of terminals More... | |
| int | poolSizeInit () const |
| initial pool size More... | |
| StopwatchWallClock * | primalHeuristicTimer () |
| timer for primal heuristics More... | |
| bool | relaxed () const |
| solve relaxed LP or ILP More... | |
| node | rootNode () const |
| the designated root node (special terminal) More... | |
| node | rootNodePH () const |
| root node (in m_pWeightedGraphPH) More... | |
| int | saturationStrategy () const |
| strategy for saturating edges during separation; Only relevant for nested cuts More... | |
| int | separationStrategy () const |
| strategy for separating directed Steiner cuts; Only relevant for nested cuts More... | |
| StopwatchWallClock * | separationTimer () |
| timer for separation More... | |
| void | setConfigFile (const char *filename) |
| Set the config file to use that overrides all other settings. More... | |
| void | setMaxFlowModule (MaxFlowModule< double > *module) |
| Set the maximum flow module to be used for separation. More... | |
| void | setMaxNumberAddedCuttingPlanes (int b) |
| Set maximum number of added cutting planes per iteration. More... | |
| void | setNIterRoot (int val) |
| nr of iterations in the root node More... | |
| void | setPoolSizeInitFactor (int b) |
| Set factor for the initial size of the cutting pool. More... | |
| void | setPrimalHeuristic (MinSteinerTreeModule< double > *pMinSteinerTreeModule) |
| Set the module option for the primal heuristic. More... | |
| void | setPrimalHeuristicCallStrategy (int b) |
| Set primal heuristic call strategy. More... | |
| void | setRelaxedSolValue (double val) |
| solution value of the root More... | |
| void | setSaturationStrategy (int b) |
| Set saturation strategy for nested cuts. More... | |
| void | setSeparationStrategy (int b) |
| Set separation strategy for nested cuts. More... | |
| bool | shuffleTerminals () const |
| shuffle ordering of terminals before each separation routine More... | |
| double | solutionValue () const |
| solution value after solving the problem, i.e., returns final primal bound More... | |
| node | terminal (int i) const |
| get terminal with index i More... | |
| const List< node > & | terminalListPH () const |
| list of terminals (in m_pWeightedGraphPH) More... | |
| const node * | terminals () const |
| terminals in an array More... | |
| StopwatchWallClock * | timerMinSTCut () |
| timer for minimum st-cut computations. Measures updates + algorithm More... | |
| edge | twin (edge e) const |
| the twin edge, i.e. twin[(u,v)] = (v,u) More... | |
| const EdgeArray< edge > & | twins () const |
| void | updateBestSolution (double *values) |
| updates best found solution More... | |
| void | updateBestSolutionByEdges (const List< edge > &sol) |
| updates best found solution by list of edges More... | |
| void | useBackCuts (bool b) |
| Switch computation of back-cuts on or off. More... | |
| void | useDegreeConstraints (bool b) |
| Switch usage of degree constraints (like indeg <= 1) on or off. More... | |
| void | useFlowBalanceConstraints (bool b) |
| Switch usage of flow balance constraints on or off. More... | |
| void | useGSEC2Constraints (bool b) |
| Switch usage of constraints x_uv + x_vu <= 1 on or off. More... | |
| void | useIndegreeEdgeConstraints (bool b) |
| Switch usage of indegree edge constraints (indeg(v) >= outgoing edge(v,x) for all x) on or off. More... | |
| void | useMinCardinalityCuts (bool b) |
| Switch usage of the cardinality heuristic (minimum-cardinality cuts) on or off. More... | |
| void | useNestedCuts (bool b) |
| Switch computation of nested cuts on or off. More... | |
| void | useTerminalShuffle (bool b) |
| Switch terminal shuffling before separation on or off. More... | |
| 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. More... | |
| BRANCHINGSTRAT | branchingStrategy () const |
| Returns the branching strategy. More... | |
| void | branchingStrategy (BRANCHINGSTRAT strat) |
| Changes the branching strategy to strat. More... | |
| const ogdf::StopwatchCPU * | branchingTime () const |
| Returns a pointer to the timer measuring the cpu time spent in finding and selecting the branching rules. More... | |
| bool | check () const |
| Can be used to control the correctness of the optimization if the value of the optimum solution has been loaded. More... | |
| int | conElimAge () const |
| Returns the age for the elimination of constraints. More... | |
| void | conElimAge (int age) |
| Changes the age for the elimination of constraints to age. More... | |
| double | conElimEps () const |
| Returns the zero tolerance for the elimination of constraints by the slack criterion. More... | |
| void | conElimEps (double eps) |
| Changes the tolerance for the elimination of constraints by the slack criterion to eps. More... | |
| CONELIMMODE | conElimMode () const |
| Returns the mode for the elimination of constraints. More... | |
| void | conElimMode (CONELIMMODE mode) |
| Changes the constraint elimination mode to mode. More... | |
| StandardPool< Constraint, Variable > * | conPool () const |
| Returns a pointer to the default pool storing the constraints of the problem formulation. More... | |
| StandardPool< Constraint, Variable > * | cutPool () const |
| Returns a pointer to the default pool for the generated cutting planes. More... | |
| bool | cutting () const |
| int | dbThreshold () const |
| Returns the number of optimizations of a subproblem until sons are created. More... | |
| void | dbThreshold (int threshold) |
| Sets the number of optimizations of a subproblem until sons are created in Sub::branching(). More... | |
| OSISOLVER | defaultLpSolver () const |
| returns the Lp Solver. More... | |
| void | defaultLpSolver (OSISOLVER osiSolver) |
| Changes the default Lp solver to osiSolver. More... | |
| bool | delayedBranching (int nOpt) const |
| Returns true if the number of optimizations nOpt of a subproblem exceeds the delayed branching threshold, false otherwise. More... | |
| bool | eliminateFixedSet () const |
| void | eliminateFixedSet (bool turnOn) |
| Turns the elimination of fixed and set variables on or off. More... | |
| ENUMSTRAT | enumerationStrategy () const |
| Returns the enumeration strategy. More... | |
| virtual int | enumerationStrategy (const Sub *s1, const Sub *s2) |
Analyzes the enumeration strategy set in the parameter file .abacus and calls the corresponding comparison function for the subproblems s1 and s2. More... | |
| void | enumerationStrategy (ENUMSTRAT strat) |
| Changes the enumeration strategy to strat. More... | |
| bool | fixSetByRedCost () const |
| void | fixSetByRedCost (bool on) |
| Turns fixing and setting variables by reduced cost on or off. More... | |
| double | guarantee () const |
| Can be used to access the guarantee which can be given for the best known feasible solution. More... | |
| bool | guaranteed () const |
| Can be used to check if the guarantee requirements are fulfilled. More... | |
| int | highestLevel () const |
| Returns the highest level in the tree which has been reached during the implicit enumeration. More... | |
| History * | history () const |
| Returns a pointer to the object storing the solution history of this branch and cut problem. More... | |
| const ogdf::StopwatchCPU * | improveTime () const |
| Returns a pointer to the timer measuring the cpu time spent in the heuristics for the computation of feasible solutions. More... | |
| bool | knownOptimum (double &optVal) const |
Opens the file specified with the parameter OptimumFileName in the configuration file .abacus and tries to find a line with the name of the problem instance (as specified in the constructor of Master) as first string. More... | |
| LpMasterOsi * | lpMasterOsi () const |
| const ogdf::StopwatchCPU * | lpSolverTime () const |
| Return a pointer to the timer measuring the cpu time required by the LP solver. More... | |
| const ogdf::StopwatchCPU * | lpTime () const |
| Returns a pointer to the timer measuring the cpu time spent in members of the LP-interface. More... | |
| int | maxConAdd () const |
| Returns the maximal number of constraints which should be added in every iteration of the cutting plane algorithm. More... | |
| void | maxConAdd (int max) |
| Sets the maximal number of constraints that are added in an iteration of the cutting plane algorithm. More... | |
| int | maxConBuffered () const |
| Returns the size of the buffer for generated constraints in the cutting plane algorithm. More... | |
| void | maxConBuffered (int max) |
| Changes the maximal number of constraints that are buffered in an iteration of the cutting plane algorithm. More... | |
| int64_t | maxCowTime () const |
| Returns the maximal wall-clock time (in seconds) which can be used by the optimization. More... | |
| void | maxCowTime (const string &t) |
| Sets the maximally allowed wall-clock time for the optimization to t. More... | |
| void | maxCowTime (int64_t seconds) |
| Sets the maximally allowed wall-clock time to seconds. More... | |
| string | maxCowTimeAsString () const |
Returns the maximal wall-clock time (as string hh:mm:ss) which can be used by the optimization. More... | |
| int64_t | maxCpuTime () const |
| Returns the maximal cpu time (in seconds) which can be used by the optimization. More... | |
| void | maxCpuTime (const string &t) |
| Sets the maximally allowed cpu time for the optimization to t. More... | |
| void | maxCpuTime (int hour, int min, int sec) |
| Sets the maximally allowed cpu time for the optimization to hour, min, sec. More... | |
| void | maxCpuTime (int64_t seconds) |
| Sets the maximally allowed cpu time to seconds. More... | |
| string | maxCpuTimeAsString () const |
Returns the maximal cpu time (as string hh:mm:ss) which can be used by the optimization. More... | |
| int | maxIterations () const |
| Returns the maximal number of iterations per subproblem optimization (-1 means no iteration limit). More... | |
| void | maxIterations (int max) |
| Changes the default value for the maximal number of iterations of the optimization of a subproblem. More... | |
| int | maxLevel () const |
| Returns the maximal depth up to which the enumeration should be performed. More... | |
| void | maxLevel (int ml) |
| This version of the function maxLevel() changes the maximal enumeration depth. More... | |
| int | maxNSub () const |
| Returns the maximal number of subproblems to be processed. More... | |
| void | maxNSub (int ml) |
| Changes the maximal number of subproblems to ml. More... | |
| int | maxVarAdd () const |
| Returns the maximal number of variables which should be added in the column generation algorithm. More... | |
| void | maxVarAdd (int max) |
| Changes the maximal number of variables that are added in an iteration of the subproblem optimization. More... | |
| int | maxVarBuffered () const |
| Returns the size of the buffer for the variables generated in the column generation algorithm. More... | |
| void | maxVarBuffered (int max) |
| Changes the maximal number of variables that are buffered in an iteration of the subproblem optimization. More... | |
| int | minDormantRounds () const |
| Returns the maximal number of rounds, i.e., number of subproblem optimizations, a subproblem is dormant. More... | |
| void | minDormantRounds (int nRounds) |
| Sets the number of rounds a subproblem should stay dormant to nRounds. More... | |
| int | nBranchingVariableCandidates () const |
| Returns the number of variables that should be tested for the selection of the branching variable. More... | |
| void | nBranchingVariableCandidates (int n) |
| Sets the number of tested branching variable candidates to n. More... | |
| bool | newRootReOptimize () const |
| void | newRootReOptimize (bool on) |
| Turns the reoptimization of new root nodes of the remaining branch and bound tree on or off. More... | |
| int | nLp () const |
| Returns the number of optimized linear programs (only LP-relaxations). More... | |
| int | nNewRoot () const |
| Returns the number of root changes of the remaining branch-and-cut tree. More... | |
| int | nStrongBranchingIterations () const |
| The number of simplex iterations that are performed when testing candidates for branching variables within strong branching. More... | |
| void | nStrongBranchingIterations (int n) |
| Sets the number of simplex iterations that are performed when testing candidates for branching variables within strong branching. More... | |
| int | nSub () const |
| returns the number of generated subproblems. More... | |
| int | nSubSelected () const |
| Returns the number of subproblems which have already been selected from the set of open subproblems. More... | |
| bool | objInteger () const |
| If true then we assume that all feasible solutions have integral objective function values. More... | |
| void | objInteger (bool b) |
| Sets the assumption that the objective function values of all feasible solutions are integer. More... | |
| OpenSub * | openSub () const |
| Returns a pointer to the set of open subproblems. More... | |
| STATUS | optimize () |
| Performs the optimization by branch-and-bound. More... | |
| const string & | optimumFileName () const |
| Returns the name of the file that stores the optimum solutions. More... | |
| void | optimumFileName (const char *name) |
| Changes the name of the file in which the value of the optimum solution is searched. More... | |
| const OptSense * | optSense () const |
| Returns a pointer to the object holding the optimization sense of the problem. More... | |
| virtual void | output () const |
| Does nothing but can be redefined in derived classes for output before the timing statistics. More... | |
| PRIMALBOUNDMODE | pbMode () const |
| Returns the mode of the primal bound initialization. More... | |
| void | pbMode (PRIMALBOUNDMODE mode) |
| Sets the mode of the primal bound initialization to mode. More... | |
| bool | pricing () const |
| int | pricingFreq () const |
| Returns the number of linear programs being solved between two additional pricing steps. More... | |
| void | pricingFreq (int f) |
| Sets the number of linear programs being solved between two additional pricing steps to f. More... | |
| const ogdf::StopwatchCPU * | pricingTime () const |
| Returns a pointer to the timer measuring the cpu time spent in pricing. More... | |
| void | printGuarantee () const |
| Writes the guarantee nicely formated on the output stream associated with this object. More... | |
| bool | printLP () const |
| void | printLP (bool on) |
| Turns the output of the linear program in every iteration on or off. More... | |
| void | printParameters () const |
| Writes all parameters of the class Master together with their values to the global output stream. More... | |
| const string & | problemName () const |
| Returns the name of the instance being optimized (as specified in the constructor of this class). More... | |
| double | requiredGuarantee () const |
| The guarantee specification for the optimization. More... | |
| void | requiredGuarantee (double g) |
| Changes the guarantee specification tp g. More... | |
| Sub * | root () const |
| Can be used to access the root node of the branch-and-bound tree. More... | |
| Sub * | rRoot () const |
| const ogdf::StopwatchCPU * | separationTime () const |
| Returns a pointer to the timer measuring the cpu time spent in the separation of cutting planes. More... | |
| virtual bool | setSolverParameters (OsiSolverInterface *interface, bool solverIsApprox) |
| Sets solver specific parameters. More... | |
| bool | showAverageCutDistance () const |
| void | showAverageCutDistance (bool on) |
| Turns the output of the average distance of the added cuts from the fractional solution on or off. More... | |
| int | skipFactor () const |
| Returns the frequency of subproblems in which constraints or variables should be generated. More... | |
| void | skipFactor (int f) |
| Sets the frequency for constraint and variable generation to f. More... | |
| SKIPPINGMODE | skippingMode () const |
| Returns the skipping strategy. More... | |
| void | skippingMode (SKIPPINGMODE mode) |
| Sets the skipping strategy to mode. More... | |
| bool | solveApprox () const |
| True, if an approximative solver should be used. More... | |
| STATUS | status () const |
| Returns the status of the Master. More... | |
| int | tailOffNLp () const |
| Returns the number of linear programs considered in the tailing off analysis. More... | |
| void | tailOffNLp (int n) |
| Sets the number of linear programs considered in the tailing off analysis to n. More... | |
| double | tailOffPercent () const |
| Returns the minimal change of the dual bound for the tailing off analysis in percent. More... | |
| void | tailOffPercent (double p) |
| Sets the minimal change of the dual bound for the tailing off analysis to p. More... | |
| const ogdf::StopwatchWallClock * | totalCowTime () const |
| Returns a pointer to the timer measuring the total wall clock time. More... | |
| const ogdf::StopwatchCPU * | totalTime () const |
| returns a pointer to the timer measuring the total cpu time for the optimization. More... | |
| int | varElimAge () const |
| Returns the age for the elimination of variables by the reduced cost criterion. More... | |
| void | varElimAge (int age) |
| Changes the age for the elimination of variables by the reduced cost criterion to age. More... | |
| double | varElimEps () const |
| Returns the zero tolerance for the elimination of variables by the reduced cost criterion. More... | |
| void | varElimEps (double eps) |
| Changes the tolerance for the elimination of variables by the reduced cost criterion to eps. More... | |
| VARELIMMODE | varElimMode () const |
| Returns the mode for the elimination of variables. More... | |
| void | varElimMode (VARELIMMODE mode) |
| Changes the variable elimination mode to mode. More... | |
| StandardPool< Variable, Constraint > * | varPool () const |
| Returns a pointer to the default pool storing the variables. More... | |
| VBCMODE | vbcLog () const |
| Returns the mode of output for the Vbc-Tool. More... | |
| void | vbcLog (VBCMODE mode) |
| Changes the mode of output for the Vbc-Tool to mode. More... | |
| double | lowerBound () const |
| Returns the value of the global lower bound. More... | |
| double | upperBound () const |
| Returns the value of the global upper bound. More... | |
| double | primalBound () const |
| Returns the value of the primal bound. More... | |
| void | primalBound (double x) |
| Sets the primal bound to x and makes a new entry in the solution history. More... | |
| double | dualBound () const |
| Returns the value of the dual bound. More... | |
| void | dualBound (double x) |
| Sets the dual bound to x and makes a new entry in the solution history. More... | |
| bool | betterDual (double x) const |
| Returns true if x is better than the best known dual bound; false otherwise. More... | |
| bool | primalViolated (double x) const |
| Can be used to compare a value with the one of the best known primal bound. More... | |
| bool | betterPrimal (double x) const |
| Can be used to check if a value is better than the best know primal bound. More... | |
| double | rootDualBound () const |
| Returns the dual bound at the root node. More... | |
| bool | feasibleFound () const |
| We use this function, e.g., to adapt the enumeration strategy in the DiveAndBest-Strategy. More... | |
| Public Member Functions inherited from abacus::AbacusGlobal | |
| AbacusGlobal (double eps=1.0e-4, double machineEps=1.0e-7, double infinity=1.0e32) | |
| The constructor. More... | |
| virtual | ~AbacusGlobal () |
| The destructor. More... | |
| void | assignParameter (bool ¶m, const char *name) const |
| See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More... | |
| void | assignParameter (bool ¶m, const char *name, bool defVal) const |
| See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More... | |
| void | assignParameter (char ¶m, const char *name, const char *feasible, char defVal) const |
| See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More... | |
| void | assignParameter (char ¶m, const char *name, const char *feasible=nullptr) const |
| See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More... | |
| void | assignParameter (double ¶m, const char *name, double minVal, double maxVal) const |
| See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More... | |
| 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. More... | |
| 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. More... | |
| 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. More... | |
| 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. More... | |
| 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. More... | |
| void | assignParameter (unsigned ¶m, const char *name, unsigned minVal, unsigned maxVal) const |
| See AbacusGlobal::assignParameter(int&,const char*,int,int) for a description. More... | |
| 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. More... | |
| double | eps () const |
| Returns the zero tolerance. More... | |
| void | eps (double e) |
| Sets the zero tolerance to e. More... | |
| bool | equal (double x, double y) const |
| Returns whether the absolute difference between x and y is less than the machine dependent zero tolerance. More... | |
| int | findParameter (const char *name, const char *feasible) const |
| See AbacusGlobal::findParameter(const char *name, unsigned nFeasible, const int *feasible) for description. More... | |
| int | findParameter (const char *name, unsigned nFeasible, const char *feasible[]) const |
| See AbacusGlobal::findParameter(const char *name, unsigned nFeasible, const int *feasible) for description. More... | |
| int | findParameter (const char *name, unsigned nFeasible, const int *feasible) const |
| Searches for parameter name in the parameter table. More... | |
| int | getParameter (const char *name, bool ¶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. More... | |
| 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. More... | |
| void | infinity (double x) |
| Sets the "infinite value" to x. More... | |
| void | insertParameter (const char *name, const char *value) |
| Inserts parameter name with value value into the parameter table. More... | |
| bool | isInfinity (double x) const |
| Returns true if x is regarded as "infinite" large, false otherwise. More... | |
| bool | isInteger (double x) const |
| Returns whether the value x differs at most by the machine dependent zero tolerance from an integer value. More... | |
| bool | isInteger (double x, double eps) const |
| Returns whether the value x differs at most by eps from an integer value. More... | |
| bool | isMinusInfinity (double x) const |
| Returns true if x is regarded as infinite small, false otherwise. More... | |
| double | machineEps () const |
| Provides a machine dependent zero tolerance. More... | |
| void | machineEps (double e) |
| Sets the machine dependent zero tolerance to e. More... | |
| void | readParameters (const string &fileName) |
| Opens the parameter file fileName, reads all parameters, and inserts them in the parameter table. More... | |
| Public Member Functions inherited from abacus::AbacusRoot | |
| virtual | ~AbacusRoot () |
| The destructor. More... | |
| Public Member Functions inherited from ogdf::Logger | |
| Logger () | |
| creates a new Logger-object with LogMode::Global and local log-level equal globalLogLevel More... | |
| Logger (Level level) | |
| creates a new Logger-object with LogMode::Log and given local log-level More... | |
| Logger (LogMode m) | |
| creates a new Logger-object with given log-mode and local log-level equal globalLogLevel More... | |
| Logger (LogMode m, Level level) | |
| creates a new Logger-object with given log-mode and given local log-level More... | |
| bool | is_lout (Level level=Level::Default) const |
| returns true if such an lout command will result in text being printed More... | |
| std::ostream & | lout (Level level=Level::Default, bool indent=true) const |
| stream for logging-output (local) More... | |
| std::ostream & | sout () const |
| stream for statistic-output (local) More... | |
| std::ostream & | fout () const |
| stream for forced output (local) More... | |
| Level | localLogLevel () const |
| gives the local log-level More... | |
| void | localLogLevel (Level level) |
| sets the local log-level More... | |
| LogMode | localLogMode () const |
| gives the local log-mode More... | |
| void | localLogMode (LogMode m) |
| sets the local log-mode More... | |
| void | indent (int by=1) |
| void | dedent (int by=1) |
| int | getIndent () const |
| void | setIndent (int indent) |
| Level | effectiveLogLevel () const |
| obtain the effective log-level for the Logger-object (i.e., resolve the dependencies on the global settings) More... | |
| bool | effectiveStatisticMode () const |
| returns true if the Logger-object is effectively in statistic-mode (as this might be depending on the global settings) More... | |
Protected Member Functions | |
| virtual void | initializeOptimization () override |
| insert variables and base constraints More... | |
| virtual void | initializeParameters () override |
| read/set parameters from file More... | |
| virtual void | terminateOptimization () override |
| store solution in EdgeArray More... | |
| 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. More... | |
| int | bestFirstSearch (const Sub *s1, const Sub *s2) const |
| Implements the best first search enumeration. More... | |
| int | breadthFirstSearch (const Sub *s1, const Sub *s2) const |
| Implements the breadth first search enumeration strategy, i.e., the subproblem with minimum level is selected. More... | |
| int | depthFirstSearch (const Sub *s1, const Sub *s2) const |
| Implements the depth first search enumeration strategy, i.e., the subproblem with maximum level is selected. More... | |
| int | diveAndBestFirstSearch (const Sub *s1, const Sub *s2) const |
| Performs depth-first search until a feasible solution is found, then the search process is continued with best-first search. More... | |
| virtual int | equalSubCompare (const Sub *s1, const Sub *s2) const |
| Is called from the function bestFirstSearch() and from the function depthFirstSearch() if the subproblems s1 and s2 have the same priority. More... | |
| void | initializeOptSense (OptSense::SENSE sense) |
| Can be used to initialize the sense of the optimization in derived classes, if this has not been already performed when the constructor of Master has been called. More... | |
| virtual void | initializePools (ArrayBuffer< Constraint * > &constraints, ArrayBuffer< Constraint * > &cuts, ArrayBuffer< Variable * > &variables, int varPoolSize, int cutPoolSize, bool dynamicCutPool=false) |
| Is overloaded such that also a first set of cutting planes can be inserted into the cutting plane pool. More... | |
| virtual void | initializePools (ArrayBuffer< Constraint * > &constraints, ArrayBuffer< Variable * > &variables, int varPoolSize, int cutPoolSize, bool dynamicCutPool=false) |
| Sets up the default pools for variables, constraints, and cutting planes. More... | |
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 More... | |
| bool | m_addFlowBalanceConstraints |
| parameter: add flow balance constraints for Steiner nodes n: outdeg(n) >= indeg(n) More... | |
| bool | m_addGSEC2Constraints |
| parameter: add GSEC2 constraints yes/no, i.e. x_uv + x_vu <= 1 More... | |
| 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 More... | |
| bool | m_backCutComputation |
| parameter: compute back cuts yes/no i.e., outgoing edges of the root-set More... | |
| double * | m_bestSolution |
| best found solution More... | |
| int | m_callPrimalHeuristic |
| parameter: primal heuristic (PH) call strategy More... | |
| EdgeArray< double > | m_capacities |
| edge costs More... | |
| const char * | m_configfile |
| problem dependent config file More... | |
| EdgeArray< int > | m_edgeIDs |
| edge -> id More... | |
| edge * | m_edges |
| id -> edge More... | |
| EdgeArray< edge > | m_edgesGToWgPH |
| edge mapping m_pGraph -> m_pWeightedGraphPH More... | |
| EdgeArray< edge > | m_edgesWgToGPH |
| edge mapping m_pWeightedGraphPH -> m_pGraph More... | |
| EdgeArray< EdgeVariable * > | m_edgeToVar |
| edge -> lp variable More... | |
| EdgeArray< bool > | m_isSolutionEdge |
| NodeArray< bool > | m_isTerminal |
| node is terminal yes/no More... | |
| NodeArray< bool > | m_isTerminalPH |
| is terminal yes/no (in m_pWeightedGraphPH) More... | |
| EdgeArray< edge > | m_mapToBidirectedGraph1 |
| the first directed arc in m_pGraph for an original edge More... | |
| EdgeArray< edge > | m_mapToBidirectedGraph2 |
| the second directed arc in m_pGraph for an original edge More... | |
| EdgeArray< edge > | m_mapToOrigGraph |
| the undirected edge in the original graph for each arc in m_pGraph More... | |
| MaxFlowModule< double > * | m_maxFlowModule |
| int | m_maxNrAddedCuttingPlanes |
| parameter: maximum nr of cutting planes per iteration More... | |
| int | m_maxPoolSize |
| statistic number of cuts in pool More... | |
| bool | m_minCardinalityCuts |
| parameter: compute minimum cardinality cuts More... | |
| int | m_nEdgesU |
| number of undirected edges More... | |
| bool | m_nestedCutComputation |
| parameter: compute nested cuts yes/no i.e., saturate all cut edges and recompute the mincut More... | |
| int | m_nIterRoot |
| statistics: nr of iterations in the root node of the b&b tree More... | |
| NodeArray< int > | m_nodeIDs |
| node -> id More... | |
| node * | m_nodes |
| id -> node More... | |
| NodeArray< node > | m_nodesGToWgPH |
| node mapping m_pGraph -> m_pWeightedGraphPH More... | |
| int | m_nrCutsTotal |
| total number of separated directed cuts More... | |
| int | m_nTerminals |
| nr of terminals More... | |
| abacus::NonDuplPool< abacus::Constraint, abacus::Variable > * | m_pCutPool |
| the non-duplicate cut pool for the directed Steiner cuts More... | |
| Graph * | m_pGraph |
| the bidirected graph More... | |
| int | m_poolSizeInit |
| size of initial pool More... | |
| int | m_poolSizeInitFactor |
| parameter: factor for the initial size of the cutting pool More... | |
| int | m_poolSizeMax |
| maximal size of the pool More... | |
| std::unique_ptr< MinSteinerTreeModule< double > > | m_primalHeuristic |
| Algorithm used for the primal heuristic. More... | |
| StopwatchWallClock | m_primalHeuristicTimer |
| timer for primal heuristics More... | |
| EdgeWeightedGraph< double > * | m_pWeightedGraphPH |
| edge weighted bidirected graph; used and modified for primal heuristics More... | |
| bool | m_relaxed |
| parameter: indicates whether we solve the relaxed problem (LP) or the ILP More... | |
| double | m_relaxedSolValue |
| statistics: solution value of the relaxed master problem More... | |
| node | m_root |
| the virtual root of our graph. This node is a terminal. More... | |
| node | m_rootPH |
| root node in m_pWeightedGraphPH More... | |
| int | m_saturationStrategy |
| parameter: saturation strategy, only important if nested cuts are computed More... | |
| int | m_separationStrategy |
| parameter: separation strategy, only important if nested cuts are computed More... | |
| StopwatchWallClock | m_separationTimer |
| timer for separation More... | |
| bool | m_shuffleTerminals |
| parameter: shuffle the list of terminals right before separation More... | |
| List< node > | m_terminalListPH |
| list of terminal nodes (in m_pWeightedGraphPH) More... | |
| node * | m_terminals |
| terminal index -> terminal node More... | |
| StopwatchWallClock | m_timerMinSTCut |
| timer for minimum st-cut computations. Measures updates + algorithm More... | |
| EdgeArray< edge > | m_twin |
| the twin edges (u,v) <-> (v,u) More... | |
| const EdgeWeightedGraph< T > & | m_wG |
| the original weighted graph More... | |
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 | Level { Level::Minor, Level::Medium, Level::Default, Level::High, Level::Alarm, Level::Force } |
| supported log-levels from lowest to highest importance More... | |
| enum | LogMode { LogMode::Global, LogMode::GlobalLog, LogMode::Log, LogMode::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. More... | |
| static bool | endsWith (const string &str, const string &end) |
| Returns true if str ends with end, false otherwise. More... | |
| static double | fracPart (double x) |
| Returns the absolute value of the fractional part of x. More... | |
| static const char * | onOff (bool value) |
| Converts a boolean variable to the strings "on" and "off". More... | |
| 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 More... | |
| static std::ostream & | slout (Level level=Level::Default) |
| stream for logging-output (global) More... | |
| static std::ostream & | ssout () |
| stream for statistic-output (global) More... | |
| static std::ostream & | sfout () |
| stream for forced output (global) More... | |
| 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 More... | |
| static std::ostream & | ilout (Level level=Level::Default) |
| static std::ostream & | ifout () |
| stream for forced output (global; used by internal libraries, e.g. Abacus) More... | |
| static Level | globalLogLevel () |
| gives the global log-level More... | |
| static void | globalLogLevel (Level level) |
| sets the global log-level More... | |
| static Level | globalInternalLibraryLogLevel () |
| gives the internal-library log-level More... | |
| static void | globalInternalLibraryLogLevel (Level level) |
| sets the internal-library log-level More... | |
| static Level | globalMinimumLogLevel () |
| gives the globally minimally required log-level More... | |
| static void | globalMinimumLogLevel (Level level) |
| sets the globally minimally required log-level More... | |
| static bool | globalStatisticMode () |
| returns true if we are globally in statistic mode More... | |
| static void | globalStatisticMode (bool s) |
| sets whether we are globally in statistic mode More... | |
| static void | setWorldStream (std::ostream &o) |
change the stream to which allowed output is written (by default: std::cout) More... | |
| Static Public Attributes inherited from abacus::Master | |
| static const char * | BRANCHINGSTRAT_ [] |
| Literal values for the enumerators of the corresponding enumeration type. More... | |
| static const char * | CONELIMMODE_ [] |
| Literal values for the enumerators of the corresponding enumeration type. More... | |
| static const char * | ENUMSTRAT_ [] |
| Literal values for the enumerators of the corresponding enumeration type. More... | |
| static const char * | OSISOLVER_ [] |
| Array for the literal values for possible Osi solvers. More... | |
| static const char * | PRIMALBOUNDMODE_ [] |
| Literal values for the enumerators of the corresponding enumeration type. More... | |
| static const char * | SKIPPINGMODE_ [] |
| Literal values for the enumerators of the corresponding enumeration type. More... | |
| static const char * | STATUS_ [] |
| Literal values for the enumerators of the corresponding enumeration type. More... | |
| static const char * | VARELIMMODE_ [] |
| Literal values for the enumerators of the corresponding enumeration type. More... | |
| static const char * | VBCMODE_ [] |
| Literal values for the enumerators of the corresponding enumeration type. More... | |
Master problem of Steiner tree branch&cut algorithm
Definition at line 206 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 986 of file MinSteinerTreeDirectedCut.h.
|
inlinevirtual |
destructor
Reimplemented from abacus::Master.
Definition at line 221 of file MinSteinerTreeDirectedCut.h.
|
private |
|
inline |
the best found solution
Definition at line 403 of file MinSteinerTreeDirectedCut.h.
|
inline |
parameter: call primal heuristic yes/no
Definition at line 429 of file MinSteinerTreeDirectedCut.h.
|
inline |
strategy for calling primal heuristic (PH)
Definition at line 432 of file MinSteinerTreeDirectedCut.h.
|
inline |
edge costs
Definition at line 379 of file MinSteinerTreeDirectedCut.h.
|
inline |
costs for edge e
Definition at line 382 of file MinSteinerTreeDirectedCut.h.
|
inline |
checks if current pool size is maximum and sets it if necessary
Definition at line 447 of file MinSteinerTreeDirectedCut.h.
|
inline |
parameter: back cut computation
Definition at line 423 of file MinSteinerTreeDirectedCut.h.
|
inline |
parameter: nested cut computation
Definition at line 420 of file MinSteinerTreeDirectedCut.h.
|
inline |
the non-duplicate cutpool for the separated Steiner cuts
Definition at line 316 of file MinSteinerTreeDirectedCut.h.
|
inline |
edge mapping m_pGraph -> m_pWeightedGraphPH
Definition at line 485 of file MinSteinerTreeDirectedCut.h.
|
inline |
edge -> id of lp variable
Definition at line 358 of file MinSteinerTreeDirectedCut.h.
|
inline |
lp variable ids of edges
Definition at line 370 of file MinSteinerTreeDirectedCut.h.
|
inline |
edge mapping m_pWeightedGraphPH -> m_pGraph
Definition at line 488 of file MinSteinerTreeDirectedCut.h.
|
inlineoverridevirtual |
generates the first subproblem
Implements abacus::Master.
Definition at line 319 of file MinSteinerTreeDirectedCut.h.
|
inline |
id -> edge
Definition at line 373 of file MinSteinerTreeDirectedCut.h.
|
inline |
Get the maximum flow module used by separation algorithm.
Definition at line 248 of file MinSteinerTreeDirectedCut.h.
|
inline |
id -> node
Definition at line 376 of file MinSteinerTreeDirectedCut.h.
|
inline |
the primal heuristic module
Definition at line 311 of file MinSteinerTreeDirectedCut.h.
|
inline |
returns the variable assigned to edge e
Definition at line 391 of file MinSteinerTreeDirectedCut.h.
|
inline |
returns the variable assigned to the twin of edge e
Definition at line 394 of file MinSteinerTreeDirectedCut.h.
|
inline |
the directed graph, i.e., the bidirection of the input graph
Definition at line 328 of file MinSteinerTreeDirectedCut.h.
|
inline |
increases the number of separated directed cuts by 1
Definition at line 460 of file MinSteinerTreeDirectedCut.h.
|
inline |
increases the number of separated directed cuts
Definition at line 457 of file MinSteinerTreeDirectedCut.h.
|
overrideprotectedvirtual |
insert variables and base constraints
Reimplemented from abacus::Master.
Definition at line 1203 of file MinSteinerTreeDirectedCut.h.
|
overrideprotectedvirtual |
read/set parameters from file
Reimplemented from abacus::Master.
Definition at line 1141 of file MinSteinerTreeDirectedCut.h.
|
inline |
returns true iff original edge is contained in optimum solution
Definition at line 322 of file MinSteinerTreeDirectedCut.h.
|
inline |
boolean array of terminal status
Definition at line 355 of file MinSteinerTreeDirectedCut.h.
|
inline |
true if n is a terminal
Definition at line 352 of file MinSteinerTreeDirectedCut.h.
|
inline |
terminal yes/no (in m_pWeightedGraphPH)
Definition at line 479 of file MinSteinerTreeDirectedCut.h.
|
inline |
maximum nr of cutting planes
Definition at line 417 of file MinSteinerTreeDirectedCut.h.
|
inline |
the maximum pool size during the algorithm
Definition at line 444 of file MinSteinerTreeDirectedCut.h.
|
inline |
parameter: compute minimum cardinality cuts
Definition at line 426 of file MinSteinerTreeDirectedCut.h.
|
inline |
returns the number of edges
Definition at line 334 of file MinSteinerTreeDirectedCut.h.
|
inline |
returns number of undirected edges, i.e., nEdges()/2
Definition at line 337 of file MinSteinerTreeDirectedCut.h.
|
inline |
number of nodes of the graph
Definition at line 331 of file MinSteinerTreeDirectedCut.h.
|
inline |
npde -> id of lp variable
Definition at line 361 of file MinSteinerTreeDirectedCut.h.
|
inline |
lp variable ids of nodes
Definition at line 367 of file MinSteinerTreeDirectedCut.h.
|
inline |
nodes of the graph
Definition at line 364 of file MinSteinerTreeDirectedCut.h.
|
inline |
total number of separated directed cuts
Definition at line 463 of file MinSteinerTreeDirectedCut.h.
|
inline |
number of terminals
Definition at line 343 of file MinSteinerTreeDirectedCut.h.
|
private |
|
inline |
initial pool size
Definition at line 454 of file MinSteinerTreeDirectedCut.h.
|
inline |
timer for primal heuristics
Definition at line 500 of file MinSteinerTreeDirectedCut.h.
|
inline |
solve relaxed LP or ILP
Definition at line 397 of file MinSteinerTreeDirectedCut.h.
|
inline |
the designated root node (special terminal)
Definition at line 340 of file MinSteinerTreeDirectedCut.h.
|
inline |
root node (in m_pWeightedGraphPH)
Definition at line 482 of file MinSteinerTreeDirectedCut.h.
|
inline |
strategy for saturating edges during separation; Only relevant for nested cuts
Definition at line 438 of file MinSteinerTreeDirectedCut.h.
|
inline |
strategy for separating directed Steiner cuts; Only relevant for nested cuts
Definition at line 435 of file MinSteinerTreeDirectedCut.h.
|
inline |
timer for separation
Definition at line 494 of file MinSteinerTreeDirectedCut.h.
|
inline |
Set the config file to use that overrides all other settings.
Definition at line 232 of file MinSteinerTreeDirectedCut.h.
|
inline |
Set the maximum flow module to be used for separation.
Definition at line 245 of file MinSteinerTreeDirectedCut.h.
|
inline |
Set maximum number of added cutting planes per iteration.
Definition at line 263 of file MinSteinerTreeDirectedCut.h.
|
inline |
nr of iterations in the root node
Definition at line 414 of file MinSteinerTreeDirectedCut.h.
|
inline |
Set factor for the initial size of the cutting pool.
Definition at line 303 of file MinSteinerTreeDirectedCut.h.
|
inline |
Set the module option for the primal heuristic.
Definition at line 306 of file MinSteinerTreeDirectedCut.h.
|
inline |
Set primal heuristic call strategy.
Definition at line 296 of file MinSteinerTreeDirectedCut.h.
|
inline |
solution value of the root
Definition at line 411 of file MinSteinerTreeDirectedCut.h.
|
inline |
Set saturation strategy for nested cuts.
Definition at line 286 of file MinSteinerTreeDirectedCut.h.
|
inline |
Set separation strategy for nested cuts.
Definition at line 279 of file MinSteinerTreeDirectedCut.h.
|
inline |
shuffle ordering of terminals before each separation routine
Definition at line 441 of file MinSteinerTreeDirectedCut.h.
|
inline |
solution value after solving the problem, i.e., returns final primal bound
Definition at line 400 of file MinSteinerTreeDirectedCut.h.
|
inline |
get terminal with index i
Definition at line 349 of file MinSteinerTreeDirectedCut.h.
|
inline |
list of terminals (in m_pWeightedGraphPH)
Definition at line 476 of file MinSteinerTreeDirectedCut.h.
|
inline |
terminals in an array
Definition at line 346 of file MinSteinerTreeDirectedCut.h.
|
overrideprotectedvirtual |
store solution in EdgeArray
Reimplemented from abacus::Master.
Definition at line 1353 of file MinSteinerTreeDirectedCut.h.
|
inline |
timer for minimum st-cut computations. Measures updates + algorithm
Definition at line 497 of file MinSteinerTreeDirectedCut.h.
|
inline |
the twin edge, i.e. twin[(u,v)] = (v,u)
Definition at line 385 of file MinSteinerTreeDirectedCut.h.
|
inline |
Definition at line 388 of file MinSteinerTreeDirectedCut.h.
| void ogdf::MinSteinerTreeDirectedCut< T >::Master::updateBestSolution | ( | double * | values | ) |
updates best found solution
Definition at line 1423 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 1438 of file MinSteinerTreeDirectedCut.h.
|
inline |
Switch computation of back-cuts on or off.
Definition at line 273 of file MinSteinerTreeDirectedCut.h.
|
inline |
Switch usage of degree constraints (like indeg <= 1) on or off.
Definition at line 251 of file MinSteinerTreeDirectedCut.h.
|
inline |
Switch usage of flow balance constraints on or off.
Definition at line 260 of file MinSteinerTreeDirectedCut.h.
|
inline |
Switch usage of constraints x_uv + x_vu <= 1 on or off.
Definition at line 257 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 254 of file MinSteinerTreeDirectedCut.h.
|
inline |
Switch usage of the cardinality heuristic (minimum-cardinality cuts) on or off.
Definition at line 293 of file MinSteinerTreeDirectedCut.h.
|
inline |
Switch computation of nested cuts on or off.
Definition at line 276 of file MinSteinerTreeDirectedCut.h.
|
inline |
Switch terminal shuffling before separation on or off.
Definition at line 270 of file MinSteinerTreeDirectedCut.h.
|
inline |
Definition at line 473 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: add constraints concerning the indegree of a node, like: indeg <= 1 for all vertices
Definition at line 607 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: add flow balance constraints for Steiner nodes n: outdeg(n) >= indeg(n)
Definition at line 611 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: add GSEC2 constraints yes/no, i.e. x_uv + x_vu <= 1
Definition at line 605 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 609 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: compute back cuts yes/no i.e., outgoing edges of the root-set
Definition at line 618 of file MinSteinerTreeDirectedCut.h.
|
private |
best found solution
Definition at line 570 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: primal heuristic (PH) call strategy
Definition at line 650 of file MinSteinerTreeDirectedCut.h.
|
private |
edge costs
Definition at line 544 of file MinSteinerTreeDirectedCut.h.
|
private |
problem dependent config file
Definition at line 514 of file MinSteinerTreeDirectedCut.h.
|
private |
edge -> id
Definition at line 539 of file MinSteinerTreeDirectedCut.h.
|
private |
id -> edge
Definition at line 537 of file MinSteinerTreeDirectedCut.h.
|
private |
edge mapping m_pGraph -> m_pWeightedGraphPH
Definition at line 585 of file MinSteinerTreeDirectedCut.h.
|
private |
edge mapping m_pWeightedGraphPH -> m_pGraph
Definition at line 587 of file MinSteinerTreeDirectedCut.h.
|
private |
edge -> lp variable
Definition at line 546 of file MinSteinerTreeDirectedCut.h.
|
private |
Definition at line 571 of file MinSteinerTreeDirectedCut.h.
|
private |
node is terminal yes/no
Definition at line 560 of file MinSteinerTreeDirectedCut.h.
|
private |
is terminal yes/no (in m_pWeightedGraphPH)
Definition at line 581 of file MinSteinerTreeDirectedCut.h.
|
private |
the first directed arc in m_pGraph for an original edge
Definition at line 551 of file MinSteinerTreeDirectedCut.h.
|
private |
the second directed arc in m_pGraph for an original edge
Definition at line 553 of file MinSteinerTreeDirectedCut.h.
|
private |
the undirected edge in the original graph for each arc in m_pGraph
Definition at line 549 of file MinSteinerTreeDirectedCut.h.
|
private |
Definition at line 511 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: maximum nr of cutting planes per iteration
Definition at line 614 of file MinSteinerTreeDirectedCut.h.
|
private |
statistic number of cuts in pool
Definition at line 600 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: compute minimum cardinality cuts
Definition at line 642 of file MinSteinerTreeDirectedCut.h.
|
private |
number of undirected edges
Definition at line 535 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: compute nested cuts yes/no i.e., saturate all cut edges and recompute the mincut
Definition at line 620 of file MinSteinerTreeDirectedCut.h.
|
private |
statistics: nr of iterations in the root node of the b&b tree
Definition at line 526 of file MinSteinerTreeDirectedCut.h.
|
private |
node -> id
Definition at line 558 of file MinSteinerTreeDirectedCut.h.
|
private |
id -> node
Definition at line 556 of file MinSteinerTreeDirectedCut.h.
|
private |
node mapping m_pGraph -> m_pWeightedGraphPH
Definition at line 583 of file MinSteinerTreeDirectedCut.h.
|
private |
total number of separated directed cuts
Definition at line 602 of file MinSteinerTreeDirectedCut.h.
|
private |
nr of terminals
Definition at line 562 of file MinSteinerTreeDirectedCut.h.
|
private |
the non-duplicate cut pool for the directed Steiner cuts
Definition at line 592 of file MinSteinerTreeDirectedCut.h.
|
private |
the bidirected graph
Definition at line 532 of file MinSteinerTreeDirectedCut.h.
|
private |
size of initial pool
Definition at line 596 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: factor for the initial size of the cutting pool
Definition at line 594 of file MinSteinerTreeDirectedCut.h.
|
private |
maximal size of the pool
Definition at line 598 of file MinSteinerTreeDirectedCut.h.
|
private |
Algorithm used for the primal heuristic.
Definition at line 517 of file MinSteinerTreeDirectedCut.h.
|
private |
timer for primal heuristics
Definition at line 657 of file MinSteinerTreeDirectedCut.h.
|
private |
edge weighted bidirected graph; used and modified for primal heuristics
Definition at line 577 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: indicates whether we solve the relaxed problem (LP) or the ILP
Definition at line 520 of file MinSteinerTreeDirectedCut.h.
|
private |
statistics: solution value of the relaxed master problem
Definition at line 523 of file MinSteinerTreeDirectedCut.h.
|
private |
the virtual root of our graph. This node is a terminal.
Definition at line 567 of file MinSteinerTreeDirectedCut.h.
|
private |
root node in m_pWeightedGraphPH
Definition at line 589 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: saturation strategy, only important if nested cuts are computed
Definition at line 636 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: separation strategy, only important if nested cuts are computed
Definition at line 629 of file MinSteinerTreeDirectedCut.h.
|
private |
timer for separation
Definition at line 653 of file MinSteinerTreeDirectedCut.h.
|
private |
parameter: shuffle the list of terminals right before separation
Definition at line 616 of file MinSteinerTreeDirectedCut.h.
|
private |
list of terminal nodes (in m_pWeightedGraphPH)
Definition at line 579 of file MinSteinerTreeDirectedCut.h.
|
private |
terminal index -> terminal node
Definition at line 564 of file MinSteinerTreeDirectedCut.h.
|
private |
timer for minimum st-cut computations. Measures updates + algorithm
Definition at line 655 of file MinSteinerTreeDirectedCut.h.
|
private |
the twin edges (u,v) <-> (v,u)
Definition at line 541 of file MinSteinerTreeDirectedCut.h.
|
private |
the original weighted graph
Definition at line 529 of file MinSteinerTreeDirectedCut.h.
