Solve optimization with binary variables

Question

I'm trying to optimize the following: people (column id) should go to one of the points A:G. Let's say that exactly two people (from a group of 14) must go to one of the 7 locations. I want to minimize the sum of the distances covered.

id <- 1:14
A  <- c(9.37,4.45,4.42,2.90,3.44,5.46,5.96,5.91,5.74,9.74,8.35,1.46,8.87,9.37)
B  <- c(8.36,3.28,3.27,1.16,2.34,3.73,4.22,4.27,4.06,8.99,7.33,0.41,8.28,9.06)
C  <- c(7.29,6.98,6.97,4.26,6.04,6.58,7.04,5.99,5.98,7.20,6.37,3.82,6.17,6.36)
D  <- c(6.07,5.16,5.17,2.14,4.41,3.97,4.40,3.30,3.27,6.62,5.04,2.75,5.91,6.76)
E  <- c(6.32,5.03,5.03,2.02,4.25,4.00,4.45,3.46,3.41,6.85,5.30,2.52,6.12,6.94)
F  <- c(4.54,6.54,6.56,3.57,5.89,4.71,5.05,3.38,3.50,5.03,3.52,4.34,4.34,5.32)
G  <- c(3.96,8.86,8.88,5.85,8.14,7.08,7.39,5.56,5.74,3.59,3.25,6.33,2.55,3.05)
dataset <- data.frame(id,A,B,C,D,E,F,G)

I thought of writing a linear programming problem with binary variables.

Is it possible to solve in R?

Marcelo Rodrigues · Accepted Answer · 2020-07-14 00:01:23Z

1

I found a solution. Just for the record (if useful to someone). It is necessary to add equations with the restrictions that each person would go to a single point

k<-14
coef <- matrix(nrow = 0, ncol = k*7)
coef <- data.frame(coef)
for (i in 1:7) {
  aux <- c(rep(0,k*(i-1)),rep(1,k),rep(0,k*(7-i)))
  coef[nrow(coef)+1,] <- aux
}
aux <- rep(0,14*7)
for (i in 1:k){
  aux2 <- aux
  for (j in 1:7){
    aux2[(j-1)*k+i] <- 1
  }
   dd[nrow(dd)+1,] <- aux2 
}
coef <- as.matrix(coef)
coef <- t(coef) 


library(lpSolve)
a <- lp (direction = "min", c(dataset$A[1:k],dataset$B[1:k],dataset$C[1:k],
     dataset$D[1:k],dataset$E[1:k],dataset$F[1:k],dataset$G[1:k]), coef, 
     c(rep("==",21), c(rep(2,7),rep(1,k)),
     transpose.constraints = FALSE, presolve=0, compute.sens=0,
     all.bin=TRUE, scale = 196,
     num.bin.solns=1, use.rw=FALSE)

edited Jul 14, 2020 at 0:01

answered Jul 13, 2020 at 22:12

Marcelo Rodrigues

2591 silver badge9 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

shadowtalker Over a year ago

We encourage self-answers like this, so thank you! Use the checkmark on the left to mark it as "accepted".

Collectives™ on Stack Overflow

Solve optimization with binary variables

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related