public class CuttingPlaneOptimizer extends Object implements StaffingOptimizer
The goal is to minimize the staffing cost of agents while satisfying all the constraints on the service levels (SLs). The service level constraint can be defined for each call type or globally over all calls.
The algorithm starts with an initial linear problem model that defines the staffing cost of the objective function to optimize. Right now, the program is set to solve the LP (linear problem) instead of an IP (integer problem) to reduce the solving time in big problems.
Each time the problem is solved with a linear solver (Solver
)
it must verify if the solution satisfies two constraints :
1) The skill-supply (agents) covers any composition of the customer demand. In
other words, the number of agents that can serve a composition of call
types must be greater or equal to the total of the ρ of the
composition times an arbitrary coefficient for each call type.
This coefficient is set by the user
with the parameter CuttingPlaneParams.loadCoefficient
.
2) The solution must satisfy the minimum service level (SL) for each call type and also the overall SL. The SL of a staffing vector is computed by using simulation or approximation. The results are then compared with the minimum required SL.
Depending on the SL, there are several possible cases :
If a heuristic cut is added to the problem model, this constraint is tracked
if the user sets the option changeHeuristicCut = true
.
This constraint is the number of agents that can serve this call type
must be greater or equal than their numbers for the current solution plus a
scaling factor. The algorithm keeps track of last heuristic cut, since we don't
want it to improve the SL too drastically. After solving with the new heuristic
cut, if the SL for that call type increased over a certain level, the algorithm
will change the newly added heuristic constraint. It lowers the right hand side
of the constraint until it finds the constraint that improves the SL around a
certain percentage for that call type or the number of additional agents
increased only by 1. The Max-Flow is tested after each solution generated.
If the minimum targeted SL for every call types are satisfied but not
the overall SL, then a overall SL subgradient cut is generated. The step
length SubStep
used to compute the subgradient may be set by the user.
If the minimum SL for each call is satisfied but not the overall SL :
if the overall SL is below pivotPerCallSL
, then a overall SL
subgradient is generated. Otherwise, a subgradient is generated for each
call type.
If both the minimum SL for each call type and the SL for heuristic cut are not satisfied, then : If the overall SL is not close to target SL, then it generates a subgradient of the overall SL. Else, depending on the priority, it generates a subgradient for each call type or a heuristic cut.
If the minimum SL of the heuristic cut is not satisfied but the minimum SL per call type is satisfied then, only a heuristic cut is generated.
If the minimum SL per call type is not satisfied but the heuristic SL is satisfied then : If the overall SL is near the targeted SL then a subgradient is generated for each call type. Else, a subgradient is generated for the overall SL.
The subgradient cut is done by approximating the number of agents needed to achieve a SL equal or higher than the targeted overall SL (for example, target SL = 0.80). To find the subgradient, it records the improvement made by adding agents to one group at a time. With the subgradient, it uses a linear approximation from the current staffing vector to estimate the additional staffing that would be needed to reach the targeted overall SL.
Otherwise, the second constraint is satisfied.
With the optimal staffing vector, it will try to lower the objective solution by doing a local search while keeping the overall SL and the SL for each call type equal or above their target value.
An optional final step is to perform a local search to an optimal vector
solution to lower the number of agents, see localSearch(int[])
.
Instead of using one instance of the solver throughout the optimization and adding or changing constraints, the new version will recreate a new instance of the solver at each iteration of the optimization. The constraints generate throughout the optimization are kept in memory so they are reloaded at the creation of each new solver instance. Also, it can no longer import IP/LP file. All constraints are generated by the program.
Modifier and Type | Class and Description |
---|---|
static class |
CuttingPlaneOptimizer.LocalSearchMethod
This enumeration contains the possible local search methods
that can be used.
|
Modifier and Type | Field and Description |
---|---|
protected double[] |
agentCosts
The cost per agent per group.
|
protected double[] |
arrivalRates
The arrival rate vector for the call types.
|
protected ArrayList<List<Integer>> |
callGroups
A list that contains for each call type a list of groups that can
serve this call type.
|
protected CallCenter |
cc |
protected int |
constraintCount
The cumulative count of constraints.
|
protected HashMap<Integer,LinearConstraint> |
constraintMap
The hash map contains the linear constraints and the keys are the id number of the constraints.
|
protected CuttingPlaneTest |
cpTest |
protected CuttingPlaneParams |
cutp |
protected ContactCenterEval |
eval |
protected int[] |
numAgents
The number of agents for each agent group.
|
protected double[] |
numAgentsNoRound
The staffing solution without rounding.
|
protected int |
numGroups |
protected int |
numTypes |
protected double |
objValue |
protected double |
optSL
The global service level of the optimal solution
optSolution ,
or -1 if the optimization has not been executed. |
protected double[] |
optSLPerCall
The service level per call type of the optimal solution
optSolution ,
or null if the optimization has not been executed. |
protected StaffingSolution |
optSolution
The optimal solution, or
null if the optimization has
not been executed. |
protected double[][] |
serviceRates
The service rate matrix for each call type and group.
|
protected double[] |
serviceRatesIG
The service rate vector (for each call type) when they are
independent from the agent groups.
|
protected Solver |
solver |
protected long |
solverTimeSec |
protected DecimalFormat |
staffNoRoundDf
To format the values of the unrounded staffing vector.
|
protected HashMap<String,Integer> |
varIndexMap
This hash map contains the variables of the linear problem.
|
protected boolean |
verbose |
Constructor and Description |
---|
CuttingPlaneOptimizer(CallCenter cc,
CuttingPlaneParams cutParams,
CuttingPlaneTest cpTest,
ContactCenterEval eval)
Constructs and initializes a cutting plane optimizer
with no initial linear programming problem.
|
Modifier and Type | Method and Description |
---|---|
protected int |
addConstraint(double[] coef,
LinearConstraint.EnumSense s,
double rhs)
Adds a constraint to the constraintMap.
|
protected boolean |
addHeuristicCut(int callType,
double sl)
Adds a heuristic cut to call type
callType with SL sl . |
protected boolean |
addIntConstr(int minSLIndexH,
double minSLH)
Adds a heuristic constraint to satisfy the minimum level of SL of
the worst SL unsatisfied call type.The number of agents that can serve this
call type must be greater or equal to its ρ.
|
protected boolean |
addIntMaxFlowConstr(int minSLIndexH,
double minSLH)
Adds a heuristic constraint to satisfy the minimum level of SL of
the worst SL unsatisfied call type.The number of agents that can serve this
call type must be greater or equal to its ρ.
|
protected boolean |
addSubGradientConstraint(SubgradientInfo subgInfo)
Adds subgradient cuts to the LP/IP.
|
protected boolean |
adjustHeuristicCut(int callType)
Controls the heuristic cut adjustment of call type
callType . |
protected void |
ccEval(int[] staffing)
Calls the simulator for the given staffing.
|
protected boolean |
changeConstraintRhs(int index,
double newRhs)
Change the right hand side (rhs) value of a constraint in the hash map.
|
protected void |
createSolverInstance()
This method creates the solver for both initialization option (max-flow and network flow).
|
protected static boolean |
equal(double a,
double b)
Function to test if two numbers are (satisfactory) equal.
|
boolean |
exportLP(String filename)
Export LP model to file.
|
void |
freeSolver()
Free up the solver.
|
Solver |
generateSolver()
Returns a new instance of the default Solver used by the optimizer.
|
int[] |
getBestStaffing()
Returns the best feasible staffing vector found.
|
double |
getBestStaffingCost()
Returns the cost of the best staffing solution found.
|
CuttingPlaneParams |
getCuttingPlaneParams()
Returns the parameter object
CuttingPlaneParams . |
CuttingPlaneTest |
getCuttingPlaneTest()
Returns the
CuttingPlaneTest instance used for the simulation
and the estimation of the subgradients. |
protected int |
getMapFlowIndex(int type,
int group)
Get the variable index of the flow of a call type to an agent group.
|
protected int |
getMapStaffingIndex(int group)
Get the variable index from Map of the group.
|
double |
getOptimalSL()
Returns the overall SL for the optimal staffing vector returned
by
getBestStaffing |
double[] |
getOptimalSLPerCall()
Returns the SL for each call type for the optimal staffing vector
returned by getOptimalstaffing.
|
double[] |
getPerAgentCost()
Returns the cost per agent for each group.
|
double |
getStaffingCost(int[] staffing)
Return the cost of the staffing.
|
protected int[] |
localSearch(int[] staffing)
Calls the (possibly different) local search algorithm.
|
static void |
main(String[] args)
Runs the optimization with the entered parameters files.
|
void |
optimize()
Executes the cutting plane optimizing algorithm.
|
protected StaffingSolution |
optimizeCP()
Executes the cutting-plane optimization.
|
protected StaffingSolution |
optimizeLocalSearch()
Manage the local search optimization.
|
protected void |
printNumAgents(int[] staffing)
Prints the staffing vector.
|
protected void |
printNumAgents(int[] staffing,
boolean print)
Prints the staffing vector,
if parameter
print is set to true . |
void |
setDefaultSolver(Class c)
Sets the default Solver to be used by the optimizer.
|
protected boolean |
setMapFlowIndex(int type,
int group,
int index)
Set the variable index of the flow of a call type to an agent group.
|
protected boolean |
setMapStaffingIndex(int group,
int index)
Set the group variable index if not present in HashMap.
|
protected void |
solveMaxFlow()
Solves the MIP with the Max-Flow of the call center network
MaxNetwork so the skill supply covers any composition of the
customer demand. |
protected void |
solverSolve()
Internal use.
|
protected CallCenter cc
protected CuttingPlaneParams cutp
protected ContactCenterEval eval
protected boolean verbose
protected int numGroups
protected int numTypes
protected double[] arrivalRates
protected double[][] serviceRates
[call type][group]
.protected double[] serviceRatesIG
protected HashMap<Integer,LinearConstraint> constraintMap
varIndexMap
.protected HashMap<String,Integer> varIndexMap
The String
name for the staffing variables have the prefix
staff:
followed by the group number (group index starting at 0).
For example, group 0 has name "staff:0" without the quotes, and group 2
has name "staff:2".
If the program uses the network flow constraints, instead of solving the max-flow problem,
then the flow variables have the prefix flow:
following by
the call type number (type index starting at 0), followed by a comma ",",
and the group number (group index starting at 0).
For example, the flow variable of call type 2 and group 1 has the name
"flow:2,1" without the quotes.
protected int constraintCount
protected int[] numAgents
protected double[] numAgentsNoRound
protected DecimalFormat staffNoRoundDf
protected double[] agentCosts
protected StaffingSolution optSolution
null
if the optimization has
not been executed.protected double optSL
optSolution
,
or -1 if the optimization has not been executed.protected double[] optSLPerCall
optSolution
,
or null
if the optimization has not been executed.protected ArrayList<List<Integer>> callGroups
protected Solver solver
protected CuttingPlaneTest cpTest
protected double objValue
protected long solverTimeSec
public CuttingPlaneOptimizer(CallCenter cc, CuttingPlaneParams cutParams, CuttingPlaneTest cpTest, ContactCenterEval eval) throws OptimizerException
init
implicitly.cc
- the call center parameters.cutParams
- the parameter file for the optimizer program.cpTest
- the CuttingPlaneTest that will be used to compute the SL.eval
- the call center evaluator to use.OptimizerException
public static void main(String[] args) throws Exception
args
- see the descriptionException
public Solver generateSolver()
setDefaultSolver(java.lang.Class)
.public void setDefaultSolver(Class c)
c
- the class of the new solver to be used by default.protected void solverSolve() throws SolverException
Solver.solve()
function of the Solver and also updates the solutions.SolverException
- if an error occurred while solving the MIP.protected int addConstraint(double[] coef, LinearConstraint.EnumSense s, double rhs)
coef
- the coefficient vector of the constraint, the length of the vector must
be equal to the total number of variables in the solver.s
- the sense of the equationrhs
- the right-hand-side valueprotected boolean changeConstraintRhs(int index, double newRhs)
index
- the constraint index in the hash map.newRhs
- the new rhs value.public void freeSolver()
protected void createSolverInstance()
public void optimize() throws OptimizerException
If a composition of call type is not covered by the skill supply (not enough agents), then there is a Minimum-Cut in the Max-Flow of the network representation of the call center. The number of agents must be equal or greater than the ρ of that composition.
If the SL of a call type is below its minimum required SL, then it adds a heuristic constraint to satisfy its minimum SL. Else, if the SL does not satisfy the overall SL, then a subgradient cut is generated.
However, satisfying the SL constraint might violate the skill supply constraint. The algorithm iterates until both constraints are satisfied or until it exceeds a maximum number of iterations.
optimize
in interface StaffingOptimizer
OptimizerException
- if an error occurred in the optimization.protected StaffingSolution optimizeCP() throws OptimizerException
OptimizerException
protected StaffingSolution optimizeLocalSearch()
protected boolean adjustHeuristicCut(int callType)
callType
.
This procedure will activate if the last heuristic cut of call type callType
improves the SL of a call type with a SL below
CuttingPlaneParams.minEachSLH
to above CuttingPlaneParams.minEachSLH
+
CuttingPlaneParams.slHCorrectionGap
.
This procedure will try to limit the "improvement" of that heuristic cut
by increasing or decreasing the right hand side (RHS) of the cut, using
a binary search, so that the SL of call type callType
is between the values
minEachSLH
and minEachSLH + slHCorrectionGap
.callType
- call type index of the last heuristic cut.true
if adjustment was needed, else false
.protected boolean addSubGradientConstraint(SubgradientInfo subgInfo) throws OptimizerException
Here is the constraint to be added :
After rearranging the terms, it becomes :
subgInfo
- the subgradient information. If SubgradientInfo.getServiceLevel()
has only one element, then it is the global service level (SL), otherwise the
subgradient has been estimated for each call type with unsatisfied SL target.true
if the cuts have been added successfully,
or false
if no cut has been addedOptimizerException
protected boolean addHeuristicCut(int callType, double sl)
callType
with SL sl
.
To add a heuristic cut to the global SL, set callType
to the
number of call types CallCenter.getNumInContactTypes()
and sl
can be set at any value.
This method will automatically select to use method
double)
or double)
based on the parameter CuttingPlaneParams.solveWithMaxFlowCut
.callType
- the call type that needs a heuristic cutsl
- the service level of call type callType
true
if a heuristic cut has been added (or modified), else
false
.protected boolean addIntConstr(int minSLIndexH, double minSLH) throws SolverException
Constraint to add :
∑m=1MIm(n)ypm >= ceil(*ρn) + (threshold-minSL_p) / (threshold)ρn
minSLIndexH
- the index of the call type that has the worst
unsatisfied SL for a cut generation by heuristic.minSLH
- the current SL level of this unsatisfied call type.true
if a constraint was added, otherwise false
.SolverException
- if an error occurred while adding the constraint.protected boolean addIntMaxFlowConstr(int minSLIndexH, double minSLH) throws SolverException
Constraint to add :
minSLIndexH
- the index of the call type that has the worst
unsatisfied SL for a cut generation by heuristicminSLH
- the current SL level of this unsatisfied call typetrue
if a constraint was added, otherwise false
.SolverException
- if an error occurred while adding the constraintprotected void solveMaxFlow()
MaxNetwork
so the skill supply covers any composition of the
customer demand.
If this constraint is not satisfied, then there is a Minimum-Cut and it will
add a constraint to the MIP.protected int[] localSearch(int[] staffing)
staffing
- last solution of the cutting-plane optimization and starting point
of the local search.public int[] getBestStaffing()
StaffingOptimizer
getBestStaffing
in interface StaffingOptimizer
public double getOptimalSL()
getBestStaffing
-1
if not available.public double[] getOptimalSLPerCall()
null
if not available.public double getBestStaffingCost()
StaffingOptimizer
getBestStaffingCost
in interface StaffingOptimizer
public double[] getPerAgentCost()
public double getStaffingCost(int[] staffing)
staffing
- find the total cost of this staffing vector.public boolean exportLP(String filename)
filename
- filename of the exported file.true
if exported without error, else false
.protected void printNumAgents(int[] staffing)
boolean)
with
parameter verbose
.staffing
- the staffing vector to printprotected void printNumAgents(int[] staffing, boolean print)
print
is set to true
.staffing
- the staffing to printprint
- prints only if print
is true
public CuttingPlaneTest getCuttingPlaneTest()
CuttingPlaneTest
instance used for the simulation
and the estimation of the subgradients.CuttingPlaneTest
instancepublic CuttingPlaneParams getCuttingPlaneParams()
CuttingPlaneParams
.protected void ccEval(int[] staffing)
staffing
- the staffing to needsCuts1.protected static boolean equal(double a, double b)
a
- the number to compareb
- the number to be compared withtrue
if they are equalprotected int getMapStaffingIndex(int group)
group
- retrieve the variable index of this groupprotected boolean setMapStaffingIndex(int group, int index)
group
- the group to insert in Mapindex
- the variable index to be associate with this groupprotected int getMapFlowIndex(int type, int group)
type
- the call typegroup
- the agent groupprotected boolean setMapFlowIndex(int type, int group, int index)
type
- the call typegroup
- the agent groupindex
- the index to assign to this variable