ABACUS: ABA_SUB Class Reference

A subproblem can have different statuses:

Parameters:

	Unprocessed	The status after generation, but before optimization of the subproblem.
	Active	The subproblem is currently processed.
	Dormant	The subproblem is partially processed and waiting in the set of open subproblems for further optimization.
	Processed	The subproblem is completely processed but could not be fathomed.
	Fathomed	The subproblem is fathomed.

Enumerator:

Unprocessed
Active
Dormant
Processed
Fathomed

Definition at line 98 of file sub.h.

enum ABA_SUB::PHASE

The optimization of the subproblem can be in one of the following phases:.

Parameters:

	Done	The optimization is done.
	Cutting	The iterative solution of the LP-relaxation and the generation of cutting planes and/or variables is currently performed.
	Branching	We try to generate further subproblems as sons of this subproblem.
	Fathoming	The subproblem is currently being fathomed.

Enumerator:

Done
Cutting
Branching
Fathoming

Definition at line 111 of file sub.h.

ABA_SUB::ABA_SUB	(	ABA_MASTER *	master,
		double	conRes,
		double	varRes,
		double	nnzRes,
		bool	relativeRes = `true`,
		ABA_BUFFER< ABA_POOLSLOT< ABA_CONSTRAINT, ABA_VARIABLE > * > *	constraints = `0`,
		ABA_BUFFER< ABA_POOLSLOT< ABA_VARIABLE, ABA_CONSTRAINT > * > *	variables = `0`
	)

The constructor for the root node of the enumeration tree.

Parameters:

	master	A pointer to the corresponding master of the optimization.
	conRes	The additional memory allocated for constraints.
	varRes	The additional memory allocated for variables.
	nnzRes	The additional memory allocated for nonzero elements of the constraint matrix.
	relativeRes	If this argument is true, then reserve space for variables, constraints, and nonzeros given by the previous three arguments, is given in percent of the original numbers. Otherwise, the numbers are interpreted as absolute values (casted to integer). The default value is true.
	constraints	The pool slots of the initial constraints. If the value is 0, then the constraints of the default constraint pool are taken. The default value is 0.
	variables	The pool slots of the initial variables. If the value is 0, then the variables of the default variable pool are taken. The default value is 0.

ABA_SUB::ABA_SUB	(	ABA_MASTER *	master,
		ABA_SUB *	father,
		ABA_BRANCHRULE *	branchRule
	)

The constructor for non-root nodes of the enumeration tree.

Parameters:

	master	A pointer to the corresponding master of the optimization.
	father	A pointer to the father in the enumeration tree.
	branchRule	The rule defining the subspace of the solution space associated with this subproblem.

virtual ABA_SUB::~ABA_SUB ( ) [virtual]

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.

ABA_SUB::ABA_SUB ( const ABA_SUB & rhs ) [private]

bool ABA_SUB::forceExactSolver ( ) const [inline]

Returns:: Whether using the exact solver is forced.

Definition at line 2207 of file sub.h.

int ABA_SUB::level ( ) const [inline]

Returns:: The level of the subproblem in the \ tree.

Definition at line 2212 of file sub.h.

int ABA_SUB::id ( ) const [inline]

Returns:: The identity number of the subproblem.

Definition at line 2217 of file sub.h.

ABA_SUB::STATUS ABA_SUB::status ( ) const [inline]

Returns:: The status of the subproblem optimization.

Definition at line 2244 of file sub.h.

int ABA_SUB::nVar ( ) const [inline]

Returns:: The number of active variables.

Definition at line 2259 of file sub.h.

int ABA_SUB::maxVar ( ) const [inline]

Returns:: The maximum number of variables which can be handled without reallocation.

Definition at line 2269 of file sub.h.

int ABA_SUB::nCon ( ) const [inline]

Returns:: The number of active constraints.

Definition at line 2264 of file sub.h.

int ABA_SUB::maxCon ( ) const [inline]

Returns:: The maximum number of constraints which can be handled without reallocation.

Definition at line 2274 of file sub.h.

double ABA_SUB::lowerBound ( ) const

Returns:: A lower bound on the optimal solution of the subproblem.

double ABA_SUB::upperBound ( ) const

Returns:: An upper bound on the optimal solution of the subproblem.

double ABA_SUB::dualBound ( ) const [inline]

Returns:: 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.

void ABA_SUB::dualBound ( double x )

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.

Parameters:

x

The new value of the dual bound.

const ABA_SUB * ABA_SUB::father ( ) const [inline]

Returns:: A pointer to the father of the subproblem in the \ tree.

Definition at line 2234 of file sub.h.

ABA_LPSUB * ABA_SUB::lp ( ) const [inline]

Returns:: A pointer to the linear program of the subproblem.

Definition at line 2239 of file sub.h.

void ABA_SUB::maxIterations ( int max )

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.

Parameters:

max

The maximal number of iterations.

ABA_ACTIVE< ABA_CONSTRAINT, ABA_VARIABLE > * ABA_SUB::actCon ( ) const [inline]

Returns:: A pointer to the currently active constraints.

Definition at line 2249 of file sub.h.

ABA_ACTIVE< ABA_VARIABLE, ABA_CONSTRAINT > * ABA_SUB::actVar ( ) const [inline]

Returns:: A pointer to the currently active variables.

Definition at line 2254 of file sub.h.

ABA_CONSTRAINT* ABA_SUB::constraint ( int i ) const

Returns:: A pointer to the i-th active constraint.

Parameters:

i

The constraint being accessed.

ABA_SLACKSTAT * ABA_SUB::slackStat ( int i ) const [inline]

Returns:: A pointer to the status of the slack variable i in the last solved linear program.

Parameters:

i

The number of the slack variable.

Definition at line 2202 of file sub.h.

ABA_VARIABLE* ABA_SUB::variable ( int i ) const

Returns:: A pointer to the i-th active variable.

Parameters:

i

The number of the variable being accessed.

double ABA_SUB::lBound ( int i ) const [inline]

Can be used to access the lower of an active variable of the subproblem.

Warning:: This is the lower bound of the variable within the current subproblem which can differ from its global lower bound.

Returns:: The lower bound of the i-th variable.

Parameters:

i

The number of the variable.

Definition at line 2168 of file sub.h.

void ABA_SUB::lBound	(	int	i,
		double	l
	)			`[inline]`

Sets the local lower bound of a variable.

It does not change the global lower bound of the variable. The bound of a fixed or set variable should not be changed.

Parameters:

	i	The number of the variable.
	x	The new value of the lower bound.

Definition at line 2173 of file sub.h.

double ABA_SUB::uBound ( int i ) const [inline]

Can be used to access the upper of an active variable of the subproblem.

Warning:: This is the upper bound of the variable within the current subproblem which can differ from its global upper bound.

Returns:: The upper bound of the i-th variable.

Parameters:

i

The number of the variable.

Definition at line 2180 of file sub.h.

void ABA_SUB::uBound	(	int	i,
		double	u
	)			`[inline]`

This version of the function uBound() sets thef local upper bound of a variable.

This does not change the global lower bound of the variable. The bound of a fixed or set variable should not be changed.

Parameters:

	i	The number of the variable.
	x	The new value of the upper bound.

Definition at line 2185 of file sub.h.

ABA_FSVARSTAT * ABA_SUB::fsVarStat ( int i ) const [inline]

In a \ algorithm we also would have to refer to the global variable status. While this subproblem is processed another subproblem could change the global status.

Returns:: A pointer to the status of fixing/setting of the i-th variable.

Note:: This is the local status of fixing/setting that might differ from the global status of fixing/setting of the variable (variable(i)->fsVarStat()).

Parameters:

i

The number of the variable.

Definition at line 2192 of file sub.h.

ABA_LPVARSTAT * ABA_SUB::lpVarStat ( int i ) const [inline]

Returns:: A pointer to the status of the variable i in the last solvedlinear program.

Parameters:

i

The number of the variable.

Definition at line 2197 of file sub.h.

double ABA_SUB::xVal ( int i ) const [inline]

Parameters:

i

The number of the variable under consideration.

Returns:: The value of the i-th variable in the last solved linear program.

Definition at line 2108 of file sub.h.

double ABA_SUB::yVal ( int i ) const [inline]

Parameters:

i

The number of the variable under consideration.

Returns:: The value of the i-th dual variable in the last solved linear program.

Definition at line 2113 of file sub.h.

bool ABA_SUB::ancestor ( const ABA_SUB * sub ) const

Returns:: true If this subproblem is an ancestor of the subproblem sub. We define that a subproblem is its own ancestor,
false otherwise.

Parameters:

sub

A pointer to a subproblem.

ABA_MASTER * ABA_SUB::master ( ) const [inline]

Definition at line 2118 of file sub.h.

void ABA_SUB::removeVars ( ABA_BUFFER< int > & remove )

With function removeVars() variables can be removed from the set of active variables.

The variables are not removed when this function is called, but are buffered and removed at the beginning of the next iteration.

Parameters:

remove

The variables which should be removed.

void ABA_SUB::removeVar ( int i ) [inline]

Can be used to remove a single variable from the set of active variables.

Like in the function removeVars() the variable is buffered and removed at the beginning of the next iteration.

Parameters:

i

The variable which should be removed.

Definition at line 2123 of file sub.h.

double ABA_SUB::nnzReserve ( ) const [inline]

Returns:: The additional space for nonzero elements of the constraint matrix when it is passed to the LP-solver.

Definition at line 2128 of file sub.h.

bool ABA_SUB::relativeReserve ( ) const [inline]

Returns:: true If the reserve space for variables, constraints, and nonzeros is given in percent of the original space, and false if its given as absolute value,
false otherwise.

Definition at line 2133 of file sub.h.

ABA_BRANCHRULE * ABA_SUB::branchRule ( ) const [inline]

Returns:: A pointer to the branching rule of the subproblem.

Definition at line 2138 of file sub.h.

bool ABA_SUB::objAllInteger ( )

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.

Note:: The result of this function can only be used to set the global parameter if actVar contains all variables of the problem formulation.

Returns:: true If this condition is satisfied by the currently active variable set,
false otherwise.

virtual void ABA_SUB::removeCons ( ABA_BUFFER< int > & remove ) [virtual]

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.

Parameters:

remove

The constraints which should be removed.

virtual void ABA_SUB::removeCon ( int i ) [virtual]

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.

Parameters:

i

The number of the constraint being removed.

int ABA_SUB::addConBufferSpace ( ) const [inline]

Can be used to determine the maximal number of the constraints which still can be added to the constraint buffer.

A separation algorithm should stop as soon as the number of generated constraints reaches this number because further work is useless.

Returns:: The number of constraints which still can be inserted into the constraint buffer.

Definition at line 2148 of file sub.h.

int ABA_SUB::addVarBufferSpace ( ) const [inline]

Can be used to determine the maximal number of the variables which still can be added to the variable buffer.

A pricing algorithm should stop as soon as the number of generated variables reaches this number because further work is useless.

Returns:: The number of variables which still can be inserted into the variable buffer.

Definition at line 2153 of file sub.h.

int ABA_SUB::nDormantRounds ( ) const [inline]

Returns:: The number of subproblem optimization the subproblem is already dormant.

Definition at line 2158 of file sub.h.

void ABA_SUB::ignoreInTailingOff ( )

Can be used to control better the tailing-off effect.

If this function is called, the next LP-solution is ignored in the tailing-off control. Calling ignoreInTailingOff() can e.g. be considered in the following situation: If only constraints that are required for the integer programming formulation of the optimization problem are added then the next LP-value could be ignored in the tailing-off control. Only ``real'' cutting planes should be considered in the tailing-off control (this is only an example strategy that might not be practical in many situations, but sometimes turned out to be efficient).

int ABA_SUB::addBranchingConstraint ( ABA_POOLSLOT< ABA_CONSTRAINT, ABA_VARIABLE > * slot ) [inline, virtual]

Adds a branching constraint to the constraint buffer such that it is automatically added at the beginning of the cutting plane algorithm.

It should be used in definitions of the pure virtual function BRANCHRULE::extract().

Returns:: 0 If the constraint could be added,
1 otherwise.

Parameters:

slot

A pointer to the pools slot containing the branching constraint.

Definition at line 2143 of file sub.h.

virtual int ABA_SUB::addCons	(	ABA_BUFFER< ABA_CONSTRAINT * > &	constraints,
		ABA_POOL< ABA_CONSTRAINT, ABA_VARIABLE > *	pool = `0`,
		ABA_BUFFER< bool > *	keepInPool = `0`,
		ABA_BUFFER< double > *	rank = `0`
	)			`[protected, virtual]`

Tries to add new constraints to the constraint buffer and a pool.

The memory management of added constraints is passed to \ by calling this function.

Returns:: The number of added constraints.

Parameters:

	constraints	The new constraints.
	pool	The pool in which the new constraints are inserted. If the value of this argument is 0, then the cut pool of the master is selected. Its default value is 0.
	keepInPool	If (keepInPool)[i] is true*, then the constraint stays in the pool even if it is not activated. The default value is a 0-pointer.
	rank	If this pointer to a buffer is nonzero, this buffer should store a rank for each constraint. The greater the rank, the better the variable. The default value of rank is 0.

virtual int ABA_SUB::addCons ( ABA_BUFFER< ABA_POOLSLOT< ABA_CONSTRAINT, ABA_VARIABLE > * > & newCons ) [protected, virtual]

Adds constraints to the active constraints and the linear program.

Returns:: The number of added constraints.

Parameters:

newCons

A buffer storing the pool slots of the new constraints.

virtual int ABA_SUB::addVars	(	ABA_BUFFER< ABA_VARIABLE * > &	variables,
		ABA_POOL< ABA_VARIABLE, ABA_CONSTRAINT > *	pool = `0`,
		ABA_BUFFER< bool > *	keepInPool = `0`,
		ABA_BUFFER< double > *	rank = `0`
	)			`[protected, virtual]`

Tries to add new variables to the variable buffer and a pool.

The memory management of added variables is passed to \ by calling this function.

Returns:: The number of added variables.

Parameters:

	variable	The new variables.
	pool	The pool in which the new variables are inserted. If the value of this argument is 0, then the default variable pool is taken. The default value is 0.
	keepInPool	If (keepInPool)[i] is true*, then the variable stays in the pool even if it is not activated. The default value is a 0-pointer.
	rank	If this pointer to a buffer is nonzero, this buffer should store a rank for each variable. The greater the rank, the better the variable. The default value of rank is 0.

virtual int ABA_SUB::addVars ( ABA_BUFFER< ABA_POOLSLOT< ABA_VARIABLE, ABA_CONSTRAINT > * > & newVars ) [protected, virtual]

Adds both the variables in newVars to the set of active variables and to the linear program of the subproblem.

If the new number of variables exceeds the maximal number of variables an automatic reallocation is performed.

Returns:: The number of added variables. We require this feature in derived classes if variables of newVars can be discarded if they are already active.

Parameters:

newVars

A buffer storing the pool slots of the new variables.

virtual int ABA_SUB::variablePoolSeparation	(	int	ranking = `0`,
		ABA_POOL< ABA_VARIABLE, ABA_CONSTRAINT > *	pool = `0`,
		double	minViolation = `0.001`
	)			`[protected, virtual]`

Tries to generate inactive variables from a pool.

Returns:: The number of generated variables.

Parameters:

	ranking	This parameter indicates how the ranks of geneated variables should be computed (0: no ranking; 1: violation is rank, 2: absolute value of violation is rank 3: rank determined by ABA_CONVAR::rank()). The default value is 0. }
	pool	The pool the variables are generated from. If pool is 0, then the default variable pool is used. The default value of pool is 0.
	minAbsViolation	A violated constraint/variable is only added if the absolute value of its violation is at least minAbsViolation. The default value is 0.001.

virtual int ABA_SUB::constraintPoolSeparation	(	int	ranking = `0`,
		ABA_POOL< ABA_CONSTRAINT, ABA_VARIABLE > *	pool = `0`,
		double	minViolation = `0.001`
	)			`[protected, virtual]`

Tries to generate inactive constraints from a pool.

Returns:: The number of generated constraints.

Parameters:

	ranking	This parameter indicates how the ranks of violated constraints should be computed (0: no ranking; 1: violation is rank, 2: absolute value of violation is rank, 3: rank determined by ABA_CONVAR::rank()). The default value is 0. }
	pool	The pool the constraints are generated from. If pool is 0, then the default constraint pool is used. The default value of pool is 0.
	minAbsViolation	A violated constraint/variable is only added if the absolute value of its violation is at least minAbsViolation. The default value is 0.001.

virtual void ABA_SUB::activate ( ) [protected, virtual]

Does nothing but can be used as an entrance point for problem specific activations by a reimplementation in derived classes.

virtual void ABA_SUB::deactivate ( ) [protected, virtual]

Can be used as entrance point for problem specific deactivations after the subproblem optimization.

The default version of this function does nothing. This function is only called if the function activate() for the subproblem has been executed. This function is called from _deactivate().

virtual int ABA_SUB::generateBranchRules ( ABA_BUFFER< ABA_BRANCHRULE * > & rules ) [protected, virtual]

Tries to find rules for splitting the current subproblem in further subproblems.

Per default we generate rules for branching on variables (branchingOnVariable()). But by redefining this function in a derived class any other branching strategy can be implemented.

Returns:: 0 If branching rules could be found,
1 otherwise.

Parameters:

rules

If branching rules are found, then they are stored in this buffer.

virtual int ABA_SUB::branchingOnVariable ( ABA_BUFFER< ABA_BRANCHRULE * > & rules ) [protected, virtual]

Generates branching rules for two new subproblems by selecting a branching variable with the function selectBranchingVariable().

If a new branching variable selection strategy should be used the function selectBranchingVariable() should be redefined.

Returns:: 0 If branching rules could be found,
1 otherwise}

Parameters:

rules

If branching rules are found, then they are stored in this buffer. The length of this buffer is the number of active variables of the subproblem. If more branching rules are generated a reallocation has to be performed.

virtual int ABA_SUB::selectBranchingVariable ( int & variable ) [protected, virtual]

Chooses a branching variable.

The function selectBranchingVariableCandidates() is asked to generate depending in the parameter { NBranchingVariableCandidates} of the file { .abacus} candidates for branching variables. If only one candidate is generate, this one becomes the branching variable. Otherwise, the pairs of branching rules are generated for all candidates and the ``best'' branching variables is determined with the function selectBestBranchingSample().

Returns:: 0 If a branching variable is found,
1 otherwise.

Parameters:

variable

Holds the branching variable if one is found.

virtual int ABA_SUB::selectBranchingVariableCandidates ( ABA_BUFFER< int > & candidates ) [protected, virtual]

Selects depending on the branching variable strategy given by the parameter { BranchingStrategy} in the file { .abacus} candidates that for branching variables.

Currently two branching variable selection strategies are implemented. The first one (CloseHalf) first searches the binary variables with fractional part closest to $0.5$ . If there is no fractional binary variable it repeats this process with the integer variables.

: The second strategy (CloseHalfExpensive) first tries to find binary variables with fraction close to and high absolute objective function coefficient. If this fails, it tries to find an integer variable with fractional part close to and high absolute objective function coefficient.

: If neither a binary nor an integer variable with fractional value is found then for both strategies we try to find non-fixed and non-set binary variables. If this fails we repeat this process with the integer variables.

: Other branching variable selection strategies can be implemented by redefining this virtual function in a derived class.

Returns:: 0 If a candidate is found,
1 otherwise.

Parameters:

candidates

The candidates for branching variables are stored in this buffer. We try to find as many variables as fit into the buffer.

virtual int ABA_SUB::selectBestBranchingSample	(	int	nSamples,
		ABA_BUFFER< ABA_BRANCHRULE * > **	samples
	)			`[protected, virtual]`

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().

Returns:: The number of the best branching sample, or -1 in case of an internal error.

Parameters:

	nSamples	The number of branching samples.
	samples	An array of pointer to buffers storing the branching rules of each sample.

virtual void ABA_SUB::rankBranchingSample	(	ABA_BUFFER< ABA_BRANCHRULE * > &	sample,
		ABA_ARRAY< double > &	rank
	)			`[protected, virtual]`

Computes for each branching rule of a branching sample a rank with the function rankBranchingRule().

Parameters:

	sample	A branching sample.
	rank	An array storing the rank for each branching rule in the sample after the function call.

virtual double ABA_SUB::rankBranchingRule ( ABA_BRANCHRULE * branchRule ) [protected, virtual]

Computes the rank of a branching rule.

This default implementation computes the rank with the function lpRankBranchingRule(). By redefining this virtual function the rank for a branching rule can be computed differently.

Returns:: The rank of the branching rule.

Parameters:

branchRule

A pointer to a branching rule.

double ABA_SUB::lpRankBranchingRule	(	ABA_BRANCHRULE *	branchRule,
		int	iterLimit = `-1`
	)			`[protected]`

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.

It is useless, but no error, to call this function for branching rules for which the virtual dummy functions extract(ABA_LPSUB*) and unExtract(ABA_LPSUB*) of the base class ABA_BRANCHRULE are not redefined.

Returns:: The value of he linear programming relaxation of the subproblem modified by the branching rule.

Parameters:

	branchRule	A pointer to a branching rule.
	iterLimit	The maximal number of iterations that should be performed by the simplex method. If this number is negative there is no iteration limit (besides internal limits of the LP-solver). The default value is -1.

virtual int ABA_SUB::compareBranchingSampleRanks	(	ABA_ARRAY< double > &	rank1,
		ABA_ARRAY< double > &	rank2
	)			`[protected, virtual]`

Compares the ranks of two branching samples.

For maximimization problem that rank is better for which the maximal rank of a rule is minimal, while for minimization problem the rank is better for which the minimal rank of a rule is maximal. If this value equals for both ranks we continue with the secand greatest value, etc.

Returns:

1 If rank1 is better.

0 If both ranks are equal.

-1 If rank2 is better.

int ABA_SUB::closeHalfExpensive	(	int &	branchVar,
		ABA_VARTYPE::TYPE	branchVarType
	)			`[protected]`

Selects a single branching variable of type branchVarType, with fractional part close to $0.5$ and high absolute objective function coefficient.

This is the default strategy from the TSP project JRT94}.

Returns:: 0 If a branching variable is found,
1 otherwise.

Parameters:

	branchVar	Holds the number of the branching variable if one is found.
	branchVartype	The type of the branching variable can be restricted either to ABA_VARTYPE::Binary or ABA_VARTYPE::Integer.

int ABA_SUB::closeHalfExpensive	(	ABA_BUFFER< int > &	variables,
		ABA_VARTYPE::TYPE	branchVarType
	)			`[protected]`

This version of the function closeHalfExpensive() selects several candidates for branching variables of type branchVarType.

Thos variables with fractional part close to $0.5$ and high absolute objective function coefficient are selected..

Returns:: 0 If at least one branching variable is found,
1 otherwise.

Parameters:

	branchVar	Holds the numbers of possible branching variables if at least one is found. We try to find as many candidates as fit into this buffer. We abort the function with a fatal error if the size of the buffer is 0.
	branchVartype	The type of the branching variable can be restricted either to ABA_VARTYPE::Binary or ABA_VARTYPE::Integer.

int ABA_SUB::closeHalf	(	int &	branchVar,
		ABA_VARTYPE::TYPE	branchVarType
	)			`[protected]`

Searches a branching variable of type branchVarType, with fraction as close to $0.5$ as possible.

Returns:: 0 If a branching variable is found,
1 otherwise.

Parameters:

	branchVar	Holds the branching variable if one is found.
	branchVartype	The type of the branching variable can be restricted either to ABA_VARTYPE::Binary or ABA_VARTYPE::Integer.

int ABA_SUB::closeHalf	(	ABA_BUFFER< int > &	branchVar,
		ABA_VARTYPE::TYPE	branchVarType
	)			`[protected]`

Searches searches several possible branching variable of type branchVarType, with fraction as close to $0.5$ as possible.

Returns:: 0 If at least one branching variable is found,
1 otherwise.

Parameters:

	variables	Stores the possible branching variables.
	branchVartype	The type of the branching variable can be restricted either to ABA_VARTYPE::Binary or ABA_VARTYPE::Integer.

int ABA_SUB::findNonFixedSet	(	ABA_BUFFER< int > &	branchVar,
		ABA_VARTYPE::TYPE	branchVarType
	)			`[protected]`

Selects the first variables that are neither fixed nor set.

Returns:: 0 If at least one variable neither fixed nor set is found,
1 otherwise.

Parameters:

	branchVar	Holds the number of the possible branching variables if one is found.
	branchVartype	The type of the branching variable can be restricted either to ABA_VARTYPE::Binary or ABA_VARTYPE::Integer.

int ABA_SUB::findNonFixedSet	(	int &	branchVar,
		ABA_VARTYPE::TYPE	branchVarType
	)			`[protected]`

Selects the first variable that is neither fixed nor set.

Returns:: 0 If a variable neither fixed nor set is found,
1 otherwise.

Parameters:

	branchVar	Holds the number of the branching variable if one is found.
	branchVarType	The type of the branching have (ABA_VARTYPE::Binary or ABA_VARTYPE::Integer).

virtual int ABA_SUB::initMakeFeas	(	ABA_BUFFER< ABA_INFEASCON * > &	infeasCon,
		ABA_BUFFER< ABA_VARIABLE * > &	newVars,
		ABA_POOL< ABA_VARIABLE, ABA_CONSTRAINT > **	pool
	)			`[protected, virtual]`

The default implementation of the virtual initMakeFeas() does nothing.

A reimplementation of this function should generate inactive variables until at least one variable v which satisfies the function ABA_INFEASCON::goodVar(v) for each infeasible constraint is found.

Returns:: 0 If the feasibility might have been restored,
1 otherwise.

Parameters:

	infeasCons	The infeasible constraints.
	newVars	The variables that might restore feasibility should be added here.
	pool	A pointer to the pool to which the new variables should be added. If this is a 0-pointer the variables are added to the default variable pool. The default value is 0.

virtual int ABA_SUB::makeFeasible ( ) [protected, virtual]

The default implementation of makeFeasible() does nothing.

If there is an infeasible structural variable then it is stored in infeasVar_, otherwise infeasVar_ is -1. If there is an infeasible slack variable, it is stored in infeasCon_, otherwise it is -1. At most one of the two members infeasVar_ and infeasCon_ can be nonnegative. A reimplementation in a derived class should generate variables to restore feasibility or confirm that the subproblem is infeasible.

: The strategy for the generation of inactive variables is completely problem and user specific. For testing if a variable might restore again the feasibility the functions ABA_VARIABLE::useful() and ABA_SUB::goodCol() might be helpful.

Returns:: 0 If feasibility can be restored,
1 otherwise.

virtual bool ABA_SUB::goodCol	(	ABA_COLUMN &	col,
		ABA_ARRAY< double > &	row,
		double	x,
		double	lb,
		double	ub
	)			`[protected, virtual]`

Returns:: true If the column col might restore feasibiblity if the variable with value x turns out to be infeasible,
false otherwise.

Parameters:

	col	The column of the variable.
	row	The row of the basis inverse associated with the infeasible variable.
	x	The LP-value of the infeasible variable.
	lb	The lower bound of the infeasible variable.
	ub	The upper bound of the infeasible variable.

virtual void ABA_SUB::setByLogImp	(	ABA_BUFFER< int > &	variable,
		ABA_BUFFER< ABA_FSVARSTAT * > &	status
	)			`[protected, virtual]`

The default implementation of setByLogImp() does nothing.

In derived classes this function can be reimplemented.

Parameters:

	variable	The variables which should be set have to be inserted in this buffer.
	status	The status of the set variables.

virtual bool ABA_SUB::feasible ( ) [protected, pure virtual]

The pure virtual function feasible() checks for the feasibility of a solution of the LP-relaxation.

If the function returns true and the value of the primal bound is worse than the value of this feasible solution, the value of the primal bound is updated automatically.

Returns:: true If the LP-solution is feasible,
false otherwise.

bool ABA_SUB::integerFeasible ( ) [protected]

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.

This function can be called from the function feasible() in derived classes.

Returns:: true If the LP-value of all binary and integer variables is integral,
false otherwise.

virtual bool ABA_SUB::primalSeparation ( ) [protected, virtual]

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.

Per default a pure cutting plane algorithm performs always a primal separation step, a pure column generation algorithm never performs a primal separation, and a hybrid algorithm generates usually cutting planes but from time to time also inactive variables are priced out depending on the pricingFrequency().

Returns:: true Then cutting planes are generated in this iteration.
false Then columns are generated in this iteration.

virtual int ABA_SUB::separate ( ) [protected, virtual]

Must be redefined in derived classes for the generation of cutting planes.

The default implementation does nothing.

Returns:: The number of generated cutting planes.

virtual void ABA_SUB::conEliminate ( ABA_BUFFER< int > & remove ) [protected, virtual]

Can be used as an entry point for application specific elimination of constraints by redefinig it in derived classes.

The default implementation of this function calls either the function nonBindingConEliminate() or the function basicConEliminate() depending on the constraint elimination mode of the master that is initialized via the parameter file.

Parameters:

remove

The constraints that should be eliminated must be inserted in this buffer.

virtual void ABA_SUB::nonBindingConEliminate ( ABA_BUFFER< int > & remove ) [protected, virtual]

Retrieves the dynamic constraints with slack exceeding the value given by the parameter { ConElimEps}.

Parameters:

remove

Stores the nonbinding constraints.

virtual void ABA_SUB::basicConEliminate ( ABA_BUFFER< int > & remove ) [protected, virtual]

Retrieves all dynamic constraints having basic slack variable.

Parameters:

remove

Stores the nonbinding constraints.

virtual void ABA_SUB::varEliminate ( ABA_BUFFER< int > & remove ) [protected, virtual]

Provides an entry point for application specific variable elimination that can be implemented by redefining this function in a derived class.

The default implementation selects the variables with the function redCostVarEliminate().

Parameters:

remove

The variables that should be removed have to be stored in this buffer.

void ABA_SUB::redCostVarEliminate ( ABA_BUFFER< int > & remove ) [protected]

Retrieves all variables with ``wrong'' reduced costs.

Parameters:

remove

The variables with ``wrong'' reduced cost are stored in this buffer.

virtual int ABA_SUB::pricing ( ) [protected, virtual]

Should generate inactive variables which do not price out correctly.

The default implementation does nothing and returns 0.

Returns:: The number of new variables.

virtual int ABA_SUB::improve ( double & primalValue ) [protected, virtual]

Can be redefined in derived classes in order to implement primal heuristics for finding feasible solutions.

The default implementation does nothing.

Returns:: 0 If no better solution could be found,
1 otherwise.

Parameters:

primalValue

Should hold the value of the feasible solution, if a better one is found.

virtual ABA_SUB* ABA_SUB::generateSon ( ABA_BRANCHRULE * rule ) [protected, pure virtual]

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.

Parameters:

rule

The branching rule with which the subproblem is generated.

bool ABA_SUB::boundCrash ( ) const [protected]

Returns:: true If the dual bound is worse than the best known primal bound,
false otherwise.

virtual bool ABA_SUB::pausing ( ) [protected, virtual]

Sometimes it is appropriate to put a subproblem back into the list of open subproblems. This is called pausing. In the default implementation the virtual function pausing() always returns false.

It could be useful to enforce pausing a node if a tailing off effect is observed during its first optimization.

Returns:: true The function pausing() should return true if this condition is satisfied,
false otherwise.

bool ABA_SUB::infeasible ( ) [protected]

Returns:: true If the subproblem does not contain a feasible solution,
false otherwise.

virtual void ABA_SUB::varRealloc ( int newSize ) [protected, virtual]

Reallocates memory that at most newSize variables can be handled in the subproblem.

Parameters:

newSize

The new maximal number of variables in the subproblem.

virtual void ABA_SUB::conRealloc ( int newSize ) [protected, virtual]

Reallocates memory that at most newSize constraints can be handled in the subproblem.

Parameters:

newSize

The new maximal number of constraints of the subproblem.

virtual ABA_LP::METHOD ABA_SUB::chooseLpMethod	(	int	nVarRemoved,
		int	nConRemoved,
		int	nVarAdded,
		int	nConAdded
	)			`[protected, virtual]`

Controls the method used to solve a linear programming relaxation.

The default implementation chooses the barrier method for the first linear program of the root node and for all other linear programs it tries to choose a method such that phase 1 of the simplex method is not required.

Returns:: The method the next linear programming relaxation is solved with.

Parameters:

	nVarRemoved	The number of removed variables.
	nConRemoved	The number of removed constraints.
	nVarAdded	The number of added variables.
	nConAdded	The number of added constraint.

virtual bool ABA_SUB::tailingOff ( ) [protected, virtual]

Is called when a tailing off effect according to the parameters { TailOffPercent} and { TailOffNLps} of the parameter file is observed.

This function can be redefined in derived classes in order to perform actions to resolve the tailing off (e.g., switching on an enhanced separation strategy).

Returns:: true If a branching step should be enforced. But before branching a pricing operation is perfored. The branching step is only performed if no variables are added. Otherwise, the cutting plane algorithm is continued.
false If the cutting plane algorithm should be continued.

bool ABA_SUB::betterDual ( double x ) const [protected]

Returns:: true If x is better than the best known dual bound of the subproblem,
false otherwise.

virtual void ABA_SUB::selectVars ( ) [protected, virtual]

Is called before variables are selected from the variable buffer.

It can be redefined in a derived class e.g., to remove multiply inserted variables from the buffer.

virtual void ABA_SUB::selectCons ( ) [protected, virtual]

Is called before constraint are selected from the constraint buffer.

It can be redefined in a derived class e.g., to remove multiply inserted constraints from the buffer.

virtual int ABA_SUB::fixByRedCost	(	bool &	newValues,
		bool	saveCand
	)			`[protected, virtual]`

Tries to fix variables according to the reduced cost criterion.

Returns:: 1 If a contradiction is found,
0 otherwise.

Parameters:

	newVales	If variables are fixed to different values as in the last solved linear program, then newValues becomes true.
	saveCand	If saveCand is true, then a new list of candidates for later calls is compiled. This is only possible when the root of the remaining \ is processed.

virtual void ABA_SUB::fixByLogImp	(	ABA_BUFFER< int > &	variable,
		ABA_BUFFER< ABA_FSVARSTAT * > &	status
	)			`[protected, virtual]`

Should collect the numbers of the variables to be fixed in variable and the respective statuses in status.

The default implementation of fixByLogImp() does nothing. This function has to be redefined if variables should be fixed by logical implications in derived classes.

Parameters:

	variables	The variables which should be fixed.
	status	The statuses these variables should be fixed to.

virtual int ABA_SUB::fixAndSet ( bool & newValues ) [protected, virtual]

Tries to fix and set variables both by logical implications and reduced cost criteria.

Actually, variables fixed or set to 0 could be eliminated. However, this could lead to a loss of important structural information for fixing and setting further variables later, for the computation of feasible solutions, for the separation and for detecting contradictions. Therefore, we do not eliminate these variables per default.

Returns:: 1 If a contradiction is found,
0 otherwise.

Parameters:

newValues

If a variables is set or fixed to a value different from the last LP-solution, newValues is set to true, otherwise it is set to false.

virtual int ABA_SUB::fixing	(	bool &	newValues,
		bool	saveCand = `false`
	)			`[protected, virtual]`

Tries to fix variables by reduced cost criteria and logical implications.

Returns:: 1 If a contradiction is found,
0 otherwise.

Parameters:

	newValues	The parameter newValues becomes true if variables are fixed to other values as in the current LP-solution.
	saveCand	If the parameter saveCand is true a new candidate list of variables for fixing is generated. The default value of saveCand is false. Candidates should not be saved if fixing is performed after the addition of variables.

virtual int ABA_SUB::setting ( bool & newValues ) [protected, virtual]

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.

Returns:: 1 If a contradiction has been found,
0 otherwise.

Parameters:

newValues

The parameter newValues becomes true if variables are fixed to other values as in the current LP-solution (setByRedCost() cannot set variables to new values).

virtual int ABA_SUB::setByRedCost ( ) [protected, virtual]

Tries to set variables according to the reduced cost criterion.

Returns:: 1 If a contradiction is found,
0 otherwise.

virtual void ABA_SUB::fathom ( bool reoptimize ) [protected, virtual]

Fathoms a node and recursively tries to fathom its father.

If the root of the remaining \ tree is fathomed we are done since the optimization problem has been solved.

: Otherwise, we count the number of unfathomed sons of the father of the subproblem being fathomed. If all sons of the father are fathomed it is recursively fathomed, too. If the father is the root of the remaining \ tree and only one of its sons is unfathomed, then this unfathomed son becomes the new root of the remaining \ tree.

: We could stop the recursive fathoming already at the root of the remaining \ tree. But, we proceed until the root of the complete tree was visited to be really correct.

Note:: Use the function ExceptionFathom() for specifying problem specific fathoming criteria.

Parameters:

reoptimize

If reoptimize is true, then we perform a reoptimization in the new root. This is controlled via a parameter since it might not be desirable when we find a new root during the fathoming of a complete subtree with the function fathomTheSubTree().

virtual bool ABA_SUB::fixAndSetTime ( ) [protected, virtual]

Controls if variables should be fixed or set when all variables price out corretly.

The default implementation always returns true.

Returns:: true If variables should be fixed and set,
false otherwise.

virtual int ABA_SUB::fix	(	int	i,
		ABA_FSVARSTAT *	newStat,
		bool &	newValue
	)			`[protected, virtual]`

Fixes a variable.

If the variable which is currently fixed is already set then we must not change its bounds in the LP since it might be eliminated.

Returns:: 1 If a contradiction is found,
0 otherwise.

Parameters:

	i	The number of the variable being fixed.
	newStat	A pointer to an object storing the new status of the variable.
	newValue	If the variable is fixed to a value different from the one of the last LP-solution, the argument newValue is set to true. Otherwise, it is set to false.

virtual int ABA_SUB::set	(	int	i,
		ABA_FSVARSTAT *	newStat,
		bool &	newValue
	)			`[protected, virtual]`

Sets a variable.

Returns:: 1 If a contradiction is found,
0 otherwise.

Parameters:

	i	The number of the variable being set.
	newStat	A pointer to the object storing the new status of the the variable.
	newValue	If the variable is set to a value different from the one of the last LP-solution, newValue is set to true. Otherwise, it is set to false.

virtual int ABA_SUB::set	(	int	i,
		ABA_FSVARSTAT::STATUS	newStat,
		bool &	newValue
	)			`[protected, virtual]`

Sets a variable.

Returns:: 1 If a contradiction is found,
0 otherwise.

Parameters:

	i	The number of the variable being set.
	newStat	The new status of the variable.
	newValue	If the variable is set to a value different from the one of the last LP-solution, newValue is set to true. Otherwise, it is set to false.

virtual int ABA_SUB::set	(	int	i,
		ABA_FSVARSTAT::STATUS	newStat,
		double	value,
		bool &	newValue
	)			`[protected, virtual]`

Sets a variable.

Returns:: 1 If a contradiction is found,
0 otherwise.

Parameters:

	i	The number of the variable being set.
	newStat	The new status of the variable.
	value	The value the variable is set to.
	newValue	If the variable is set to a value different from the one of the last LP-solution, newValue is set to true. Otherwise, it is set to false.

virtual double ABA_SUB::dualRound ( double x ) [protected, virtual]

Returns:: If all objective function values of feasible solutions are integer the function dualRound() returns x rounded up to the next integer if this is a minimization problem, or x rounded down to the next integer if this is a maximization problem, respectively. Otherwise, the return value is x.

Parameters:

x

The value that should be rounded if possible.

virtual double ABA_SUB::guarantee ( ) [protected, virtual]

May not be called if the lower bound is 0 and upper bound not equal to 0.

The guarantee that can be given for the subproblem.

virtual bool ABA_SUB::guaranteed ( ) [protected, virtual]

Returns:: true If the lower and the upper bound of the subproblem satisfies the guarantee requirements,
false otherwise.

virtual bool ABA_SUB::removeNonLiftableCons ( ) [protected, virtual]

Returns:: true If all active constraints can be lifted.
false otherwise. In this case the non-liftable constraints are removed and genNonLiftCons_ is set to false to avoid the generation of non-liftable constraints in the next cutting plane iterations.

virtual int ABA_SUB::prepareBranching ( bool & lastIteration ) [protected, virtual]

Is called before a branching step to remove constraints.

Returns:: 1 If constraints have been removed,
0 otherwise.

Parameters:

lastIteration

This argument is always set to true in the function call.

virtual void ABA_SUB::fathomTheSubTree ( ) [protected, virtual]

Fathoms all nodes in the subtree rooted at this subproblem.

Dormant and Unprocessed nodes are also removed from the set of open subproblems.

If the subproblem is already Fathomed we do not have to proceed in this branch. Otherwise, we fathom the node and continue with all its sons. The actual fathoming starts at the unfathomed leaves of the subtree and recursively goes up through the tree.

virtual int ABA_SUB::optimize ( ) [protected, virtual]

Performs the optimization of the subproblem.

After activating the subproblem, i.e., allocating and initializing memory, and initializing the LP, the optimization process constitutes of the three phases Cutting, Branching, and Fathoming, which are alternately processed. The function fathoming() always returns Done. However, we think that the code is better readable instead of taking it out of the while loop. The optimization stops if the PHASE Done is reached. Note, Done does not necessarily mean that the subproblem is solved to optimality!

: After the node is processed we deallocate memory, which is not required for further computations or of which the corresponding data can be easily reconstructed. This is performed in _deactivate().

Returns:: 0 If the optimization has been performed without error,
1 otherwise.

virtual void ABA_SUB::reoptimize ( ) [protected, virtual]

Repeats the optimization of an already optimized subproblem.

This function is used to determine the reduced costs for fixing variables of a new root of the remaining \ tree.

As the subproblem has been processed already earlier it is sufficient to perform the cutting plane algorithm. If the subproblem is fathomed the complete subtree rooted at this subproblem can be fathomed, too. Since this function is usually only called for the root of the remaining \ tree, we are done in this case.

It is not guaranteed that all constraints and variables of this subproblem can be regenerated in _activate(). Therefore, the result of a call to reoptimize() can differ from the result obtained by the cutting plane algorithm in optimize().

virtual void ABA_SUB::initializeVars ( int maxVar ) [protected, virtual]

Initializes the active variable set.

Parameters:

maxVar

The maximal number of variables of the subproblem.

virtual void ABA_SUB::initializeCons ( int maxCon ) [protected, virtual]

Initializes the active constraint set.

Parameters:

maxCon

The maximal number of constraints of the subproblem.

virtual PHASE ABA_SUB::branching ( ) [protected, virtual]

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).

Usually, two new subproblems are generated. However, our implementation of branching() is more sophisticated that allows different branching. Moreover, we also check if this node is only paused. If this is the case the node is put back into the list of open \ nodes without generating sons of this node.

Finally if none of the previous conditions is satisfied we generate new subproblems.

Returns:: Done If sons of the subproblem could be generated,
Fathoming otherwise.

virtual PHASE ABA_SUB::fathoming ( ) [protected, virtual]

Fathoms the node, and if certain conditions are satisfied, also its ancestor.

The third central phase of the optimization of a subproblem is the Fathoming of a subproblem. A subproblem is fathomed if it can be guaranteed that this subproblem cannot contain a better solution than the best known one. This is the case if the global upper bound does not exceed the local lower bound (maximization problem assumed) or the subproblem cannot contain a feasible solution either if there is a fixing/setting contradiction or the LP-relaxation turns out to be infeasible.

Note:: Use the function ExceptionFathom() for specifying problem specific fathoming criteria.

: The called function fathom() fathoms the subproblem itself and recursively also tries to fathom its father in the enumeration tree. The argument of fathom() is true as a possibly detected new root should be reoptimized in order to receive better criteria for fixing variables by reduced costs.

: In the parallel version, only the subproblem itself is fathomed. No processed unfathomed nodes are kept in memory (father_=0).

Returns:: The function always returns Done.

virtual PHASE ABA_SUB::cutting ( ) [protected, virtual]

Iteratively solves the LP-relaxation, generates constraints and/or variables.

Also generating variables can be regarded as ``cutting'', namely as generating cuts for the dual problem. A reader even studying these lines has been very brave! Therefore, the first reader of these lines is invited to a beer from the author.

Returns:: Fathoming If one of the conditions for fathoming the subproblem is satisfied.
Branching If the subproblem should be splitted in further subproblems.

virtual ABA_LPSUB* ABA_SUB::generateLp ( ) [protected, virtual]

Instantiates an LP for the solution of the LP-relaxation in this subproblem.

This function is redefined in a derived class for a specific LP-solver interface

This function is defined in the file lpif.cc.

Returns:: A pointer to an object of type ABA_LPSUB.

virtual int ABA_SUB::initializeLp ( ) [protected, virtual]

Initializes the linear program.

Since not all variables might be active we first have to try making the LP feasible again by the addition of variables. If this fails, i.e., _initMakeFeas() has a nonzero return value, we return 1 in order to indicate that the corresponding subproblem can be fathomed. Otherwise, we continue with the initialization of the LP.

Returns:: 0 If the linear program could be initialized successfully.
1 If the linear program turns out to be infeasible.

virtual int ABA_SUB::solveLp ( ) [protected, virtual]

Solves the LP-relaxation of the subproblem.

As soon as the LP-relaxation becomes infeasible in a static branch and cut algorithm the respective subproblem can be fathomed. Otherwise, we memorize the value of the LP-solution to control the tailing off effect.

: { We assume that the LP is never primal unbounded.

Returns:

0 The linear program has an optimimal solution.

1 If the linear program is infeasible.

2 If the linear program is infeasible for the current variable set, but non-liftable constraints have to be removed before a pricing step can be performed.

virtual bool ABA_SUB::exceptionFathom ( ) [protected, virtual]

Can be used to specify a problem specific fathoming criterium that is checked before the separation or pricing.

The default implementation always returns false.

Returns:: true If the subproblem should be fathomed,
false otherwise.

virtual bool ABA_SUB::exceptionBranch ( ) [protected, virtual]

Can be used to specify a problem specific criteria for enforcing a branching step.

This criterium is checked before the separation or pricing. The default implementation always returns false.

Returns:: true If the subproblem should be fathomed,
false otherwise.

virtual bool ABA_SUB::solveApproxNow ( ) [protected, virtual]

Returns:: True, if the approximative solver should be used to solve the next linear program, false otherwise.

The default implementation always returns false.

virtual int ABA_SUB::_separate ( ) [private, virtual]

Returns the number of generated cutting planes.

virtual int ABA_SUB::_conEliminate ( ) [private, virtual]

Returns the number of eliminated constraints.

Only dynamic constraints are eliminated from the LP.

It might be worth to implement problem specific versions of this function.

virtual int ABA_SUB::_varEliminate ( ) [private, virtual]

Returns the number of eliminated variables.

Only dynamic variables can be eliminated.

virtual int ABA_SUB::_pricing	(	bool &	newValues,
		bool	doFixSet = `true`
	)			`[private, virtual]`

If doFixSet is true, then we try to fix and set variables, if all inactive variables price out correctly. In this case newValues becomes true of a variable is set or fixed to a value different from its value in the last linear program.

: In a pricing step the reduced costs of inactive variables are computed and variables with positive (negative) reduced costs in a maximization (minimization) problem are activated.

: The function _pricing() returns the 1 if no global optimality can be guaranteed, since variables have negative reduced costs, it returns 2 if before a pricing step can be performed, non-liftable constraints have to be removed, and 0 if the LP-solution is global dual feasible.

: Also if there are no inactive variables, this function is called since it will also try to fix and set variables.

: true is the default value of doFixSet. No variables should be fixed or set if _pricing() is called from _makeFeasible().

virtual int ABA_SUB::_improve ( double & primalValue ) [private, virtual]

Tries to find a better feasible solution.

If a better solution is found its value is stored in primalValue and we return 1, otherwise we return 0.

: If the upper bound has been initialized with the optimum solution or with the optimum solution plus/minus one these primal heuristics are skipped.

: The primal bound, if improved, is either updated in the function cutting(), from which _improved() is called, are can be updated in the function improve() of an application in a derived class.

virtual int ABA_SUB::_fixByLogImp ( bool & newValues ) [private, virtual]

Returns 1, if a contradiction has been found, 0 otherwise.

The parameter newValues is set to true if a variable is fixed to value different from its value in the last solved linear program.

virtual void ABA_SUB::updateBoundInLp ( int i ) [private, virtual]

Adapts the bound of a fixed or set variable i also in the linear program.

This can be only done if a linear program is available and the variable is not eliminated.

virtual double ABA_SUB::fixSetNewBound ( int i ) [private, virtual]

Returns the value which the upper and lower bounds of a variable should take after it is fixed or set.

void ABA_SUB::newDormantRound ( ) [inline, private, virtual]

Increments the counter for the number of rounds the subproblem is dormant.

This function is called, when the set of open subproblems is scanned for the selection of the next subproblem.

Definition at line 2163 of file sub.h.

virtual PHASE ABA_SUB::_activate ( ) [private, virtual]

Allocates and initializes memory of the subproblem at the beginning of the optimization.

The function returns the next phase of the optimization. This is either Cutting or Fathoming if the subproblem immediately turns out to be infeasible.

: Since many objects of the class ABA_SUB can exist at the same time, yet in a sequential algorithm only one problem is active, a lot of memory can be saved if some memory is dynamically allocated when the subproblem becomes active and other information is stored in a compressed format for dormant problems.

: These allocations and decompressions are performed by the function _activate(), the respective deallocations and compression of data is executed by the function _deactivate().

: Currently for all subproblems which have not been processed already (except for the root) we initialize the active constraints and variables with the respective data from the father node adapted by the branching information since so we can make sure that all fixed and set variables are active. A more flexible strategy might be desirable but also dangerous.

: The virtual function activate() can perform problem specific activations. It is called before variables are fixed by logical implications, because, e.g., for problems on graphs, the graph associated with the subproblem might have to be activated.

: Moreover, the function _activate() is redundant in the sense that it is called only once and could be substituted by a function. However, having a future generalization to non \ in mind, we keep this function.

virtual void ABA_SUB::_deactivate ( ) [private, virtual]

Deallocates the memory which is not required after the optimization of the subproblem.

The virtual dummy function deactivate() can perform problem specific deactivations.

: As the function _activate(), the function _deactivate() is redundant in the sense that it is called only once and could be substituted by a function. However, having a future generalization to non \ in mind, we keep this function.

virtual int ABA_SUB::_initMakeFeas ( ) [private, virtual]

Tries to add variables to restore infeasibilities detected at initialization time.

It returns 0 if variables could be activated which might restore feasibility, otherwise it returns 1.

: The function should analyse the constraints stored in ABA_LPSUB::infeasCons_ and try to add inactive variables which could restore the infeasibility.

: The new variables are only added to the set of active variables but not to the linear program since no linear program exists when this function is called.

virtual int ABA_SUB::_makeFeasible ( ) [private, virtual]

Is called if the LP is infeasible and adds inactive variables, which can make the LP feasible again, to the set of active variables.

The function returns 0 if feasibility might have been restored and 1 if it is guaranteed that the linear program is infeasible on the complete variable set.

virtual int ABA_SUB::_setByLogImp ( bool & newValues ) [private, virtual]

Tries to set variables according to logical implications of already set and fixed variables.

Since logical implications are problem specific the virtual function setByLogImp() is called to find variables which can be set. If a variable is set to a new value, i.e., a value different from the one in the last solved LP, newValues is set to true. If such a setting implies a contradiction, _setByLogImp() returns 1, otherwise it returns 0.

virtual void ABA_SUB::infeasibleSub ( ) [private, virtual]

Should be called if a subproblem turns out to be infeasible.

It sets the dual bound of the subproblem correctly.

virtual void ABA_SUB::getBase ( ) [private, virtual]

Updates the status of the variables and the slack variables.

virtual void ABA_SUB::activateVars ( ABA_BUFFER< ABA_POOLSLOT< ABA_VARIABLE, ABA_CONSTRAINT > * > & newVars ) [private, virtual]

Adds the variables stored in the pool slots of newVars to the set of active variables, but not to the linear program.

If the new number of variables exceeds the maximal number of variables an automatic reallocation is performed.

virtual void ABA_SUB::addVarsToLp	(	ABA_BUFFER< ABA_POOLSLOT< ABA_VARIABLE, ABA_CONSTRAINT > * > &	newVars,
		ABA_BUFFER< ABA_FSVARSTAT * > *	localStatus = `0`
	)			`[private, virtual]`

Adds the variables stored in the pool slots of newVars to the linear program. localStatus can specify a local status of fixing and setting.

If the local ABA_FSVARSTAT of the added variables differs from their global status, then this local status can be stated in localStatus. Per default the value of localStatus is 0.

virtual void ABA_SUB::_selectVars ( ABA_BUFFER< ABA_POOLSLOT< ABA_VARIABLE, ABA_CONSTRAINT > * > & newVars ) [private, virtual]

Selects the master_->maxVarAdd() best variables from the buffered variables.

Parameters:

newVars

Holds the selected variables after the call.

virtual void ABA_SUB::_selectCons ( ABA_BUFFER< ABA_POOLSLOT< ABA_CONSTRAINT, ABA_VARIABLE > * > & newCons ) [private, virtual]

Selects the master_->maxConAdd() best constraints from the buffered constraints and stores them in newCons.

virtual int ABA_SUB::_removeVars ( ABA_BUFFER< int > & remove ) [private, virtual]

virtual int ABA_SUB::_removeCons ( ABA_BUFFER< int > & remove ) [private, virtual]

Removes the constraints with numbers remove from the set of active constraints.

const ABA_SUB& ABA_SUB::operator= ( const ABA_SUB & rhs ) [private]

friend class ABA_MASTER [friend]

Definition at line 76 of file sub.h.

friend class ABA_BOUNDBRANCHRULE [friend]

Definition at line 77 of file sub.h.

friend class ABA_OPENSUB [friend]

Definition at line 78 of file sub.h.

friend class ABA_LPSOLUTION< ABA_CONSTRAINT, ABA_VARIABLE > [friend]

Definition at line 79 of file sub.h.

friend class ABA_LPSOLUTION< ABA_VARIABLE, ABA_CONSTRAINT > [friend]

Definition at line 80 of file sub.h.

ABA_MASTER* ABA_SUB::master_ [protected]

A pointer to the corresponding master of the optimization.

Definition at line 1656 of file sub.h.

ABA_ACTIVE<ABA_CONSTRAINT, ABA_VARIABLE>* ABA_SUB::actCon_ [protected]

The active constraints of the subproblem.

Definition at line 1660 of file sub.h.

ABA_ACTIVE<ABA_VARIABLE, ABA_CONSTRAINT>* ABA_SUB::actVar_ [protected]

The active variables of the subproblem.

Definition at line 1664 of file sub.h.

ABA_SUB* ABA_SUB::father_ [protected]

A pointer to the father in the \ tree.

Definition at line 1668 of file sub.h.

ABA_LPSUB* ABA_SUB::lp_ [protected]

A pointer to the corresponding linear program.

Definition at line 1672 of file sub.h.

ABA_ARRAY<ABA_FSVARSTAT*>* ABA_SUB::fsVarStat_ [protected]

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.

Definition at line 1681 of file sub.h.

ABA_ARRAY<ABA_LPVARSTAT*>* ABA_SUB::lpVarStat_ [protected]

A pointer to an array storing the status of each active variable in the linear program.

Definition at line 1686 of file sub.h.

ABA_ARRAY<double>* ABA_SUB::lBound_ [protected]

A pointer to an array with the local lower bound of the active variables.

Definition at line 1690 of file sub.h.

ABA_ARRAY<double>* ABA_SUB::uBound_ [protected]

A pointer to an array with the local upper bounds of the active variables.

Definition at line 1694 of file sub.h.

ABA_ARRAY<ABA_SLACKSTAT*>* ABA_SUB::slackStat_ [protected]

A pointer to an array storing the statuses of the slack variables of the last solved linear program.

Definition at line 1699 of file sub.h.

ABA_TAILOFF* ABA_SUB::tailOff_ [protected]

A pointer to the tailing off manager.

Definition at line 1703 of file sub.h.

double ABA_SUB::dualBound_ [protected]

The dual bound of the subproblem.

Definition at line 1707 of file sub.h.

int ABA_SUB::nIter_ [protected]

The number of iterations in the cutting plane phase.

Definition at line 1711 of file sub.h.

int ABA_SUB::lastIterConAdd_ [protected]

The last iteration in which constraints have been added.

Definition at line 1715 of file sub.h.

int ABA_SUB::lastIterVarAdd_ [protected]

The last iteration in which variables have been added.

Definition at line 1719 of file sub.h.

ABA_BRANCHRULE* ABA_SUB::branchRule_ [protected]

The branching rule for the subproblem.

Definition at line 1723 of file sub.h.

bool ABA_SUB::allBranchOnSetVars_ [protected]

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.

Definition at line 1729 of file sub.h.

ABA_LP::METHOD ABA_SUB::lpMethod_ [protected]

The solution method for the next linear program.

Definition at line 1733 of file sub.h.

ABA_CUTBUFFER<ABA_VARIABLE, ABA_CONSTRAINT>* ABA_SUB::addVarBuffer_ [protected]

The buffer of the newly generated variables.

Definition at line 1737 of file sub.h.

ABA_CUTBUFFER<ABA_CONSTRAINT, ABA_VARIABLE>* ABA_SUB::addConBuffer_ [protected]

The buffer of the newly generated constraints.

Definition at line 1741 of file sub.h.

ABA_BUFFER<int>* ABA_SUB::removeVarBuffer_ [protected]

The buffer of the variables which are removed at the beginning of the next iteration.

Definition at line 1746 of file sub.h.

ABA_BUFFER<int>* ABA_SUB::removeConBuffer_ [protected]

The buffer of the constraints which are removed at the beginning of the next iteration.

Definition at line 1751 of file sub.h.

double* ABA_SUB::xVal_ [protected]

The last LP-solution.

Definition at line 1755 of file sub.h.

double* ABA_SUB::yVal_ [protected]

The dual variables of the last linear program.

Definition at line 1759 of file sub.h.

double* ABA_SUB::bInvRow_ [protected]

A row of the basis inverse associated with the infeasible variable infeasVar_ or slack variable infeasCon_.

Definition at line 1764 of file sub.h.

int ABA_SUB::infeasCon_ [protected]

The number of an infeasible constraint.

Definition at line 1768 of file sub.h.

int ABA_SUB::infeasVar_ [protected]

The number of an infeasible variable.

Definition at line 1772 of file sub.h.

bool ABA_SUB::genNonLiftCons_ [protected]

If true, then the management of non-liftable constraints is performed.

Definition at line 1776 of file sub.h.

int ABA_SUB::level_ [private]

The level of the subproblem in the enumeration tree.

Definition at line 2024 of file sub.h.

int ABA_SUB::id_ [private]

The number of the subproblem.

Definition at line 2028 of file sub.h.

STATUS ABA_SUB::status_ [private]

The status of the subproblem.

Definition at line 2035 of file sub.h.

ABA_BUFFER<ABA_SUB*>* ABA_SUB::sons_ [private]

The sons of the node in the \ tree.

Definition at line 2039 of file sub.h.

int ABA_SUB::maxIterations_ [private]

The maximum number of iterations in the cutting plane phase.

Definition at line 2043 of file sub.h.

int ABA_SUB::nOpt_ [private]

The number of optimizations of the subproblem.

Definition at line 2047 of file sub.h.

bool ABA_SUB::relativeReserve_ [private]

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.

Definition at line 2056 of file sub.h.

double ABA_SUB::varReserve_ [private]

The additional space for variables.

Definition at line 2060 of file sub.h.

double ABA_SUB::conReserve_ [private]

The additional space for constraints.

Definition at line 2064 of file sub.h.

double ABA_SUB::nnzReserve_ [private]

The additional space for nonzeros.

Definition at line 2068 of file sub.h.

int ABA_SUB::nDormantRounds_ [private]

The number of subproblem optimizations the subproblem has already the status Dormant.

Definition at line 2073 of file sub.h.

bool ABA_SUB::activated_ [private]

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.

Definition at line 2080 of file sub.h.

bool ABA_SUB::ignoreInTailingOff_ [private]

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().

Definition at line 2086 of file sub.h.

ABA_LP::METHOD ABA_SUB::lastLP_ [private]

The method that was used to solve the last LP.

Definition at line 2089 of file sub.h.

ABA_CPUTIMER ABA_SUB::localTimer_ [private]

Definition at line 2091 of file sub.h.

bool ABA_SUB::forceExactSolver_ [private]

Indicates whether to force the use of an exact solver to prepare branching etc.

Definition at line 2096 of file sub.h.

ABA_SUB Class Reference

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Friends

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation


Public Types
enum	STATUS { Unprocessed, Active, Dormant, Processed, Fathomed }
enum	PHASE { Done, Cutting, Branching, Fathoming }
	The optimization of the subproblem can be in one of the following phases:. More...
Public Member Functions
	ABA_SUB (ABA_MASTER master, double conRes, double varRes, double nnzRes, bool relativeRes=true, ABA_BUFFER< ABA_POOLSLOT< ABA_CONSTRAINT, ABA_VARIABLE > > constraints=0, ABA_BUFFER< ABA_POOLSLOT< ABA_VARIABLE, ABA_CONSTRAINT > > *variables=0)
	The constructor for the root node of the enumeration tree.
	ABA_SUB (ABA_MASTER master, ABA_SUB father, ABA_BRANCHRULE *branchRule)
	The constructor for non-root nodes of the enumeration tree.
virtual	~ABA_SUB ()
bool	forceExactSolver () const
int	level () const
int	id () const
STATUS	status () const
int	nVar () const
int	maxVar () const
int	nCon () const
int	maxCon () const
double	lowerBound () const
double	upperBound () const
double	dualBound () const
void	dualBound (double x)
	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.
const ABA_SUB *	father () const
ABA_LPSUB *	lp () const
void	maxIterations (int max)
ABA_ACTIVE< ABA_CONSTRAINT, ABA_VARIABLE > *	actCon () const
ABA_ACTIVE< ABA_VARIABLE, ABA_CONSTRAINT > *	actVar () const
ABA_CONSTRAINT *	constraint (int i) const
ABA_SLACKSTAT *	slackStat (int i) const
ABA_VARIABLE *	variable (int i) const
double	lBound (int i) const
void	lBound (int i, double l)
double	uBound (int i) const
void	uBound (int i, double u)
	This version of the function uBound() sets thef local upper bound of a variable.
ABA_FSVARSTAT *	fsVarStat (int i) const
ABA_LPVARSTAT *	lpVarStat (int i) const
double	xVal (int i) const
double	yVal (int i) const
bool	ancestor (const ABA_SUB *sub) const
ABA_MASTER *	master () const
void	removeVars (ABA_BUFFER< int > &remove)
	With function removeVars() variables can be removed from the set of active variables.
void	removeVar (int i)
double	nnzReserve () const
bool	relativeReserve () const
ABA_BRANCHRULE *	branchRule () const
bool	objAllInteger ()
	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.
virtual void	removeCons (ABA_BUFFER< int > &remove)
	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.
virtual void	removeCon (int i)
	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.
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.
int	nDormantRounds () const
void	ignoreInTailingOff ()
virtual int	addBranchingConstraint (ABA_POOLSLOT< ABA_CONSTRAINT, ABA_VARIABLE > *slot)
	Adds a branching constraint to the constraint buffer such that it is automatically added at the beginning of the cutting plane algorithm.
Protected Member Functions
virtual int	addCons (ABA_BUFFER< ABA_CONSTRAINT * > &constraints, ABA_POOL< ABA_CONSTRAINT, ABA_VARIABLE > pool=0, ABA_BUFFER< bool > keepInPool=0, ABA_BUFFER< double > *rank=0)
virtual int	addCons (ABA_BUFFER< ABA_POOLSLOT< ABA_CONSTRAINT, ABA_VARIABLE > * > &newCons)
virtual int	addVars (ABA_BUFFER< ABA_VARIABLE * > &variables, ABA_POOL< ABA_VARIABLE, ABA_CONSTRAINT > pool=0, ABA_BUFFER< bool > keepInPool=0, ABA_BUFFER< double > *rank=0)
virtual int	addVars (ABA_BUFFER< ABA_POOLSLOT< ABA_VARIABLE, ABA_CONSTRAINT > * > &newVars)
virtual int	variablePoolSeparation (int ranking=0, ABA_POOL< ABA_VARIABLE, ABA_CONSTRAINT > *pool=0, double minViolation=0.001)
virtual int	constraintPoolSeparation (int ranking=0, ABA_POOL< ABA_CONSTRAINT, ABA_VARIABLE > *pool=0, double minViolation=0.001)
virtual void	activate ()
	Does nothing but can be used as an entrance point for problem specific activations by a reimplementation in derived classes.
virtual void	deactivate ()
	Can be used as entrance point for problem specific deactivations after the subproblem optimization.
virtual int	generateBranchRules (ABA_BUFFER< ABA_BRANCHRULE * > &rules)
virtual int	branchingOnVariable (ABA_BUFFER< ABA_BRANCHRULE * > &rules)
	Generates branching rules for two new subproblems by selecting a branching variable with the function selectBranchingVariable().
virtual int	selectBranchingVariable (int &variable)
virtual int	selectBranchingVariableCandidates (ABA_BUFFER< int > &candidates)
	Selects depending on the branching variable strategy given by the parameter { BranchingStrategy} in the file { .abacus} candidates that for branching variables.
virtual int	selectBestBranchingSample (int nSamples, ABA_BUFFER< ABA_BRANCHRULE * > **samples)
	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().
virtual void	rankBranchingSample (ABA_BUFFER< ABA_BRANCHRULE * > &sample, ABA_ARRAY< double > &rank)
	Computes for each branching rule of a branching sample a rank with the function rankBranchingRule().
virtual double	rankBranchingRule (ABA_BRANCHRULE *branchRule)
double	lpRankBranchingRule (ABA_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. This modifiction is undone after the solution of the linear program.
virtual int	compareBranchingSampleRanks (ABA_ARRAY< double > &rank1, ABA_ARRAY< double > &rank2)
int	closeHalfExpensive (int &branchVar, ABA_VARTYPE::TYPE branchVarType)
	Selects a single branching variable of type branchVarType, with fractional part close to and high absolute objective function coefficient.
int	closeHalfExpensive (ABA_BUFFER< int > &variables, ABA_VARTYPE::TYPE branchVarType)
	This version of the function closeHalfExpensive() selects several candidates for branching variables of type branchVarType.
int	closeHalf (int &branchVar, ABA_VARTYPE::TYPE branchVarType)
	Searches a branching variable of type branchVarType, with fraction as close to as possible.
int	closeHalf (ABA_BUFFER< int > &branchVar, ABA_VARTYPE::TYPE branchVarType)
	Searches searches several possible branching variable of type branchVarType, with fraction as close to as possible.
int	findNonFixedSet (ABA_BUFFER< int > &branchVar, ABA_VARTYPE::TYPE branchVarType)
int	findNonFixedSet (int &branchVar, ABA_VARTYPE::TYPE branchVarType)
virtual int	initMakeFeas (ABA_BUFFER< ABA_INFEASCON * > &infeasCon, ABA_BUFFER< ABA_VARIABLE * > &newVars, ABA_POOL< ABA_VARIABLE, ABA_CONSTRAINT > **pool)
	The default implementation of the virtual initMakeFeas() does nothing.
virtual int	makeFeasible ()
	The default implementation of makeFeasible() does nothing.
virtual bool	goodCol (ABA_COLUMN &col, ABA_ARRAY< double > &row, double x, double lb, double ub)
virtual void	setByLogImp (ABA_BUFFER< int > &variable, ABA_BUFFER< ABA_FSVARSTAT * > &status)
	The default implementation of setByLogImp() does nothing.
virtual bool	feasible ()=0
	The pure virtual function feasible() checks for the feasibility of a solution of the LP-relaxation.
bool	integerFeasible ()
	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.
virtual bool	primalSeparation ()
	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.
virtual int	separate ()
virtual void	conEliminate (ABA_BUFFER< int > &remove)
	Can be used as an entry point for application specific elimination of constraints by redefinig it in derived classes.
virtual void	nonBindingConEliminate (ABA_BUFFER< int > &remove)
	Retrieves the dynamic constraints with slack exceeding the value given by the parameter { ConElimEps}.
virtual void	basicConEliminate (ABA_BUFFER< int > &remove)
virtual void	varEliminate (ABA_BUFFER< int > &remove)
	Provides an entry point for application specific variable elimination that can be implemented by redefining this function in a derived class.
void	redCostVarEliminate (ABA_BUFFER< int > &remove)
virtual int	pricing ()
virtual int	improve (double &primalValue)
	Can be redefined in derived classes in order to implement primal heuristics for finding feasible solutions.
virtual ABA_SUB *	generateSon (ABA_BRANCHRULE *rule)=0
	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.
bool	boundCrash () const
virtual bool	pausing ()
bool	infeasible ()
virtual void	varRealloc (int newSize)
	Reallocates memory that at most newSize variables can be handled in the subproblem.
virtual void	conRealloc (int newSize)
	Reallocates memory that at most newSize constraints can be handled in the subproblem.
virtual ABA_LP::METHOD	chooseLpMethod (int nVarRemoved, int nConRemoved, int nVarAdded, int nConAdded)
virtual bool	tailingOff ()
bool	betterDual (double x) const
virtual void	selectVars ()
virtual void	selectCons ()
virtual int	fixByRedCost (bool &newValues, bool saveCand)
virtual void	fixByLogImp (ABA_BUFFER< int > &variable, ABA_BUFFER< ABA_FSVARSTAT * > &status)
	Should collect the numbers of the variables to be fixed in variable and the respective statuses in status.
virtual int	fixAndSet (bool &newValues)
	Tries to fix and set variables both by logical implications and reduced cost criteria.
virtual int	fixing (bool &newValues, bool saveCand=false)
virtual int	setting (bool &newValues)
	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.
virtual int	setByRedCost ()
virtual void	fathom (bool reoptimize)
virtual bool	fixAndSetTime ()
virtual int	fix (int i, ABA_FSVARSTAT *newStat, bool &newValue)
virtual int	set (int i, ABA_FSVARSTAT *newStat, bool &newValue)
virtual int	set (int i, ABA_FSVARSTAT::STATUS newStat, bool &newValue)
virtual int	set (int i, ABA_FSVARSTAT::STATUS newStat, double value, bool &newValue)
virtual double	dualRound (double x)
virtual double	guarantee ()
virtual bool	guaranteed ()
virtual bool	removeNonLiftableCons ()
virtual int	prepareBranching (bool &lastIteration)
virtual void	fathomTheSubTree ()
virtual int	optimize ()
virtual void	reoptimize ()
virtual void	initializeVars (int maxVar)
virtual void	initializeCons (int maxCon)
virtual PHASE	branching ()
	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).
virtual PHASE	fathoming ()
	Fathoms the node, and if certain conditions are satisfied, also its ancestor.
virtual PHASE	cutting ()
	Iteratively solves the LP-relaxation, generates constraints and/or variables.
virtual ABA_LPSUB *	generateLp ()
virtual int	initializeLp ()
virtual int	solveLp ()
virtual bool	exceptionFathom ()
	Can be used to specify a problem specific fathoming criterium that is checked before the separation or pricing.
virtual bool	exceptionBranch ()
virtual bool	solveApproxNow ()
Protected Attributes
ABA_MASTER *	master_
ABA_ACTIVE< ABA_CONSTRAINT, ABA_VARIABLE > *	actCon_
ABA_ACTIVE< ABA_VARIABLE, ABA_CONSTRAINT > *	actVar_
ABA_SUB *	father_
ABA_LPSUB *	lp_
ABA_ARRAY< ABA_FSVARSTAT * > *	fsVarStat_
	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.
ABA_ARRAY< ABA_LPVARSTAT * > *	lpVarStat_
	A pointer to an array storing the status of each active variable in the linear program.
ABA_ARRAY< double > *	lBound_
ABA_ARRAY< double > *	uBound_
ABA_ARRAY< ABA_SLACKSTAT * > *	slackStat_
	A pointer to an array storing the statuses of the slack variables of the last solved linear program.
ABA_TAILOFF *	tailOff_
double	dualBound_
int	nIter_
int	lastIterConAdd_
int	lastIterVarAdd_
ABA_BRANCHRULE *	branchRule_
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.
ABA_LP::METHOD	lpMethod_
ABA_CUTBUFFER< ABA_VARIABLE, ABA_CONSTRAINT > *	addVarBuffer_
ABA_CUTBUFFER< ABA_CONSTRAINT, ABA_VARIABLE > *	addConBuffer_
ABA_BUFFER< int > *	removeVarBuffer_
	The buffer of the variables which are removed at the beginning of the next iteration.
ABA_BUFFER< int > *	removeConBuffer_
	The buffer of the constraints which are removed at the beginning of the next iteration.
double *	xVal_
double *	yVal_
double *	bInvRow_
	A row of the basis inverse associated with the infeasible variable infeasVar_ or slack variable infeasCon_.
int	infeasCon_
int	infeasVar_
bool	genNonLiftCons_
Private Member Functions
virtual int	_separate ()
virtual int	_conEliminate ()
virtual int	_varEliminate ()
virtual int	_pricing (bool &newValues, bool doFixSet=true)
virtual int	_improve (double &primalValue)
virtual int	_fixByLogImp (bool &newValues)
	Returns 1, if a contradiction has been found, 0 otherwise.
virtual void	updateBoundInLp (int i)
virtual double	fixSetNewBound (int i)
	Returns the value which the upper and lower bounds of a variable should take after it is fixed or set.
virtual void	newDormantRound ()
virtual PHASE	_activate ()
	Allocates and initializes memory of the subproblem at the beginning of the optimization.
virtual void	_deactivate ()
	Deallocates the memory which is not required after the optimization of the subproblem.
virtual int	_initMakeFeas ()
	Tries to add variables to restore infeasibilities detected at initialization time.
virtual int	_makeFeasible ()
	Is called if the LP is infeasible and adds inactive variables, which can make the LP feasible again, to the set of active variables.
virtual int	_setByLogImp (bool &newValues)
	Tries to set variables according to logical implications of already set and fixed variables.
virtual void	infeasibleSub ()
virtual void	getBase ()
virtual void	activateVars (ABA_BUFFER< ABA_POOLSLOT< ABA_VARIABLE, ABA_CONSTRAINT > * > &newVars)
	Adds the variables stored in the pool slots of newVars to the set of active variables, but not to the linear program.
virtual void	addVarsToLp (ABA_BUFFER< ABA_POOLSLOT< ABA_VARIABLE, ABA_CONSTRAINT > * > &newVars, ABA_BUFFER< ABA_FSVARSTAT * > *localStatus=0)
	Adds the variables stored in the pool slots of newVars to the linear program. localStatus can specify a local status of fixing and setting.
virtual void	_selectVars (ABA_BUFFER< ABA_POOLSLOT< ABA_VARIABLE, ABA_CONSTRAINT > * > &newVars)
virtual void	_selectCons (ABA_BUFFER< ABA_POOLSLOT< ABA_CONSTRAINT, ABA_VARIABLE > * > &newCons)
	Selects the master_->maxConAdd() best constraints from the buffered constraints and stores them in newCons.
virtual int	_removeVars (ABA_BUFFER< int > &remove)
virtual int	_removeCons (ABA_BUFFER< int > &remove)
	ABA_SUB (const ABA_SUB &rhs)
const ABA_SUB &	operator= (const ABA_SUB &rhs)
Private Attributes
int	level_
int	id_
STATUS	status_
ABA_BUFFER< ABA_SUB * > *	sons_
int	maxIterations_
int	nOpt_
bool	relativeReserve_
	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.
double	varReserve_
double	conReserve_
double	nnzReserve_
int	nDormantRounds_
	The number of subproblem optimizations the subproblem has already the status Dormant.
bool	activated_
	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.
bool	ignoreInTailingOff_
	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().
ABA_LP::METHOD	lastLP_
	The method that was used to solve the last LP.
ABA_CPUTIMER	localTimer_
bool	forceExactSolver_
	Indicates whether to force the use of an exact solver to prepare branching etc.
Friends
class	ABA_MASTER
class	ABA_BOUNDBRANCHRULE
class	ABA_OPENSUB
class	ABA_LPSOLUTION< ABA_CONSTRAINT, ABA_VARIABLE >
class	ABA_LPSOLUTION< ABA_VARIABLE, ABA_CONSTRAINT >