Repository of scripts used by IRIDIA members

From IridiaWiki
Jump to navigationJump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Max's scripts

When testing different algorithms on some combinatorial optimization problem, I usually organize the data on my machine according to a same schema. Basically I create the following structure of directories to store sources, problem instances, output data, executables and scripts.

+ main_project_folder
|
|-+ bin   (contains the executables of the algorithms)
|
|-+ instances   (contains the problem instances)
|
|-+ out   (contains the outputs of the trial)
|
|-+ sh   (contains the script to launch the experiments)
|
|-+ src   (contains the sources of the algorithms)
|
|-+ analysis    (contains the R script to boxplot the experimental data)


Boxplot of solution values by algorithm

Tai100a 1000.png

I organize the data in the following way:

in the file optimal_values.txt I put the best-known solution values for the problem instances I'm testing

instance   optimum 
sko100a    152002 
sko100e    149150 
tai100a    21059006 
tai100b    1185996137 


in the files algorithms.txt I put the algorithms details

idalgo          topo    schema  ls      type    number_of_cpus
PIR-2opt        PIR     PIR     2       Par     2
PIR-ts          PIR     PIR     3       Par     2
SEQ-2opt        SEQ     SEQ     2       Par     2
SEQ-ts          SEQ     SEQ     3       Par     2
SEQ2-2opt       SEQ     SEQ     2       Par     2
SEQ2-ts         SEQ     SEQ     3       Par     2
HC.1.x.10-2opt  HC      1.x.10  2       Par     2
HC.2.6.10-2opt  HC      2.6.10  2       Par     2
HC.2.7.10-2opt  HC      2.7.10  2       Par     2


in the files algorithm_factors_instance-size_cut-time.txt I record the history of the search of the algo for the instance

idalgo          cpu_id  instance        try     best    time    iteration
HC.1.x.10-2opt  0       sko100a         1       155254  0.35    1
HC.1.x.10-2opt  0       sko100a         1       154162  0.35    1
HC.1.x.10-2opt  0       sko100a         1       154050  0.35    1
HC.1.x.10-2opt  0       sko100a         1       153684  2.69    8
HC.1.x.10-2opt  0       sko100a         1       153508  3.24    10
HC.1.x.10-2opt  0       sko100a         1       153396  3.24    10
HC.1.x.10-2opt  0       sko100a         1       153344  3.24    10
HC.1.x.10-2opt  0       sko100a         1       153092  3.52    11
HC.1.x.10-2opt  0       sko100a         1       153062  3.75    12

In order to produce boxplots like the one above you can look at the R source used to produce it.


optimal_values<-read.table("optimal_values.txt",header=TRUE)

resPIR2OPT<-read.table("parallel_independent_2-opt_100_1000.txt",header=TRUE)
resSEQ2OPT<-read.table("sequential_2-opt_100_2000.txt",header=TRUE)
resSEQ22OPT<-read.table("sequential2_2-opt_100_1000.txt",header=TRUE)
resHC1x102OPT<-read.table("hc.1.x.10_2-opt_100_1000.txt",header=TRUE)
resHC26102OPT<-read.table("hc.2.6.10_2-opt_100_1000.txt",header=TRUE)
resHC27102OPT<-read.table("hc.2.7.10_2-opt_100_1000.txt",header=TRUE)
resHC28102OPT<-read.table("hc.2.8.10_2-opt_100_1000.txt",header=TRUE)
resHC29102OPT<-read.table("hc.2.9.10_2-opt_100_1000.txt",header=TRUE)
resHC36102OPT<-read.table("hc.3.6.10_2-opt_100_1000.txt",header=TRUE)
resHC37102OPT<-read.table("hc.3.7.10_2-opt_100_1000.txt",header=TRUE)
resHC38102OPT<-read.table("hc.3.8.10_2-opt_100_1000.txt",header=TRUE)
resHC39102OPT<-read.table("hc.3.9.10_2-opt_100_1000.txt",header=TRUE)
resRW1x102OPT<-read.table("rw.1.x.10_2-opt_100_1000.txt",header=TRUE)
resRW26102OPT<-read.table("rw.2.6.10_2-opt_100_1000.txt",header=TRUE)
resRW27102OPT<-read.table("rw.2.7.10_2-opt_100_1000.txt",header=TRUE)
resRW28102OPT<-read.table("rw.2.8.10_2-opt_100_1000.txt",header=TRUE)
resRW29102OPT<-read.table("rw.2.9.10_2-opt_100_1000.txt",header=TRUE)
resRW36102OPT<-read.table("rw.3.6.10_2-opt_100_1000.txt",header=TRUE)
resRW37102OPT<-read.table("rw.3.7.10_2-opt_100_1000.txt",header=TRUE)
resRW38102OPT<-read.table("rw.3.8.10_2-opt_100_1000.txt",header=TRUE)
resRW39102OPT<-read.table("rw.3.9.10_2-opt_100_1000.txt",header=TRUE)

res<-rbind(resRW1x102OPT,resRW26102OPT,resRW27102OPT,resRW28102OPT,resRW29102OPT,
resRW36102OPT,resRW37102OPT,resRW38102OPT,resRW39102OPT,resHC1x102OPT,resHC26102OPT,
resHC27102OPT,resHC28102OPT,resHC29102OPT,resHC36102OPT,resHC37102OPT,resHC38102OPT,
resHC39102OPT,resPIR2OPT,resSEQ2OPT,resSEQ22OPT)


linstance<-levels(res$instance)

res.split<-split(1:nrow(res), list(res$instance, res$try, res$idalgo), drop=TRUE)

min.list <- lapply(res.split, function(x){
        x[match(min(res$best[x]), res$best[x])]
        })

# matches return the first among all the values with min best!!!
# so is not the one with minimal time

min.vector <- unlist(min.list)

bestalgo<-res[min.vector,]

bestalgo.split <- split(1:nrow(bestalgo), bestalgo$instance, drop=TRUE)

for (i in (1:length(bestalgo.split)))
{
        bestalgo.vector <- unlist(bestalgo.split[i])
        bestalgo.temp <- bestalgo[bestalgo.vector,]
        l<-split(as.double(bestalgo.temp$best),bestalgo.temp$idalgo)

        epsfile=paste(linstance[i],"_1000.eps",sep="")
        postscript(file=epsfile,onefile=TRUE,horizontal=TRUE)
        par(mar=c(5,5,5,3),cex.axis=0.7,las=2,mgp=c(4, 1, 0))
        title_plot=paste("2 CPU - 1000 iterations - instance ",linstance[i],sep="")
        boxplot(l,xlab="",ylab="solution value",names=c(levels(bestalgo$idalgo)),main=title_plot,
yaxt="n",ylim=c(min(min(bestalgo.temp$best),optimal_values[optimal_values$instance==linstance[i],]$optimum),
max(bestalgo.temp$best)))
        axis(2, seq(from=min(min(bestalgo.temp$best),optimal_values[optimal_values$instance==linstance[i],]$optimum),
to=max(bestalgo.temp$best),length.out=10))
        abline(h=optimal_values[optimal_values$instance==linstance[i],]$optimum)
        grid(nx=0, ny=55,col="gray5")
        dev.off()
}