|
| | CPlanaritySub (abacus::Master *master) |
| |
| | CPlanaritySub (abacus::Master *master, abacus::Sub *father, abacus::BranchRule *branchRule, List< abacus::Constraint * > &criticalConstraints) |
| |
| virtual | ~CPlanaritySub () |
| |
| virtual abacus::Sub * | generateSon (abacus::BranchRule *rule) override |
| | Returns a pointer to an object of a problem specific subproblem, which is generated from the current subproblem by branching rule rule.
|
| |
| | Sub (Master *master, double conRes, double varRes, double nnzRes, bool relativeRes=true, ArrayBuffer< PoolSlot< Constraint, Variable > * > *constraints=nullptr, ArrayBuffer< PoolSlot< Variable, Constraint > * > *variables=nullptr) |
| | Creates the root node of the enumeration tree.
|
| |
| | Sub (Master *master, Sub *father, BranchRule *branchRule) |
| | Creates a non-root node of the enumeration tree.
|
| |
| virtual | ~Sub () |
| | The destructor only deletes the sons of the node.
|
| |
| Active< Constraint, Variable > * | actCon () const |
| | Returns a pointer to the currently active constraints.
|
| |
| Active< Variable, Constraint > * | actVar () const |
| | Returns a pointer to the currently active variables.
|
| |
| virtual int | addBranchingConstraint (PoolSlot< Constraint, Variable > *slot) |
| | Adds a branching constraint to the constraint buffer.
|
| |
| int | addConBufferSpace () const |
| | Can be used to determine the maximal number of the constraints which still can be added to the constraint buffer.
|
| |
| int | addVarBufferSpace () const |
| | Can be used to determine the maximal number of the variables which still can be added to the variable buffer.
|
| |
| bool | ancestor (const Sub *sub) const |
| | Returns true if this subproblem is an ancestor of the subproblem sub, false otherwise.
|
| |
| BranchRule * | branchRule () const |
| | Returns a pointer to the branching rule of the subproblem.
|
| |
| Constraint * | constraint (int i) const |
| | Returns a pointer to the i-th active constraint.
|
| |
| double | dualBound () const |
| | Returns a bound which is "better" than the optimal solution of the subproblem w.r.t. the sense of the optimization.
|
| |
| void | dualBound (double x) |
| | Sets the dual bound of the subproblem.
|
| |
| const Sub * | father () const |
| | Returns a pointer to the father of the subproblem in the branch-and-bound tree.
|
| |
| bool | forceExactSolver () const |
| | Returns whether using the exact solver is forced.
|
| |
| FSVarStat * | fsVarStat (int i) const |
| | Returns a pointer to the status of fixing/setting of the i-th variable.
|
| |
| int | id () const |
| | Returns the identity number of the subproblem.
|
| |
| void | ignoreInTailingOff () |
| | Can be used to control better the tailing-off effect.
|
| |
| double | lBound (int i) const |
| | Can be used to access the lower of an active variable of the subproblem.
|
| |
| void | lBound (int i, double l) |
| | Sets the local lower bound of variable i to l.
|
| |
| int | level () const |
| | Returns the level of the subproblem in the branch-and-bound tree.
|
| |
| double | lowerBound () const |
| | Returns a lower bound on the optimal solution of the subproblem.
|
| |
| LpSub * | lp () const |
| | Returns a pointer to the linear program of the subproblem.
|
| |
| LPVARSTAT * | lpVarStat (int i) const |
| | Returns a pointer to the status of the variable i in the last solved linear program.
|
| |
| Master * | master () |
| | Returns the master of the optimization.
|
| |
| const Master * | master () const |
| | Returns the const master of the optimization.
|
| |
| int | maxCon () const |
| | Returns the maximum number of constraints which can be handled without reallocation.
|
| |
| void | maxIterations (int max) |
| | Sets the maximal number of iterations in the cutting plane phase.
|
| |
| int | maxVar () const |
| | Returns the maximum number of variables which can be handled without reallocation.
|
| |
| int | nCon () const |
| | Returns the number of active constraints.
|
| |
| int | nDormantRounds () const |
| |
| double | nnzReserve () const |
| | Returns the additional space for nonzero elements of the constraint matrix when it is passed to the LP-solver.
|
| |
| int | nVar () const |
| | Returns the number of active variables.
|
| |
| bool | objAllInteger () const |
| | Tests if all active variables and objective function coefficients are integer.
|
| |
| bool | relativeReserve () const |
| |
| virtual void | removeCon (int i) |
| | Adds a single constraint to the set of constraints which are removed from the active set at the beginning of the next iteration.
|
| |
| virtual void | removeCons (ArrayBuffer< int > &remove) |
| | Adds constraints to the buffer of the removed constraints.
|
| |
| void | removeVar (int i) |
| | Remove variable i from the set of active variables.
|
| |
| void | removeVars (ArrayBuffer< int > &remove) |
| | Removes the variables in remove from the set of active variables.
|
| |
| SlackStat * | slackStat (int i) const |
| | Returns a pointer to the status of the slack variable i in the last solved linear program.
|
| |
| STATUS | status () const |
| | Returns the status of the subproblem optimization.
|
| |
| double | uBound (int i) const |
| | Can be used to access the upper of an active variable of the subproblem.
|
| |
| void | uBound (int i, double u) |
| | Sets the local upper bound of variable i to u.
|
| |
| double | upperBound () const |
| | Returns an upper bound on the optimal solution of the subproblem.
|
| |
| Variable * | variable (int i) const |
| | Returns a pointer to the i-th active variable.
|
| |
| double | xVal (int i) const |
| | Returns the value of the i-th variable in the last solved linear program.
|
| |
| double | yVal (int i) const |
| | Returns the value of the i-th dual variable in the last solved linear program.
|
| |
| virtual | ~AbacusRoot () |
| | The destructor.
|
| |
|
| int | addPoolCons (ArrayBuffer< abacus::Constraint * > &cons, abacus::StandardPool< abacus::Constraint, abacus::Variable > *pool) |
| | Adds the given constraints to the given pool.
|
| |
| bool | checkCConnectivity (const GraphCopy &support) |
| | Checks if the cluster induced graphs and their complement are connected in the current solution.
|
| |
| bool | checkCConnectivityOld (const GraphCopy &support) |
| |
| int | clusterBags (ClusterGraph &CG, cluster c) |
| |
| virtual bool | feasible () override |
| | Must check the feasibility of a solution of the LP-relaxation.
|
| |
| node | getRepresentative (node v, NodeArray< node > &parent) |
| | run through the pointer list parent and return the representative i.e. the node with parent[v] == v
|
| |
| virtual int | improve (double &primalValue) override |
| | Can be redefined in order to implement primal heuristics for finding feasible solutions.
|
| |
| virtual int | makeFeasible () override |
| | The default implementation of makeFeasible()does nothing.
|
| |
| virtual int | optimize () override |
| | Performs the optimization of the subproblem.
|
| |
| virtual int | pricing () override |
| | Should generate inactive variables which do not price out correctly.
|
| |
| int | repair () |
| |
| virtual int | selectBranchingVariable (int &variable) override |
| | Chooses a branching variable.
|
| |
| virtual int | selectBranchingVariableCandidates (ArrayBuffer< int > &candidates) override |
| | Selects candidates for branching variables.
|
| |
| virtual int | separate () override |
| | Must be redefined in derived classes for the generation of cutting planes.
|
| |
| int | separateCutPool (abacus::StandardPool< abacus::Constraint, abacus::Variable > *pool, double minViolation) |
| |
| int | separateReal (double minViolate) |
| | these functions are mainly reporting to let abacus think everthing is normal.
|
| |
| int | separateRealO (double minViolate) |
| |
| virtual int | solveLp () override |
| | Solves the LP-relaxation of the subproblem.
|
| |
| virtual void | activate () |
| | Can be used as an entrance point for problem specific activations.
|
| |
| virtual int | addCons (ArrayBuffer< Constraint * > &constraints, Pool< Constraint, Variable > *pool=nullptr, ArrayBuffer< bool > *keepInPool=nullptr, ArrayBuffer< double > *rank=nullptr) |
| | Tries to add new constraints to the constraint buffer and a pool.
|
| |
| virtual int | addCons (ArrayBuffer< PoolSlot< Constraint, Variable > * > &newCons) |
| | Adds constraints to the active constraints and the linear program.
|
| |
| virtual int | addVars (ArrayBuffer< PoolSlot< Variable, Constraint > * > &newVars) |
| | Adds both the variables in newVars to the set of active variables and to the linear program of the subproblem.
|
| |
| virtual int | addVars (ArrayBuffer< Variable * > &variables, Pool< Variable, Constraint > *pool=nullptr, ArrayBuffer< bool > *keepInPool=nullptr, ArrayBuffer< double > *rank=nullptr) |
| | Tries to add new variables to the variable buffer and a pool.
|
| |
| virtual void | basicConEliminate (ArrayBuffer< int > &remove) |
| | Retrieves all dynamic constraints having basic slack variable.
|
| |
| bool | betterDual (double x) const |
| | Returns true if x is better than the best known dual bound of the subproblem, false otherwise.
|
| |
| bool | boundCrash () const |
| | Returns true if the dual bound is worse than the best known primal bound, false otherwise.
|
| |
| virtual PHASE | branching () |
| | Performs branching.
|
| |
| virtual int | branchingOnVariable (ArrayBuffer< BranchRule * > &rules) |
| | Generates branching rules for two new subproblems by selecting a branching variable with the function selectBranchingVariable().
|
| |
| virtual LP::METHOD | chooseLpMethod (int nVarRemoved, int nConRemoved, int nVarAdded, int nConAdded) |
| | Controls the method used to solve a linear programming relaxation.
|
| |
| int | closeHalf (ArrayBuffer< int > &branchVar, VarType::TYPE branchVarType) |
| | Searches searches several possible branching variable of type branchVarType, with fraction as close to \(0.5\) as possible.
|
| |
| int | closeHalf (int &branchVar, VarType::TYPE branchVarType) |
| | Searches a branching variable of type branchVarType, with fraction as close to \(0.5\) as possible.
|
| |
| int | closeHalfExpensive (ArrayBuffer< int > &variables, VarType::TYPE branchVarType) |
| | Selects several candidates for branching variables of type branchVarType.
|
| |
| int | closeHalfExpensive (int &branchVar, VarType::TYPE branchVarType) |
| | Selects a single branching variable of type branchVarType, with fractional part close to \(0.5\) and high absolute objective function coefficient.
|
| |
| virtual int | compareBranchingSampleRanks (Array< double > &rank1, Array< double > &rank2) |
| | Compares the ranks of two branching samples.
|
| |
| virtual void | conEliminate (ArrayBuffer< int > &remove) |
| | Can be used as an entry point for application specific elimination of constraints.
|
| |
| virtual void | conRealloc (int newSize) |
| | Reallocates memory that at most newSize constraints can be handled in the subproblem.
|
| |
| virtual int | constraintPoolSeparation (int ranking=0, Pool< Constraint, Variable > *pool=nullptr, double minViolation=0.001) |
| | Tries to generate inactive constraints from a pool.
|
| |
| virtual PHASE | cutting () |
| | Iteratively solves the LP-relaxation, generates constraints and/or variables.
|
| |
| virtual void | deactivate () |
| | Can be used as entrance point for problem specific deactivations after the subproblem optimization.
|
| |
| virtual double | dualRound (double x) |
| |
| virtual bool | exceptionBranch () |
| | Can be used to specify a problem specific criteria for enforcing a branching step.
|
| |
| virtual bool | exceptionFathom () |
| | Can be used to specify a problem specific fathoming criterium that is checked before the separation or pricing.
|
| |
| virtual void | fathom (bool reoptimize) |
| | Fathoms a node and recursively tries to fathom its father.
|
| |
| virtual PHASE | fathoming () |
| | Fathoms the node, and if certain conditions are satisfied, also its ancestor.
|
| |
| virtual void | fathomTheSubTree () |
| | Fathoms all nodes in the subtree rooted at this subproblem.
|
| |
| int | findNonFixedSet (ArrayBuffer< int > &branchVar, VarType::TYPE branchVarType) |
| | Selects the first variables that are neither fixed nor set.
|
| |
| int | findNonFixedSet (int &branchVar, VarType::TYPE branchVarType) |
| | Selects the first variable that is neither fixed nor set.
|
| |
| virtual int | fix (int i, FSVarStat *newStat, bool &newValue) |
| | Fixes a variable.
|
| |
| virtual int | fixAndSet (bool &newValues) |
| | Tries to fix and set variables both by logical implications and reduced cost criteria.
|
| |
| virtual bool | fixAndSetTime () |
| | Controls if variables should be fixed or set when all variables price out correctly.
|
| |
| virtual void | fixByLogImp (ArrayBuffer< int > &variables, ArrayBuffer< FSVarStat * > &status) |
| | Should collect the numbers of the variables to be fixed in variable and the respective statuses in status.
|
| |
| virtual int | fixByRedCost (bool &newValues, bool saveCand) |
| | Tries to fix variables according to the reduced cost criterion.
|
| |
| virtual int | fixing (bool &newValues, bool saveCand=false) |
| | Tries to fix variables by reduced cost criteria and logical implications.
|
| |
| virtual int | generateBranchRules (ArrayBuffer< BranchRule * > &rules) |
| | Tries to find rules for splitting the current subproblem in further subproblems.
|
| |
| virtual LpSub * | generateLp () |
| | Instantiates an LP for the solution of the LP-relaxation in this subproblem.
|
| |
| virtual bool | goodCol (Column &col, Array< double > &row, double x, double lb, double ub) |
| |
| virtual double | guarantee () const |
| | May not be called if the lower bound is 0 and upper bound not equal to 0.
|
| |
| virtual bool | guaranteed () const |
| |
| bool | infeasible () |
| | Returns true if the subproblem does not contain a feasible solution, false otherwise.
|
| |
| virtual void | initializeCons (int maxCon) |
| | Initializes the active constraint set.
|
| |
| virtual int | initializeLp () |
| | Initializes the linear program.
|
| |
| virtual void | initializeVars (int maxVar) |
| | Initializes the active variable set.
|
| |
| virtual int | initMakeFeas (ArrayBuffer< InfeasCon * > &infeasCon, ArrayBuffer< Variable * > &newVars, Pool< Variable, Constraint > **pool) |
| | The default implementation of the virtual initMakeFeas() does nothing.
|
| |
| bool | integerFeasible () |
| | Can be used to check if the solution of the LP-relaxation is primally feasible if integrality is suficinet.
|
| |
| double | lpRankBranchingRule (BranchRule *branchRule, int iterLimit=-1) |
| | Computes the rank of a branching rule by modifying the linear programming relaxation of the subproblem according to the branching rule and solving it.
|
| |
| virtual void | nonBindingConEliminate (ArrayBuffer< int > &remove) |
| | Retrieves the dynamic constraints with slack exceeding the value given by the parameter ConElimEps.
|
| |
| virtual bool | pausing () |
| | Sometimes it is appropriate to put a subproblem back into the list of open subproblems.
|
| |
| virtual int | prepareBranching (bool &lastIteration) |
| | Is called before a branching step to remove constraints.
|
| |
| virtual bool | primalSeparation () |
| | Controls if during the cutting plane phase a (primal) separation step or a pricing step (dual separation) should be performed.
|
| |
| virtual double | rankBranchingRule (BranchRule *branchRule) |
| | Computes the rank of a branching rule.
|
| |
| virtual void | rankBranchingSample (ArrayBuffer< BranchRule * > &sample, Array< double > &rank) |
| | Computes for each branching rule of a branching sample a rank with the function rankBranchingRule().
|
| |
| void | redCostVarEliminate (ArrayBuffer< int > &remove) |
| | Retrieves all variables with "wrong" reduced costs.
|
| |
| virtual bool | removeNonLiftableCons () |
| |
| virtual void | reoptimize () |
| | Repeats the optimization of an already optimized subproblem.
|
| |
| virtual int | selectBestBranchingSample (int nSamples, ArrayBuffer< BranchRule * > **samples) |
| | Evaluates branching samples.
|
| |
| virtual void | selectCons () |
| | Is called before constraint are selected from the constraint buffer.
|
| |
| virtual void | selectVars () |
| | Is called before variables are selected from the variable buffer.
|
| |
| virtual int | set (int i, FSVarStat *newStat, bool &newValue) |
| | Sets a variable.
|
| |
| virtual int | set (int i, FSVarStat::STATUS newStat, bool &newValue) |
| | Sets a variable.
|
| |
| virtual int | set (int i, FSVarStat::STATUS newStat, double value, bool &newValue) |
| | Sets a variable.
|
| |
| virtual void | setByLogImp (ArrayBuffer< int > &variable, ArrayBuffer< FSVarStat * > &status) |
| | The default implementation of setByLogImp() does nothing.
|
| |
| virtual int | setByRedCost () |
| | Tries to set variables according to the reduced cost criterion.
|
| |
| virtual int | setting (bool &newValues) |
| | Tries to set variables by reduced cost criteria and logical implications like fixing().
|
| |
| virtual bool | solveApproxNow () |
| | The default implementation always returns false.
|
| |
| virtual bool | tailingOff () |
| | Called when a tailing off effect according to the parameters TailOffPercent and TailOffNLps is observed.
|
| |
| virtual void | varEliminate (ArrayBuffer< int > &remove) |
| | Entry point for application specific variable elimination.
|
| |
| virtual int | variablePoolSeparation (int ranking=0, Pool< Variable, Constraint > *pool=nullptr, double minViolation=0.001) |
| | Tries to generate inactive variables from a pool.
|
| |
| virtual void | varRealloc (int newSize) |
| | Reallocates memory that at most newSize variables can be handled in the subproblem.
|
| |
|
| enum | PHASE { Done
, Cutting
, Branching
, Fathoming
} |
| | The optimization of the subproblem can be in one of the following phases. More...
|
| |
| enum | STATUS { Unprocessed
, ActiveSub
, Dormant
, Processed
, Fathomed
} |
| | A subproblem can have different statuses. More...
|
| |
| 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".
|
| |
| Active< Constraint, Variable > * | actCon_ |
| | The active constraints of the subproblem.
|
| |
| Active< Variable, Constraint > * | actVar_ |
| | The active variables of the subproblem.
|
| |
| CutBuffer< Constraint, Variable > * | addConBuffer_ |
| | The buffer of the newly generated constraints.
|
| |
| CutBuffer< Variable, Constraint > * | addVarBuffer_ |
| | The buffer of the newly generated variables.
|
| |
| bool | allBranchOnSetVars_ |
| | If true, then the branching rule of the subproblem and of all ancestor on the path to the root node are branching on a binary variable.
|
| |
| double * | bInvRow_ |
| | A row of the basis inverse associated with the infeasible variable infeasVar_ or slack variable infeasCon_.
|
| |
| BranchRule * | branchRule_ |
| | The branching rule for the subproblem.
|
| |
| double | dualBound_ |
| | The dual bound of the subproblem.
|
| |
| Sub * | father_ |
| | A pointer to the father in the branch-and-cut tree.
|
| |
| Array< FSVarStat * > * | fsVarStat_ |
| | A pointer to an array storing the status of fixing and setting of the active variables.
|
| |
| bool | genNonLiftCons_ |
| | If true, then the management of non-liftable constraints is performed.
|
| |
| int | infeasCon_ |
| | The number of an infeasible constraint.
|
| |
| int | infeasVar_ |
| | The number of an infeasible variable.
|
| |
| int | lastIterConAdd_ |
| | The last iteration in which constraints have been added.
|
| |
| int | lastIterVarAdd_ |
| | The last iteration in which variables have been added.
|
| |
| Array< double > * | lBound_ |
| | A pointer to an array with the local lower bound of the active variables.
|
| |
| LpSub * | lp_ |
| | A pointer to the corresponding linear program.
|
| |
| LP::METHOD | lpMethod_ |
| | The solution method for the next linear program.
|
| |
| Array< LPVARSTAT * > * | lpVarStat_ |
| | A pointer to an array storing the status of each active variable in the linear program.
|
| |
| Master * | master_ |
| | A pointer to the corresponding master of the optimization.
|
| |
| int | nIter_ |
| | The number of iterations in the cutting plane phase.
|
| |
| ArrayBuffer< int > * | removeConBuffer_ |
| | The buffer of the constraints which are removed at the beginning of the next iteration.
|
| |
| ArrayBuffer< int > * | removeVarBuffer_ |
| | The buffer of the variables which are removed at the beginning of the next iteration.
|
| |
| Array< SlackStat * > * | slackStat_ |
| | A pointer to an array storing the statuses of the slack variables of the last solved linear program.
|
| |
| TailOff * | tailOff_ |
| | A pointer to the tailing off manager.
|
| |
| Array< double > * | uBound_ |
| | A pointer to an array with the local upper bounds of the active variables.
|
| |
| double * | xVal_ |
| | The last LP-solution.
|
| |
| double * | yVal_ |
| | The dual variables of the last linear program.
|
| |
Inheritance diagram for ogdf::cluster_planarity::CPlanaritySub:
