Let’s find the smallest exemple requiring one more iteration than necessary.

costs <- replicate(3, { rgamma(n = 3, shape = 1, scale = 1) })
while(alloc_max_cycle(costs)$iter <= 4) {
  costs <- replicate(3, { rgamma(n = 3, shape = 1, scale = 1) })
}
costs
##           [,1]      [,2]      [,3]
## [1,] 0.2588334 0.4270844 0.5694931
## [2,] 0.3976671 1.7184487 2.0945935
## [3,] 0.8398360 2.4316668 0.3972361

Let’s simplify this instance with rounded values:

costs <- rbind(c(1, 1-1e-5, 2), c(1, 2, 2), c(2-1e-5, 2, 1))
alloc_max_cycle(costs)$iter
## [1] 6

This is an even better example with 6 iterations whereas we would like only 4. Let’s consider an ideal initial iteration at first where task 1 will go from proc 1 to proc 2 (in exchange for task 2) and task 3 will go from proc 2 to proc 3 (in exchange for task 2).

I1 : m4*c41-m1*c11;
I2 : m1*c12+m3*c32-m2*c22-m4*c42;
I3 : m2*c23-m3*c33;
solve([I1 - I2, I2 - I3], [m1, m2]);
solve([I1 - I2, I2 - I3], [m1, m3]);
solve([I1 - I2, I2 - I3], [m1, m4]);
solve([I1 - I2, I2 - I3], [m2, m3]);
solve([I1 - I2, I2 - I3], [m2, m4]);
solve([I1 - I2, I2 - I3], [m3, m4]);

This is becoming increasingly complex. Moreover, we have an alternative that consists in running a simple LP with any very efficient solver. Finally, it is not sure that the number of iterations with this new approach could be bounded.

We give up on this direction.

## R version 3.3.3 (2017-03-06)
## Platform: x86_64-pc-linux-gnu (64-bit)
## Running under: Ubuntu 16.04.2 LTS
## 
## locale:
##  [1] LC_CTYPE=fr_FR.UTF-8       LC_NUMERIC=C              
##  [3] LC_TIME=fr_FR.UTF-8        LC_COLLATE=fr_FR.UTF-8    
##  [5] LC_MONETARY=fr_FR.UTF-8    LC_MESSAGES=fr_FR.UTF-8   
##  [7] LC_PAPER=fr_FR.UTF-8       LC_NAME=C                 
##  [9] LC_ADDRESS=C               LC_TELEPHONE=C            
## [11] LC_MEASUREMENT=fr_FR.UTF-8 LC_IDENTIFICATION=C       
## 
## attached base packages:
## [1] stats     graphics  grDevices utils     datasets  methods   base     
## 
## other attached packages:
## [1] ggplot2_2.1.0 dplyr_0.5.0   tidyr_0.2.0   purrr_0.2.0  
## 
## loaded via a namespace (and not attached):
##  [1] Rcpp_0.12.9      digest_0.6.9     assertthat_0.1   plyr_1.8.1      
##  [5] grid_3.3.3       R6_2.1.2         gtable_0.1.2     DBI_0.6         
##  [9] pacman_0.4.1     formatR_1.4      magrittr_1.5     scales_0.4.0    
## [13] evaluate_0.10    stringi_0.5-5    lazyeval_0.1.10  rmarkdown_1.1   
## [17] tools_3.3.3      stringr_1.0.0    munsell_0.4      yaml_2.1.13     
## [21] colorspace_1.2-2 htmltools_0.3.5  knitr_1.14       tibble_1.2