|
| | CP_MasterBase (const ClusterGraph &C, int heuristicLevel=1, int heuristicRuns=2, double heuristicOEdgeBound=0.3, int heuristicNPermLists=5, int kuratowskiIterations=3, int subdivisions=10, int kSupportGraphs=3, double kuratowskiHigh=0.7, double kuratowskiLow=0.3, bool perturbation=false, double branchingGap=0.4, const char *time="00:05:00") |
| | Construction and default values.
|
| |
| virtual | ~CP_MasterBase () |
| | Destruction.
|
| |
| int | addedCConstraints () const |
| |
| int | addedKConstraints () const |
| |
| double | epsilon () const |
| | Returns the objective function coefficient of C-edges.
|
| |
| const ClusterGraph * | getClusterGraph () const |
| | Returns a pointer to the given Clustergraph.
|
| |
| virtual void | getConnectionOptimalSolutionEdges (List< NodePair > &edges) const |
| | Returns nodePairs of connecting optimal solution edges in list edges.
|
| |
| abacus::StandardPool< abacus::Constraint, abacus::Variable > * | getCutConnPool () |
| | Returns cut pool for connectivity.
|
| |
| abacus::StandardPool< abacus::Constraint, abacus::Variable > * | getCutKuraPool () |
| | Returns cut pool for planarity.
|
| |
| double | getDualBound () |
| |
| const Graph * | getGraph () const |
| | Returns a pointer to the underlying Graph.
|
| |
| double | getHeuristicFractionalBound () const |
| |
| int | getHeuristicLevel () const |
| |
| int | getHeuristicRuns () const |
| |
| double | getKBoundHigh () const |
| |
| double | getKBoundLow () const |
| |
| int | getKIterations () const |
| |
| bool | getMPHeuristic () const |
| |
| int | getNKuratowskiSupportGraphs () const |
| |
| int | getNSubdivisions () const |
| |
| int | getNumAddVariables () const |
| |
| int | getNumInactiveVars () |
| |
| double | getPrimalBound () |
| |
| const char * | getStdConstraintsFileName () |
| | The name of the file that contains the standard, i.e., non-cut, constraints (may be deleted by ABACUS and shouldn't be stored twice)
|
| |
| double | getStrongConstraintViolation () const |
| |
| double | getStrongVariableViolation () const |
| |
| void | heuristicLevel (int level) |
| |
| double | intGap () |
| | Returns a value that allows to distinguish result values when connection edges (tiny negative cost) are added.
|
| |
| int | nMaxVars () const |
| | Returns the number of variables.
|
| |
| int | numberOfHeuristicPermutationLists () const |
| |
| bool | perturbation () const |
| |
| void | printGraph (const Graph &G) |
| |
| void | setHeuristicFractionalBound (double b) |
| |
| void | setHeuristicPermutationLists (int n) |
| |
| void | setHeuristicRuns (int n) |
| |
| void | setKBoundHigh (double n) |
| |
| void | setKBoundLow (double n) |
| |
| void | setKIterations (int n) |
| |
| void | setMPHeuristic (bool b) |
| | Switches use of lower bound heuristic.
|
| |
| void | setNHeuristicRuns (int n) |
| |
| void | setNKuratowskiSupportGraphs (int n) |
| |
| void | setNSubdivisions (int n) |
| |
| void | setNumAddVariables (int i) |
| |
| void | setPertubation (bool b) |
| |
| void | setPortaFile (bool b) |
| | If set to true, PORTA output is written in a file.
|
| |
| void | setStrongConstraintViolation (double d) |
| |
| void | setStrongVariableViolation (double d) |
| |
| void | setTimeLimit (const char *s) |
| |
| virtual Graph * | solutionInducedGraph () |
| | Returns the optimal solution induced Clustergraph.
|
| |
| void | updateAddedCCons (int n) |
| |
| void | updateAddedKCons (int n) |
| |
| virtual void | updateBestSubGraph (List< NodePair > &connection) |
| | Updates the "best" Subgraph m_solutionGraph found so far and fills connection with.
|
| |
| bool & | useDefaultCutPool () |
| | Returns true if default cut pool is used. Otherwise, separate connectivity and Kuratowski pools are generated and used.
|
| |
| | Master (const char *problemName, bool cutting, bool pricing, OptSense::SENSE optSense=OptSense::Unknown, double eps=1.0e-4, double machineEps=1.0e-7, double infinity=1.0e30, bool readParamFromFile=false) |
| | The constructor.
|
| |
| virtual | ~Master () |
| | The destructor.
|
| |
| BRANCHINGSTRAT | branchingStrategy () const |
| | Returns the branching strategy.
|
| |
| void | branchingStrategy (BRANCHINGSTRAT strat) |
| | Changes the branching strategy to strat.
|
| |
| const ogdf::StopwatchCPU * | branchingTime () const |
| | Returns a pointer to the timer measuring the cpu time spent in finding and selecting the branching rules.
|
| |
| bool | check () const |
| | Can be used to control the correctness of the optimization if the value of the optimum solution has been loaded.
|
| |
| int | conElimAge () const |
| | Returns the age for the elimination of constraints.
|
| |
| void | conElimAge (int age) |
| | Changes the age for the elimination of constraints to age.
|
| |
| double | conElimEps () const |
| | Returns the zero tolerance for the elimination of constraints by the slack criterion.
|
| |
| void | conElimEps (double eps) |
| | Changes the tolerance for the elimination of constraints by the slack criterion to eps.
|
| |
| CONELIMMODE | conElimMode () const |
| | Returns the mode for the elimination of constraints.
|
| |
| void | conElimMode (CONELIMMODE mode) |
| | Changes the constraint elimination mode to mode.
|
| |
| StandardPool< Constraint, Variable > * | conPool () const |
| | Returns a pointer to the default pool storing the constraints of the problem formulation.
|
| |
| StandardPool< Constraint, Variable > * | cutPool () const |
| | Returns a pointer to the default pool for the generated cutting planes.
|
| |
| bool | cutting () const |
| |
| int | dbThreshold () const |
| | Returns the number of optimizations of a subproblem until sons are created.
|
| |
| void | dbThreshold (int threshold) |
| | Sets the number of optimizations of a subproblem until sons are created in Sub::branching().
|
| |
| OSISOLVER | defaultLpSolver () const |
| | returns the Lp Solver.
|
| |
| void | defaultLpSolver (OSISOLVER osiSolver) |
| | Changes the default Lp solver to osiSolver.
|
| |
| bool | delayedBranching (int nOpt) const |
| | Returns true if the number of optimizations nOpt of a subproblem exceeds the delayed branching threshold, false otherwise.
|
| |
| bool | eliminateFixedSet () const |
| |
| void | eliminateFixedSet (bool turnOn) |
| | Turns the elimination of fixed and set variables on or off.
|
| |
| ENUMSTRAT | enumerationStrategy () const |
| | Returns the enumeration strategy.
|
| |
| virtual int | enumerationStrategy (const Sub *s1, const Sub *s2) |
| | Analyzes the enumeration strategy set in the parameter file .abacus and calls the corresponding comparison function for the subproblems s1 and s2.
|
| |
| void | enumerationStrategy (ENUMSTRAT strat) |
| | Changes the enumeration strategy to strat.
|
| |
| bool | fixSetByRedCost () const |
| |
| void | fixSetByRedCost (bool on) |
| | Turns fixing and setting variables by reduced cost on or off.
|
| |
| double | guarantee () const |
| | Can be used to access the guarantee which can be given for the best known feasible solution.
|
| |
| bool | guaranteed () const |
| | Can be used to check if the guarantee requirements are fulfilled.
|
| |
| int | highestLevel () const |
| | Returns the highest level in the tree which has been reached during the implicit enumeration.
|
| |
| History * | history () const |
| | Returns a pointer to the object storing the solution history of this branch and cut problem.
|
| |
| const ogdf::StopwatchCPU * | improveTime () const |
| | Returns a pointer to the timer measuring the cpu time spent in the heuristics for the computation of feasible solutions.
|
| |
| bool | knownOptimum (double &optVal) const |
| | Opens the file specified with the parameter OptimumFileName in the configuration file .abacus and tries to find a line with the name of the problem instance (as specified in the constructor of Master) as first string.
|
| |
| LpMasterOsi * | lpMasterOsi () const |
| |
| const ogdf::StopwatchCPU * | lpSolverTime () const |
| | Return a pointer to the timer measuring the cpu time required by the LP solver.
|
| |
| const ogdf::StopwatchCPU * | lpTime () const |
| | Returns a pointer to the timer measuring the cpu time spent in members of the LP-interface.
|
| |
| int | maxConAdd () const |
| | Returns the maximal number of constraints which should be added in every iteration of the cutting plane algorithm.
|
| |
| void | maxConAdd (int max) |
| | Sets the maximal number of constraints that are added in an iteration of the cutting plane algorithm.
|
| |
| int | maxConBuffered () const |
| | Returns the size of the buffer for generated constraints in the cutting plane algorithm.
|
| |
| void | maxConBuffered (int max) |
| | Changes the maximal number of constraints that are buffered in an iteration of the cutting plane algorithm.
|
| |
| int64_t | maxCowTime () const |
| | Returns the maximal wall-clock time (in seconds) which can be used by the optimization.
|
| |
| void | maxCowTime (const string &t) |
| | Sets the maximally allowed wall-clock time for the optimization to t.
|
| |
| void | maxCowTime (int64_t seconds) |
| | Sets the maximally allowed wall-clock time to seconds.
|
| |
| string | maxCowTimeAsString () const |
| | Returns the maximal wall-clock time (as string hh:mm:ss) which can be used by the optimization.
|
| |
| int64_t | maxCpuTime () const |
| | Returns the maximal cpu time (in seconds) which can be used by the optimization.
|
| |
| void | maxCpuTime (const string &t) |
| | Sets the maximally allowed cpu time for the optimization to t.
|
| |
| void | maxCpuTime (int hour, int min, int sec) |
| | Sets the maximally allowed cpu time for the optimization to hour, min, sec.
|
| |
| void | maxCpuTime (int64_t seconds) |
| | Sets the maximally allowed cpu time to seconds.
|
| |
| string | maxCpuTimeAsString () const |
| | Returns the maximal cpu time (as string hh:mm:ss) which can be used by the optimization.
|
| |
| int | maxIterations () const |
| | Returns the maximal number of iterations per subproblem optimization (-1 means no iteration limit).
|
| |
| void | maxIterations (int max) |
| | Changes the default value for the maximal number of iterations of the optimization of a subproblem.
|
| |
| int | maxLevel () const |
| | Returns the maximal depth up to which the enumeration should be performed.
|
| |
| void | maxLevel (int ml) |
| | This version of the function maxLevel() changes the maximal enumeration depth.
|
| |
| int | maxNSub () const |
| | Returns the maximal number of subproblems to be processed.
|
| |
| void | maxNSub (int ml) |
| | Changes the maximal number of subproblems to ml.
|
| |
| int | maxVarAdd () const |
| | Returns the maximal number of variables which should be added in the column generation algorithm.
|
| |
| void | maxVarAdd (int max) |
| | Changes the maximal number of variables that are added in an iteration of the subproblem optimization.
|
| |
| int | maxVarBuffered () const |
| | Returns the size of the buffer for the variables generated in the column generation algorithm.
|
| |
| void | maxVarBuffered (int max) |
| | Changes the maximal number of variables that are buffered in an iteration of the subproblem optimization.
|
| |
| int | minDormantRounds () const |
| | Returns the maximal number of rounds, i.e., number of subproblem optimizations, a subproblem is dormant.
|
| |
| void | minDormantRounds (int nRounds) |
| | Sets the number of rounds a subproblem should stay dormant to nRounds.
|
| |
| int | nBranchingVariableCandidates () const |
| | Returns the number of variables that should be tested for the selection of the branching variable.
|
| |
| void | nBranchingVariableCandidates (int n) |
| | Sets the number of tested branching variable candidates to n.
|
| |
| bool | newRootReOptimize () const |
| |
| void | newRootReOptimize (bool on) |
| | Turns the reoptimization of new root nodes of the remaining branch and bound tree on or off.
|
| |
| int | nLp () const |
| | Returns the number of optimized linear programs (only LP-relaxations).
|
| |
| int | nNewRoot () const |
| | Returns the number of root changes of the remaining branch-and-cut tree.
|
| |
| int | nStrongBranchingIterations () const |
| | The number of simplex iterations that are performed when testing candidates for branching variables within strong branching.
|
| |
| void | nStrongBranchingIterations (int n) |
| | Sets the number of simplex iterations that are performed when testing candidates for branching variables within strong branching.
|
| |
| int | nSub () const |
| | returns the number of generated subproblems.
|
| |
| int | nSubSelected () const |
| | Returns the number of subproblems which have already been selected from the set of open subproblems.
|
| |
| bool | objInteger () const |
| | If true then we assume that all feasible solutions have integral objective function values.
|
| |
| void | objInteger (bool b) |
| | Sets the assumption that the objective function values of all feasible solutions are integer.
|
| |
| OpenSub * | openSub () const |
| | Returns a pointer to the set of open subproblems.
|
| |
| STATUS | optimize () |
| | Performs the optimization by branch-and-bound.
|
| |
| const string & | optimumFileName () const |
| | Returns the name of the file that stores the optimum solutions.
|
| |
| void | optimumFileName (const char *name) |
| | Changes the name of the file in which the value of the optimum solution is searched.
|
| |
| const OptSense * | optSense () const |
| | Returns a pointer to the object holding the optimization sense of the problem.
|
| |
| virtual void | output () const |
| | Does nothing but can be redefined in derived classes for output before the timing statistics.
|
| |
| PRIMALBOUNDMODE | pbMode () const |
| | Returns the mode of the primal bound initialization.
|
| |
| void | pbMode (PRIMALBOUNDMODE mode) |
| | Sets the mode of the primal bound initialization to mode.
|
| |
| bool | pricing () const |
| |
| int | pricingFreq () const |
| | Returns the number of linear programs being solved between two additional pricing steps.
|
| |
| void | pricingFreq (int f) |
| | Sets the number of linear programs being solved between two additional pricing steps to f.
|
| |
| const ogdf::StopwatchCPU * | pricingTime () const |
| | Returns a pointer to the timer measuring the cpu time spent in pricing.
|
| |
| void | printGuarantee () const |
| | Writes the guarantee nicely formated on the output stream associated with this object.
|
| |
| bool | printLP () const |
| |
| void | printLP (bool on) |
| | Turns the output of the linear program in every iteration on or off.
|
| |
| void | printParameters () const |
| | Writes all parameters of the class Master together with their values to the global output stream.
|
| |
| const string & | problemName () const |
| | Returns the name of the instance being optimized (as specified in the constructor of this class).
|
| |
| double | requiredGuarantee () const |
| | The guarantee specification for the optimization.
|
| |
| void | requiredGuarantee (double g) |
| | Changes the guarantee specification tp g.
|
| |
| Sub * | root () const |
| | Can be used to access the root node of the branch-and-bound tree.
|
| |
| Sub * | rRoot () const |
| |
| const ogdf::StopwatchCPU * | separationTime () const |
| | Returns a pointer to the timer measuring the cpu time spent in the separation of cutting planes.
|
| |
| virtual bool | setSolverParameters (OsiSolverInterface *interface, bool solverIsApprox) |
| | Sets solver specific parameters.
|
| |
| bool | showAverageCutDistance () const |
| |
| void | showAverageCutDistance (bool on) |
| | Turns the output of the average distance of the added cuts from the fractional solution on or off.
|
| |
| int | skipFactor () const |
| | Returns the frequency of subproblems in which constraints or variables should be generated.
|
| |
| void | skipFactor (int f) |
| | Sets the frequency for constraint and variable generation to f.
|
| |
| SKIPPINGMODE | skippingMode () const |
| | Returns the skipping strategy.
|
| |
| void | skippingMode (SKIPPINGMODE mode) |
| | Sets the skipping strategy to mode.
|
| |
| bool | solveApprox () const |
| | True, if an approximative solver should be used.
|
| |
| STATUS | status () const |
| | Returns the status of the Master.
|
| |
| int | tailOffNLp () const |
| | Returns the number of linear programs considered in the tailing off analysis.
|
| |
| void | tailOffNLp (int n) |
| | Sets the number of linear programs considered in the tailing off analysis to n.
|
| |
| double | tailOffPercent () const |
| | Returns the minimal change of the dual bound for the tailing off analysis in percent.
|
| |
| void | tailOffPercent (double p) |
| | Sets the minimal change of the dual bound for the tailing off analysis to p.
|
| |
| const ogdf::StopwatchWallClock * | totalCowTime () const |
| | Returns a pointer to the timer measuring the total wall clock time.
|
| |
| const ogdf::StopwatchCPU * | totalTime () const |
| | returns a pointer to the timer measuring the total cpu time for the optimization.
|
| |
| int | varElimAge () const |
| | Returns the age for the elimination of variables by the reduced cost criterion.
|
| |
| void | varElimAge (int age) |
| | Changes the age for the elimination of variables by the reduced cost criterion to age.
|
| |
| double | varElimEps () const |
| | Returns the zero tolerance for the elimination of variables by the reduced cost criterion.
|
| |
| void | varElimEps (double eps) |
| | Changes the tolerance for the elimination of variables by the reduced cost criterion to eps.
|
| |
| VARELIMMODE | varElimMode () const |
| | Returns the mode for the elimination of variables.
|
| |
| void | varElimMode (VARELIMMODE mode) |
| | Changes the variable elimination mode to mode.
|
| |
| StandardPool< Variable, Constraint > * | varPool () const |
| | Returns a pointer to the default pool storing the variables.
|
| |
| VBCMODE | vbcLog () const |
| | Returns the mode of output for the Vbc-Tool.
|
| |
| void | vbcLog (VBCMODE mode) |
| | Changes the mode of output for the Vbc-Tool to mode.
|
| |
| 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.
|
| |
| | 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.
|
| |
| virtual | ~AbacusRoot () |
| | The destructor.
|
| |
Inheritance diagram for ogdf::cluster_planarity::CP_MasterBase:
