Meaning of imbalanceTolerance

[Bernd Welter]

One of my customers asked me about the handling of "imbalanceTolerance". He played with different combinations of imbalanceTolerance and ignoreImbalanceTolerance. While one of the combinations provided a good solution in terms of "all assigned territories total activities have almost equal values" the other results seem to provide an equal, poor level of balancing.

Trivial assignment. Each customer is assigned to the closest input territory center. The activities of this result are between 80.4% and 131.9% of the target.

Getting same responses every time with below combination:
1. imbalanceTolerance=10,50&10 and ignoreImabalanceTolerance=false
2. ignoreImbalanceTolerance=true

But getting different response with combination imbalanceTolerance=0 and ignoreImabalanceTolerance=false.

Please let me know, why similar response is generated with above mentioned combinations? I am expecting different responses with different tolerance values.

Let me explain this... As you might know the clustrering tries to satisfy two conflicting goals:

• create geographic compact territories
• assign each territory an equal workload

I start with a definition:

Target activity: the average activity which satisfies the second goal in a perfect way. Simply the sum of all activities divided by the number of output clusters, e.g. the total activity is 10'000 and you want to create 5 clusters. TargetActivity is then 2'000.

So if you activate a specific tolerance T% (e.g.5%) we determine the target activity and derive thresholds for a potential solution:

• MinActivity := TargetActivity * (1 - T%), e.g. 2'000 * 0.95 = 1'900
• MaxActivity := TargetActivity * (1 + T%), e.g. 2'000 * 1.05 = 2'100

In this example all assignments which create clusters with clusterActivity between 1'900 and 2'100 are "valid" in terms of the second goal.

Now the next question is:

Why do the various tolerances in the customers example return same solutions?

For this you need to understand the iteration under the roof.

Trivial assignment: each customer is simply assigned to the closest cluster center.

This is how we create a kickof "condition" which we would try to improve if it violates the imbalanceTolerance.

• In the customers example the Trivial assignment satisfies all the imbalance tolerances [100%,50%, 10%] so there's no need to improve the trivial assignment.
• By setting the imbalanceTolerance to 0% the trivial assignment is no longer sufficient.

That's it.
Bernd

Appendix:
There's no such a call as "find me the best tolerance" in a single step. If you want to go for it you can apply a client logic based on one of the following approaches:

Stragegy 1: start with a low value of imbalance tolerance (e.g.0) - as long as this creates "no valid solution found" increase it step by step

Strategy 2 : start with a trivial tolerance and reduce it until you run into the "no valid solution found". The las successful solution is what you are looking for

By setting the tolerance to 30% (just a little below the deviation of the "trivial assignment" I push towards "iteration". The result is now between 80% and 130%

By setting the tolerance to 0% I really push towards the equality (risk of "no valid solution found")

[Bernd Welter]

Here's a follow-up question:

Does this mean that

• (ignoreImbalanceTolerance=true)
• (ignoreImbalanceTolerance=false) && (imbalanceTolerance=100)

return equal results?

Short answer: Nope. Let's look into the following example, again based on a total activity of 10'000.

Scenarios		Various tolerances
#clusters	target activity	min/max : 10	min/max : 50	min/max : 100	min/max : 200 (=illegal!)
2	5'000	4'500 to 5'500	2'500 to 7'500	0 to 10'000	-5'000 to 15'000
3	3'333	3'000 to 3'666	1'500 to 4'500	0 to 6'666	-3'333 to 10'000
4	2'500	2'250 to 2'750	1'250 to 3'750	0 to 5'000	-2'500 to 7'500
5	2'000	1'800 to 2'200	1'000 to 3'000	0 to 4'000	-2'000 to 6'000

So with a balanceTolerance of 100 only the #clusters==2 guarantees that any starting solution will terminate immediately.
In other words: "What imbalanceTolerance is equal to ignoreImpanceTolerance== true?" depends on the number of target clusters!
Now the value reange for the imbalanceTolerance is restricted to be <=100.
Here are some examples / edge cases based on "all orders are located in the area of cluster 1 and the total activity is 2'871":

ignoreImbalanceTolerance==true : all orders are assigned to the cluster 1 and stay within this cluster"

As the number of clusters is 3 the allowed range for a cluster is 0 to 957x2 = 1'914: so assigning all activity to one single cluster is not valid as this would overload that cluster.