uk.ac.ic.doc.automed.p2p.qproc.optimise
Class CapacitatedNetworkFlowOptimiser

java.lang.Object
  uk.ac.ic.doc.automed.p2p.qproc.optimise.CapacitatedNetworkFlowOptimiser

public class CapacitatedNetworkFlowOptimiser
extends java.lang.Object

Field Summary

private Jama.Matrix	A
private Jama.Matrix	b
private static java.lang.String	BANNER0
private static java.lang.String	BANNER1
private Jama.Matrix	cprime
private Jama.Matrix	d
private Jama.Matrix	f
private FlowResultSet	fd
private GraphI	G
private java.util.logging.Logger	logger
private int	m
private int	n
private static int	SLEEP_TIME
private Jama.Matrix	u

Constructor Summary

CapacitatedNetworkFlowOptimiser(GraphI G, Jama.Matrix cprime, Jama.Matrix A, Jama.Matrix b, Jama.Matrix u, Jama.Matrix d, Jama.Matrix f)
Create a new instance of the optimiser object with the specified parameters

Method Summary

private void	analyseFlowCycle(LevelledGTree T, java.util.List F, java.util.List B, Edge ire, boolean edgeInU) Analyse the tree T after being added with an extra reduced cost edge to form a cycle.
void	dfs(Node n, LevelledGTree t, int nodeCount, int level) Depth first search of the flow graph to construct a tree that has a specified number of nodes
FlowResultSet	getResult()
private Jama.Matrix	initBFS(LevelledGTree T, java.util.Set U, java.util.Set D) Construct an initial tree T from G and partition the remaining arcs into an upper bound sets (U) and a lower bound set (D).
void	optimiseFlow()
private Jama.Matrix	p(GTree T) Calculate the vector p based on the equality constraints of the cost differences of the basic flows

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

G

private GraphI G

cprime

private Jama.Matrix cprime

A

private Jama.Matrix A

b

private Jama.Matrix b

u

private Jama.Matrix u

d

private Jama.Matrix d

f

private Jama.Matrix f

n

private int n

m

private int m

fd

private FlowResultSet fd

logger

private java.util.logging.Logger logger

BANNER0

private static final java.lang.String BANNER0

See Also:

Constant Field Values

BANNER1

private static final java.lang.String BANNER1

See Also:

Constant Field Values

SLEEP_TIME

private static final int SLEEP_TIME

See Also:

Constant Field Values

Constructor Detail

CapacitatedNetworkFlowOptimiser

public CapacitatedNetworkFlowOptimiser(GraphI G,
                                       Jama.Matrix cprime,
                                       Jama.Matrix A,
                                       Jama.Matrix b,
                                       Jama.Matrix u,
                                       Jama.Matrix d,
                                       Jama.Matrix f)

Create a new instance of the optimiser object with the specified parameters

Parameters:

G - the directed network flow graph with n nodes and m edges

cprime - the cost vector (1xm)

A - the (initial) node-arc incident matrix (nxm)

b - the RHS vector (1xn) of the flow constraints of nodes

u - the vector (1xm) of upper bound constraints

d - the vector (1xm) of lower bound constraints

f - the vector (1xm) of the flow variables (one for an edge)

Method Detail

optimiseFlow

public void optimiseFlow()
                  throws OptimisationException

Throws:

OptimisationException

analyseFlowCycle

private void analyseFlowCycle(LevelledGTree T,
                              java.util.List F,
                              java.util.List B,
                              Edge ire,
                              boolean edgeInU)

Analyse the tree T after being added with an extra reduced cost edge to form a cycle. Basically this involves finding the cycle and at the same time classifying the nodes in the cycle into two sets: one set (F) contains all forward arcs and one set (B) contains all backward arcs

Parameters:

T - the tree with one cycle

F - set of forward arcs

B - set of backward arcs

ire - the newly added edge (which causes a cycle)

edgeInU - whether or not the tree is in the upperbound or lower bound edge set

p

private Jama.Matrix p(GTree T)

Calculate the vector p based on the equality constraints of the cost differences of the basic flows

Returns:

initBFS

private Jama.Matrix initBFS(LevelledGTree T,
                            java.util.Set U,
                            java.util.Set D)

Construct an initial tree T from G and partition the remaining arcs into an upper bound sets (U) and a lower bound set (D). It also returns the initial flow matrix f calculated from T.

Parameters:

T - the feasible tree to be constructed

U - the set of edges corresponding to the upper bound constraints

D - the set of edges corresponding to the lower bound constraints

Returns:

the matrix of a basic feasible solution corresponding to tree T

dfs

public void dfs(Node n,
                LevelledGTree t,
                int nodeCount,
                int level)

Depth first search of the flow graph to construct a tree that has a specified number of nodes

Parameters:

n -

t -

nodeCount -

level -

getResult

public FlowResultSet getResult()