|
|
class implements an abstract base class for a subproblem of the enumeration, i.e., a node of the \ tree.
#include <sub.h>
Inheritance diagram for ABA_SUB::
|
|
Unprocessed, Active, Dormant, Processed,
Fathomed }
The optimization of the subproblem can be in one of the following phases:.
The constructor for the root node of the enumeration tree.
The constructor for non-root nodes of the enumeration tree.
Sets the dual bound of the subproblem, and if the subproblem is the root node of the enumeration tree and the new value is better than its dual bound, also the global dual bound is updated. It is an error if the dual bound gets worse.
This version of the function uBound() sets thef local upper bound of a variable.
With function removeVars() variables can be removed from the set of active variables.
If all variables are Binary or Integer and all objective function coefficients are integral, then all objective function values of feasible solutions are integral. The function objAllInteger() tests this condition for the current set of active variables.
Adds constraints to the buffer of the removed constraints, which will be removed at the beginning of the next iteration of the cutting plane algorithm.
The following version of the function removeCon() adds a single constraint to the set of constraints which are removed from the active set at the beginning of the next iteration.
Can be used to determine the maximal number of the constraints which still can be added to the constraint buffer.
Can be used to determine the maximal number of the variables which still can be added to the variable buffer.
Adds a branching constraint to the constraint buffer such that it is automatically added at the beginning of the cutting plane algorithm.
Does nothing but can be used as an entrance point for problem specific activations by a reimplementation in derived classes.
Can be used as entrance point for problem specific deactivations after the subproblem optimization.
Generates branching rules for two new subproblems by selecting a branching variable with the function selectBranchingVariable().
Selects depending on the branching variable strategy given by the parameter { BranchingStrategy} in the file { .abacus} candidates that for branching variables.
Evaluates branching samples (we denote a branching sample the set of rules defining all sons of a subproblem in the enumeration tree). For each sample the ranks are determined with the function rankBranchingSample(). The ranks of the various samples are compared with the function compareBranchingSample().
Computes for each branching rule of a branching sample a rank with the function rankBranchingRule().
Computes the rank of a branching rule by modifying the linear programming relaxation of the subproblem according to the branching rule and solving it. This modifiction is undone after the solution of the linear program.
Selects a single branching variable of type branchVarType, with fractional part close to 0.5 and high absolute objective function coefficient.
This version of the function closeHalfExpensive() selects several candidates for branching variables of type branchVarType.
Searches a branching variable of type branchVarType, with fraction as close to 0.5 as possible.
Searches searches several possible branching variable of type branchVarType, with fraction as close to 0.5 as possible.
The default implementation of the virtual initMakeFeas() does nothing.
The default implementation of makeFeasible() does nothing.
The default implementation of setByLogImp() does nothing.
The pure virtual function feasible() checks for the feasibility of a solution of the LP-relaxation.
Can be used to check if the solution of the LP-relaxation is primally feasible if for feasibility an integral value for all binary and integer variables is sufficient.
Is a virtual function which controls, if during the cutting plane phase a (primal) separation step or a pricing step (dual separation) should be performed.
Can be used as an entry point for application specific elimination of constraints by redefinig it in derived classes.
Retrieves the dynamic constraints with slack exceeding the value given by the parameter { ConElimEps}.
Provides an entry point for application specific variable elimination that can be implemented by redefining this function in a derived class.
Can be redefined in derived classes in order to implement primal heuristics for finding feasible solutions.
Returns a pointer to an object of a problem specific subproblem derived from the class ABA_SUB, which is generated from the current subproblem by the branching rule rule.
Reallocates memory that at most newSize variables can be handled in the subproblem.
Reallocates memory that at most newSize constraints can be handled in the subproblem.
Should collect the numbers of the variables to be fixed in variable and the respective statuses in status.
Tries to fix and set variables both by logical implications and reduced cost criteria.
Tries to set variables by reduced cost criteria and logical implications like fixing(), but instead of global conditions only locally valid conditions have to be satisfied.
Is called if the global lower bound of a \ node is still strictly less than the local upper bound, but either no violated cutting planes or variables are found, or we abort the cutting phase for some other strategic reason (e.g., observation of a tailing off effect, or branch pausing).
Fathoms the node, and if certain conditions are satisfied, also its ancestor.
Iteratively solves the LP-relaxation, generates constraints and/or variables.
Can be used to specify a problem specific fathoming criterium that is checked before the separation or pricing.
A pointer to an array storing the status of fixing and setting of the active variables. Although fixed and set variables are already kept at their value by the adaption of the lower and upper bounds, we store this information, since, e.g., a fixed or set variable should not be removed, but a variable with an upper bound equal to the lower bound can be removed.
A pointer to an array storing the status of each active variable in the linear program.
A pointer to an array storing the statuses of the slack variables of the last solved linear program.
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.
The buffer of the variables which are removed at the beginning of the next iteration.
The buffer of the constraints which are removed at the beginning of the next iteration.
A row of the basis inverse associated with the infeasible variable infeasVar_ or slack variable infeasCon_.
Returns 1, if a contradiction has been found, 0 otherwise.
Returns the value which the upper and lower bounds of a variable should take after it is fixed or set.
Allocates and initializes memory of the subproblem at the beginning of the optimization.
Deallocates the memory which is not required after the optimization of the subproblem.
Tries to add variables to restore infeasibilities detected at initialization time.
Is called if the LP is infeasible and adds inactive variables, which can make the LP feasible again, to the set of active variables.
Tries to set variables according to logical implications of already set and fixed variables.
Adds the variables stored in the pool slots of newVars to the set of active variables, but not to the linear program.
Adds the variables stored in the pool slots of newVars to the linear program. localStatus can specify a local status of fixing and setting.
Selects the master_->maxConAdd() best constraints from the buffered constraints and stores them in newCons.
If this member is true then the space reserve of the following three members varReserve_, conReserve_, and nnzReserve_ is relative to the initial numbers of constraints, variables, and nonzeros, respectively. Otherwise, the values are casted to integers and regarded as absolute values.
The number of subproblem optimizations the subproblem has already the status Dormant.
The variable is true if the function activate() has been called from the function _activate(). This memorization is required such that a deactivate() is only called when activate() has been called.
If this flag is set to true then the next LP-solution is ignored in the tailing-off control. The default value of the variable is false. It can be set to true by the function ignoreInTailingOff().
The method that was used to solve the last LP.
Indicates whether to force the use of an exact solver to prepare branching etc.
class implements an abstract base class for a subproblem of the enumeration, i.e., a node of the \ tree.
Definition at line 75 of file sub.h.
A subproblem can have different statuses:
Definition at line 98 of file sub.h.
The optimization of the subproblem can be in one of the following phases:.
Definition at line 111 of file sub.h.
The constructor for the root node of the enumeration tree.
The constructor for non-root nodes of the enumeration tree.
The destructor only deletes the sons of the node.
The deletion of allocated memory is already performed when the node is fathomed. We recursively call the destructors of all subproblems contained in the enumeration tree below this subproblem itself.
If a subproblem has no sons and its status is either Unprocessed or Dormant, then it is still contained in the set of open subproblems, where it is removed from.
Whether using the exact solver is forced.
Definition at line 2207 of file sub.h.
The level of the subproblem in the \ tree.
Definition at line 2212 of file sub.h.
The identity number of the subproblem.
Definition at line 2217 of file sub.h.
The status of the subproblem optimization.
Definition at line 2244 of file sub.h.
The number of active variables.
Definition at line 2259 of file sub.h.
The maximum number of variables which can be handled without reallocation.
Definition at line 2269 of file sub.h.
The number of active constraints.
Definition at line 2264 of file sub.h.
The maximum number of constraints which can be handled without reallocation.
Definition at line 2274 of file sub.h.
A lower bound on the optimal solution of the subproblem.
An upper bound on the optimal solution of the subproblem.
A bound which is better than the optimal solution of the subproblem in respect to the sense of the optimization, i.e., an upper for a maximization problem or a lower bound for a minimization problem, respectively.
Definition at line 2229 of file sub.h.
Sets the dual bound of the subproblem, and if the subproblem is the root node of the enumeration tree and the new value is better than its dual bound, also the global dual bound is updated. It is an error if the dual bound gets worse.
In normal applications it is not required to call this function explicitly. This is already done by \ during the subproblem optimization.
A pointer to the father of the subproblem in the \ tree.
Definition at line 2234 of file sub.h.
A pointer to the linear program of the subproblem.
Definition at line 2239 of file sub.h.
Sets the maximal number of iterations in the cutting plane phase.
Setting this value to 1 implies that no cuts are generated in the optimization process of the subproblem.
A pointer to the currently active constraints.
Definition at line 2249 of file sub.h.
A pointer to the currently active variables.
Definition at line 2254 of file sub.h.
A pointer to the i-th active constraint.
A pointer to the status of the slack variable i in the last solved linear program.
Definition at line 2202 of file sub.h.
A pointer to the i-th active variable.
Can be used to access the lower of an active variable of the subproblem.
This is the lower bound of the variable within the current subproblem which can differ from its global lower bound.
The lower bound of the i-th variable.
Definition at line 2168 of file sub.h.
