public class MaxNetwork extends Object
Characteristics of the network : There are 4 types of nodes in this network : the source node, the sink node, the call type nodes and the agent group nodes. For each call type and each agent group in the call center, there is an associated node in the network. This makes a total of (number of call types + number of agent groups + 2) nodes.
There are 3 types of arcs: from the source node to a call type node, from a call type node to an agent group node (that can serve this call type) and from an agent group node to the sink node. There is an arc from the source node to every call type nodes and its upper bound capacity is equal to the arrival rate over the service rate of the call type ( (λ) / (μ) = ρ), which is the load. A load coefficient α is used to control the load ρ.
There is an arc from each agent group node to the sink node and its upper bound capacity is equal to the number of agents in the group. There is an arc leaving from a call type node i to an agent group node j if the agent group j can serve call type i. The agent skill sets are used to determine these arcs. The upper bound capacity is infinity and the lower bound capacity is zero for all arcs.
The following figure shows the graph flow with the minimum and maximum capacities of each arc, where there are M agent groups and N call types.
The flow conservation rule is: for every node except the source and the sink nodes, the sum of the flow that enters in a node is equal to the sum of the flow that leaves the node.
With the traditional linear constraint method, the number of constraints that ensure the coverage of the skill supplies over any composition of the customer demand is exponential. Solving a Max-flow min-cut problem can reduce the computation time.
Here is a quick summary of the available functions:
findMaxFlow(umontreal.iro.lecuyer.ccoptim.util.Solver)
builds the network problem and solves the LP
(finds the maximum flow that can pass through the network from the source
node to the sink node) and returns the maximum flow value.
findFlowCut()
finds the minimum-cut sets of the network after solving
the Max-Flow.
The user needs to call findMaxFlow(umontreal.iro.lecuyer.ccoptim.util.Solver) before calling findFlowCut().
Each instance of this class should represent one 1 network flow problem.
So the max-flow problem needs to be solved only once with findMaxFlow(umontreal.iro.lecuyer.ccoptim.util.Solver)
,
and the solution is saved by the instance.
Calling findMaxFlow(umontreal.iro.lecuyer.ccoptim.util.Solver) subsequently will only return the cached solution.
Constructor and Description |
---|
MaxNetwork(int[] numAgents,
ArrayList<List<Integer>> callGroups,
double[] arrivalRates,
double[] serviceRates,
double[] netRhoCoeff)
Constructs a new network, but not the LP model.
|
Modifier and Type | Method and Description |
---|---|
boolean[] |
findFlowCut()
Finds the minimum-cut and returns the set in a boolean array
representing the nodes.
|
double |
findMaxFlow(Solver s)
Solves the max-flow problem of this network, from the source node to the sink node.
|
double[] |
getArcFlowSolution()
Returns the flows of the arcs after solving the max-flow problem.
|
double |
getObjValue()
Returns the maximum flow found by the solver for the max-flow problem.
|
public MaxNetwork(int[] numAgents, ArrayList<List<Integer>> callGroups, double[] arrivalRates, double[] serviceRates, double[] netRhoCoeff) throws IllegalArgumentException
numAgents
- the number of agents for each agent groups.callGroups
- a list that contains for each call type a list of groups that can
serve this call type. The agent group numbering starts with zero.arrivalRates
- represents the arrival rate for each call type.
arrivalRate[i]
= arrival rate for call type i
.serviceRates
- represents the service rates for each call type.
The service rates are equal for all agent groups.netRhoCoeff
- the coefficient vector that multiplies ρ (the load), for each call type.IllegalArgumentException
- if the array length are not compatible.public double findMaxFlow(Solver s) throws SolverException
getArcFlowSolution()
and
getObjValue()
.s
- the solver instance to be usedSolverException
- if an error occurred while creating or solving the max-flow problempublic boolean[] findFlowCut() throws SolverException
true
are in the same set as the source node and the elements that contain
false
are in the same set as the sink node.
First, the max-flow must be already solved by calling
findMaxFlow(umontreal.iro.lecuyer.ccoptim.util.Solver)
to obtain the residual network. If the flow is
greater or equal to the aggregate ρ then there are no minimum-cuts,
since all the flow has passed.
true
then node i is in the same set as
the source node. Otherwise, it is in the same set as the sink node.
Returns null
if there are no minimum-cuts.SolverException
- if the Max-Flow hasn't been solved.public double getObjValue() throws NullPointerException
NullPointerException
- if the max-flow problem has not been solvedpublic double[] getArcFlowSolution() throws NullPointerException
NullPointerException
- if the max-flow problem has not been solved yet