LP solver for SCP

jmsallan · Jun 3, 2018 · 0836429 · 0836429
1 parent 2971e4a
commit 0836429
Show file tree

Hide file tree

Showing 5 changed files with 83 additions and 12 deletions.
diff --git a/SCP/bib/mnsc.21.5.591.pdf b/SCP/bib/mnsc.21.5.591.pdf
diff --git a/SCP/readingSCP.R → SCP/code/functionsSCP.R b/SCP/readingSCP.R → SCP/code/functionsSCP.R
@@ -1,7 +1,7 @@
+#---- reading SCP instances ----
 
-url <- "http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/scp42.txt"
-
-
+# set-covering instances from OR-library
+# http://people.brunel.ac.uk/~mastjjb/jeb/orlib/scpinfo.html
 
 # The format of all of these 80 data files is:
 # number of rows (m), number of columns (n)
@@ -51,14 +51,27 @@ readCSP <- function(url){
 return(list(M=M, costs=costs))
 }
 
-url <- "http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/scp42.txt"
-
-paste0("http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/", "scp42", ".txt")
+#---- solving LP with linear programming ----
 
-urls <- lapply(c("scp41", "scp42", "scp43", "scp44", "scp45", "scp46", "scp47", "scp48", "scp49", "scp410"), function(x)  paste0("http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/", x, ".txt"))
-
-allelements <- lapply(urls, readCSP)
-
-save.image("SCPinstances.RData")
+solveLP_SCP <- function(instance){
+
+  obj <- instance$costs
+  mat <- instance$M
+
+  m <- dim(mat)[1]
+  n <- length(obj)
+
+  dir <- rep(">=", m)
+  rhs <- rep(1, m)
+  types <- rep("B", n)
+
+  solution <- Rglpk_solve_LP(obj=obj, mat=mat, dir=dir, rhs=rhs, types=types, max=FALSE)
+
+  optcost <- solution$optimum
+
+  optsolution <- which(solution$solution==1)
+
+  return(list(optcost=optcost, optsolution=optsolution))
+
+}
 
-matricesRDS <- saveRDS(allelements, "SCPinstances.RDS")
diff --git a/SCP/instances/scp41_410instances.RData b/SCP/instances/scp41_410instances.RData
diff --git a/SCP/results/SCPresults.Rdata b/SCP/results/SCPresults.Rdata
diff --git a/SCP/solvingSCPInstances.R b/SCP/solvingSCPInstances.R
@@ -0,0 +1,58 @@
+#set wd
+
+source("code/functionsSCP.R")
+
+#---- reading and solving SCP instances ----
+
+url <- "http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/scp42.txt"
+
+urls41_410 <- lapply(c("scp41", "scp42", "scp43", "scp44", "scp45", "scp46", "scp47", "scp48", "scp49", "scp410"), function(x)  paste0("http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/", x, ".txt"))
+
+Instances41_410 <- lapply(urls41_410, readCSP)
+
+SolutionInstances41_410 <- lapply(Instances41_410, solveLP_SCP)
+
+urls51_510 <- lapply(c("scp51", "scp52", "scp53", "scp54", "scp55", "scp56", "scp57", "scp58", "scp59", "scp510"), function(x)  paste0("http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/", x, ".txt"))
+
+Instances51_510 <- lapply(urls51_510, readCSP)
+
+SolutionInstances51_510 <- lapply(Instances51_510, solveLP_SCP)
+
+urls61_65 <- lapply(c("scp61", "scp62", "scp63", "scp64", "scp65"), function(x)  paste0("http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/", x, ".txt"))
+
+Instances61_65 <- lapply(urls61_65, readCSP)
+
+SolutionInstances61_65 <- lapply(Instances61_65, solveLP_SCP)
+
+urlsa1_a5 <- lapply(c("scpa1", "scpa2", "scpa3", "scpa4", "scpa5"), function(x)  paste0("http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/", x, ".txt"))
+
+Instancesa1_a5 <- lapply(urlsa1_a5, readCSP)
+
+SolutionInstancesa1_a5 <- lapply(Instancesa1_a5, solveLP_SCP)
+
+urlsb1_b5 <- lapply(c("scpb1", "scpb2", "scpb3", "scpb4", "scpb5"), function(x)  paste0("http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/", x, ".txt"))
+
+Instancesb1_b5 <- lapply(urlsb1_b5, readCSP)
+
+SolutionInstancesb1_b5 <- lapply(Instancesb1_b5, solveLP_SCP)
+
+urlsc1_c5 <- lapply(c("scpc1", "scpc2", "scpc3", "scpc4", "scpc5"), function(x)  paste0("http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/", x, ".txt"))
+
+Instancesc1_c5 <- lapply(urlsc1_c5, readCSP)
+
+SolutionInstancesc1_c5 <- lapply(Instancesc1_c5, solveLP_SCP)
+
+urlsd1_d5 <- lapply(c("scpd1", "scpd2", "scpd3", "scpd4", "scpd5"), function(x)  paste0("http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/", x, ".txt"))
+
+Instancesd1_d5 <- lapply(urlsd1_d5, readCSP)
+
+SolutionInstancesd1_d5 <- lapply(Instancesd1_d5, solveLP_SCP)
+
+urlse1_e5 <- lapply(c("scpe1", "scpe2", "scpe3", "scpe4", "scpe5"), function(x)  paste0("http://people.brunel.ac.uk/~mastjjb/jeb/orlib/files/", x, ".txt"))
+
+Instancese1_e5 <- lapply(urlse1_e5, readCSP)
+
+SolutionInstancese1_e5 <- lapply(Instancese1_e5, solveLP_SCP)
+
+
+save.image("results/SCPresults.Rdata")