branchMaxCut Class Reference
[Maximum edge cuts]

Branch & bound implementation for maximum edge cuts. More...

#include <branchMaxCut.h>

Inheritance diagram for branchMaxCut:

branchNode< TNode, TFloat > managedObject goblinRootObject

Public Member Functions

 branchMaxCut (abstractMixedGraph &, TNode=NoNode, TNode=NoNode) throw ()
 branchMaxCut (branchMaxCut &) throw ()
 ~branchMaxCut () throw ()
unsigned long Size () const throw ()
unsigned long Allocated () const throw ()
TFloat SumWeight (TNode) throw ()
TFloat MinWeight (TNode) throw ()
TFloat MaxWeight (TNode) throw ()
TNode SelectVariable () throw ()
TBranchDir DirectionConstructive (TNode i) throw (ERRange)
TBranchDir DirectionExhaustive (TNode i) throw (ERRange)
branchNode< TNode, TFloat > * Clone () throw ()
void Raise (TNode i) throw (ERRange)
void Lower (TNode i) throw (ERRange)
TFloat SolveRelaxation () throw ()
TObjectSense ObjectSense () const throw ()
TFloat Infeasibility () const throw ()
void SaveSolution () throw ()
void ReallySaveSolution () throw ()
TFloat LocalSearch () throw ()

Data Fields

TFloat totalWeight
TFloat selectedWeight
TFloat dismissedWeight
abstractMixedGraphG
TNode currentVar

Detailed Description

Branch & bound implementation for maximum edge cuts.


Constructor & Destructor Documentation

branchMaxCut abstractMixedGraph ,
TNode  = NoNode,
TNode  = NoNode
throw ()
 

branchMaxCut branchMaxCut  )  throw ()
 

~branchMaxCut  )  throw ()
 


Member Function Documentation

unsigned long Allocated  )  const throw ()
 

Reimplemented from branchNode< TNode, TFloat >.

branchNode< TNode, TFloat > * Clone  )  throw () [virtual]
 

Generate a copy of this branch node.

Returns:
A pointer to the copy

Implements branchNode< TNode, TFloat >.

branchNode< TNode, TFloat >::TBranchDir DirectionConstructive TNode  v  )  throw (ERRange) [virtual]
 

Preferred search direction before feasibility has been achieved.

Implements branchNode< TNode, TFloat >.

branchNode< TNode, TFloat >::TBranchDir DirectionExhaustive TNode  v  )  throw (ERRange) [virtual]
 

Preferred search direction after feasibility has been achieved.

Implements branchNode< TNode, TFloat >.

TFloat Infeasibility  )  const throw () [virtual]
 

Symbolic value for infeasible subproblems.

Implements branchNode< TNode, TFloat >.

TFloat LocalSearch  )  throw () [virtual]
 

Apply a probelm dependent local search method.

Returns:
The (possibly improved) objective value

Reimplemented from branchNode< TNode, TFloat >.

void Lower TNode  i  )  throw (ERRange) [virtual]
 

Lower an upper variable bound.

This operation applies after solving a relaxation and duplicating the branch node. It sets an upper variable bound to the greatest integral lower bound on the current variable value.

The operation may restrict further variables, namely, if it is obvoious that no solutions for the master problem are lost.

Parameters:
i The index of the restricted variable

Implements branchNode< TNode, TFloat >.

TFloat MaxWeight TNode   )  throw ()
 

TFloat MinWeight TNode   )  throw ()
 

branchNode< TNode, TFloat >::TObjectSense ObjectSense  )  const throw () [virtual]
 

Decide between maximization and minimization problems.

Implements branchNode< TNode, TFloat >.

void Raise TNode  i  )  throw (ERRange) [virtual]
 

Raise a lower variable bound.

This operation applies after solving a relaxation and duplicating the branch node. It sets a lower variable bound to the least integral upper bound on the current variable value.

The operation may restrict further variables, namely, if it is obvoious that no solutions for the master problem are lost.

Parameters:
i The index of the variable to be restricted

Implements branchNode< TNode, TFloat >.

void ReallySaveSolution  )  throw ()
 

void SaveSolution  )  throw () [virtual]
 

Copy the current solution to the original problem instance.

Implements branchNode< TNode, TFloat >.

TNode SelectVariable  )  throw () [virtual]
 

Selection of a variable to be restricted next.

Returns:
The branch variable index

Implements branchNode< TNode, TFloat >.

unsigned long Size  )  const throw () [virtual]
 

Implements goblinRootObject.

TFloat SolveRelaxation  )  throw () [virtual]
 

Solve the relaxed subproblem according.

Returns:
The objective value of this relaxed subproblem

Implements branchNode< TNode, TFloat >.

TFloat SumWeight TNode   )  throw ()
 


Field Documentation

TNode currentVar
 

TFloat dismissedWeight
 

abstractMixedGraph& G
 

TFloat selectedWeight
 

TFloat totalWeight