Optimization with Multiple Constraints in R

Question

I have a question about optimizing program use across multiple rooms in a building using a couple constraints. My question is how can I ask for the optimum program in all 4 classrooms based on the data and constraints at the same time?

The following is a small sample of my data.

Program                 sf    101   201 301 401 
(1) Offices             120    6     6   5   5
(2) Gallery             1000   5     5   4   4
(3) Reception / Greeter 300    6     6   5   7
(4) Studio / Classroom  800    6     6   5   5

101, 201, 301, and 401 represent 4 rooms in a building.
Program is the potential room use.
sf represents the maximum square feet of the intended program (one constraint).
The data represents how many criteria the intended program matches with attributes of each room (this is the number I want to maximize).

I would also like to place constraints that would allow me to say I only want a certain number of Offices, Galleries, etc. in the building.

e.g., I want 1 Reception/Greeter and 2 Offices, and the last room can be filled by best available matches. Room 101 has a maximum sf of 150, Room 201 has a maximum sf of 250 sf, Room 301 has a maximum sf of 1500, and Room 401 has a maximum sf of 500 (these constraints are not in my data frame because I couldn't think of a good way to do include them).
This example should return 101 = Offices, 201 = Offices, 301 = one of the three excluding Gallery, and 401 = Reception / Greeter.

---

Update: Objective should be something like this (I want them all maximized):

obj <- data$101, data$201, data$301, data$401 (and probably data$sf too) 

Then I'm not really sure how to write the constraints but they would be this:

data$101
data$sf <= 150
number of solutions from this column should be 1

data$201
data$sf <= 250
number of solutions from this column should be 1

...

data$401
data$sf <= 500
number of solutions from this column should be 1

And then finally somehow restrict the number of "Offices", "Gallery", "Reception / Greeter", "Studio / Classroom".

Maybe something like:

as.numeric(data$Program %in% c("(1) Offices") == 1

Hopefully this clarifies some things.

Answer 1

It sounds like you are assigning programs (rows in data) to rooms (columns in data) such that you maximize the value of the assignment. You can only assign a program to a room if the room is big enough and you can only assign one program to a room, though the same program can be assigned to multiple rooms (e.g. you could assign "Office" to both room 101 and 201). Therefore, your data really consists of program sizes, room sizes, and objective values:

program.size <- c(120, 1000, 300, 800)
room.size <- c(150, 250, 1500, 500)
(obj.vals <- matrix(c(6, 5, 6, 6, 6, 5, 6, 6, 5, 4, 5, 5, 5, 4, 7, 5), nrow=4))
#      [,1] [,2] [,3] [,4]
# [1,]    6    6    5    5
# [2,]    5    5    4    4
# [3,]    6    6    5    7
# [4,]    6    6    5    5

A simple way to block assigning a program to a room that is too small would be to set the objective value for such an assignment to a low value (I'll use 0 here):

(obj.adj <- obj.vals * outer(program.size, room.size, "<="))
#      [,1] [,2] [,3] [,4]
# [1,]    6    6    5    5
# [2,]    0    0    4    0
# [3,]    0    0    5    7
# [4,]    0    0    5    0

Now, you can approach this problem using integer programming, defining a variable x_pr that takes value 1 if program p is assigned to room r and 0 otherwise. You can code up the objective and constraints pretty easily using the lpSolve package in R:

# Convenience variables
nr <- nrow(obj.adj)
nc <- ncol(obj.adj)

# Model
library(lpSolve)
mod <- lp("max",
          as.vector(obj.adj),
          t(1*sapply(1:nc, function(x) rep(1:nc == x, each=nr))),
          rep("<=", nc),
          rep(1, nc),
          all.bin=TRUE)
matrix(mod$solution, nrow=nr)
#      [,1] [,2] [,3] [,4]
# [1,]    1    1    0    0
# [2,]    0    0    0    0
# [3,]    0    0    0    1
# [4,]    0    0    1    0

Now we've assigned "Office" to rooms 101 and 201, "Studio/Classroom" to room 301, and "Reception/Greeter" to room 401.

It's worth noting that this program could easily be solved by selecting the program with the largest value for each room in obj.adj, so the use of lpSolve is only warranted if you have more complicated constraints than the ones mentioned in the question.