Intuitively, we can see that a task correlation of 1 and a machine correlation of 0 is equivalent to the Q|pi=p|Cmax problem. In this case, the matrix contains n times the same row. The machine correlation is thus 0 and the task correlation is 1. With instances of this kind, most heuristics should be optimal. We would like to check this. Additionally, they could remains efficient even if the correlations are not perfectly 1 and 0. Preliminary data show that this is not the case. We will first see whether the generated instances are far from Q|pi=p|Cmax instances and whether this distance impact the optimality.
Let's generate Q|pi=p|Cmax instances:
n <- 10
m <- 4
CV <- 0.1
(Z <- generate_uniform_identical_matrix(n, m, 1, CV))
## [,1] [,2] [,3] [,4]
## [1,] 1.125 0.9627 0.9134 1.037
## [2,] 1.125 0.9627 0.9134 1.037
## [3,] 1.125 0.9627 0.9134 1.037
## [4,] 1.125 0.9627 0.9134 1.037
## [5,] 1.125 0.9627 0.9134 1.037
## [6,] 1.125 0.9627 0.9134 1.037
## [7,] 1.125 0.9627 0.9134 1.037
## [8,] 1.125 0.9627 0.9134 1.037
## [9,] 1.125 0.9627 0.9134 1.037
## [10,] 1.125 0.9627 0.9134 1.037
Let's see the distance from such instances when controlling the correlations:
Z1 <- generate_matrix_corr_positive(n, m, rgamma_cost, 1, CV, 0.99, 0)
Z2 <- generate_heterogeneous_matrix_noise_corr(n, m, rgamma_cost, 0.99, 0, CV)
distance_uniform_identical(Z1)
## [1] 0.007791
distance_uniform_identical(Z2)
## [1] 0.008007
Now, let's see how this distance is impacted by the task correlation:
n <- 100
m <- 30
CV <- 0.1
distance_corr_pos <- NULL
for (i in 1:1000) {
corr_comp <- runif(1, 0, 1)
Z <- generate_matrix_corr_positive(n, m, rgamma_cost, 1, CV, 1 - corr_comp,
0)
distance_corr_pos <- rbind(distance_corr_pos, data.frame(corr_comp = corr_comp,
dis = distance_uniform_identical(Z)))
}
library(ggplot2)
p <- ggplot(data = distance_corr_pos, aes(x = corr_comp, y = dis))
p <- p + geom_point() + geom_smooth()
p
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
This is interesting: the closeness is regular (the closer to 1, the closer the instance to a Q|pi=p|Cmax instance). We should probably replace 1 (unreachable) by 1-eps (with eps=1e-3) in the experiments or over-sample values close to 1.
Let's see if the same is true for the second generation method:
n <- 100
m <- 30
CV <- 0.1
distance_noise_corr <- NULL
for (i in 1:1000) {
corr_comp <- runif(1, 0, 1)
Z <- generate_heterogeneous_matrix_noise_corr(n, m, rgamma_cost, 1 - corr_comp,
0, CV)
distance_noise_corr <- rbind(distance_noise_corr, data.frame(corr_comp = corr_comp,
dis = distance_uniform_identical(Z)))
}
library(ggplot2)
p <- ggplot(data = distance_noise_corr, aes(x = corr_comp, y = dis))
p <- p + geom_point() + geom_smooth()
p
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
The method behaves abnormally when the correlation is below 0.5. This corresponds to the transition for fixing Vnoise. This method should problably be used carefully and double-checked (experimentally and formally).
Let's consider a given Q|pi=p|Cmax instance and let's try each heuristic on it:
n <- 100
m <- 30
CV <- 0.1
var_heur <- NULL
for (i in 1:10) {
Z <- generate_uniform_identical_matrix(n, m, 1, CV)
mks <- c(MCT(Z), MinMin(Z), MaxMin(Z), EFT(Z), LPT_unrelated(Z), classic_sufferage(Z),
greedy_Suff(Z), balance_sufferage(Z), balance_EFT(Z))
var_heur <- c(var_heur, var(mks))
}
summary(var_heur)
## Min. 1st Qu. Median Mean 3rd Qu. Max.
## 0 0 0 0 0 0
OK, all heuristics are optimal (empirical evidence). Now, let's see how this degrades for each heuristic depending on the distance from this case:
n <- 30
m <- 10
CV <- 0.1
degradation <- NULL
for (i in 1:1000) {
comp_corr <- 10^runif(1, -2, 0)
Z <- generate_matrix_corr_positive(n, m, rgamma_cost, 1, CV, 1 - comp_corr,
0)
mks <- rbind(data.frame(ratio = MaxMin(Z), algo = "MaxMin"), data.frame(ratio = MCT(Z),
algo = "MCT"), data.frame(ratio = greedy_Suff(Z), algo = "greedy_Suff"),
data.frame(ratio = LPT_unrelated(Z), algo = "LPT_unrelated"), data.frame(ratio = EFT(Z),
algo = "EFT"), data.frame(ratio = classic_sufferage(Z), algo = "classic_sufferage"),
data.frame(ratio = balance_EFT(Z), algo = "balance_EFT"), data.frame(ratio = balance_sufferage(Z),
algo = "balance_sufferage"))
degradation <- rbind(degradation, data.frame(comp_corr = comp_corr, ratio = mks$ratio/min(mks$ratio),
algo = mks$algo))
}
library(ggplot2)
p <- ggplot(data = degradation, aes(x = comp_corr, y = ratio))
p <- p + geom_point(size = 1) + geom_smooth()
p <- p + scale_x_log10()
p <- p + facet_wrap(~algo)
p
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
OK, all these results are actually consistent and they fit preliminary observed data. The real question is whether we will get similar results when we fix the task correlation to a value close to 1 while increasing machine correlation.
n <- 30
m <- 10
CV <- 0.1
degradation <- NULL
for (i in 1:1000) {
corr <- 10^runif(1, -2, 0)
Z <- generate_matrix_corr_positive(n, m, rgamma_cost, 1, CV, 0.9999, corr)
mks <- rbind(data.frame(ratio = MaxMin(Z), algo = "MaxMin"), data.frame(ratio = MCT(Z),
algo = "MCT"), data.frame(ratio = greedy_Suff(Z), algo = "greedy_Suff"),
data.frame(ratio = LPT_unrelated(Z), algo = "LPT_unrelated"), data.frame(ratio = EFT(Z),
algo = "EFT"), data.frame(ratio = classic_sufferage(Z), algo = "classic_sufferage"),
data.frame(ratio = balance_EFT(Z), algo = "balance_EFT"), data.frame(ratio = balance_sufferage(Z),
algo = "balance_sufferage"))
degradation <- rbind(degradation, data.frame(corr = corr, ratio = mks$ratio/min(mks$ratio),
algo = mks$algo))
}
library(ggplot2)
p <- ggplot(data = degradation, aes(x = corr, y = ratio))
p <- p + geom_point(size = 1) + geom_smooth()
p <- p + scale_x_log10()
p <- p + facet_wrap(~algo)
p
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
The performance remains quite constant except when it starts from a high value (MaxMin and HLPT) in which case the performance increases as the machine correlation increases (except for EFT). Let's confirm this with a lesser task correlation:
n <- 30
m <- 10
CV <- 0.1
degradation <- NULL
for (i in 1:1000) {
corr <- 10^runif(1, -2, 0)
Z <- generate_matrix_corr_positive(n, m, rgamma_cost, 1, CV, 0.9, corr)
mks <- rbind(data.frame(ratio = MaxMin(Z), algo = "MaxMin"), data.frame(ratio = MCT(Z),
algo = "MCT"), data.frame(ratio = greedy_Suff(Z), algo = "greedy_Suff"),
data.frame(ratio = LPT_unrelated(Z), algo = "LPT_unrelated"), data.frame(ratio = EFT(Z),
algo = "EFT"), data.frame(ratio = classic_sufferage(Z), algo = "classic_sufferage"),
data.frame(ratio = balance_EFT(Z), algo = "balance_EFT"), data.frame(ratio = balance_sufferage(Z),
algo = "balance_sufferage"))
degradation <- rbind(degradation, data.frame(corr = corr, ratio = mks$ratio/min(mks$ratio),
algo = mks$algo))
}
library(ggplot2)
p <- ggplot(data = degradation, aes(x = corr, y = ratio))
p <- p + geom_point(size = 1) + geom_smooth()
p <- p + scale_x_log10()
p <- p + facet_wrap(~algo)
p
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
## geom_smooth: method="auto" and size of largest group is >=1000, so using gam with formula: y ~ s(x, bs = "cs"). Use 'method = x' to change the smoothing method.
MaxMin is particularly affected (even more than HLPT). They are probably both equivalent when both correlations are 1. Having a low machine correlation means tasks do not have a relevant weight. That is why HLPT cannot sort tasks with a good relevance. The impact on MaxMin is less clear.
The effect of the correlations is quite intuitive: the left bottom corner corresponds to Q|pi=p|Cmax instances for which all heuristics are optimal.
The values close to 1 may be higly relevant. It could be relevant to use a log scale on the complement correlations.
It is still necessary to check the behavior of the noise-based generation method: there is a inflexion point when the correlation is 0.5.