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.

josliber · Accepted Answer · 2015-08-03 20:16:49Z

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.

Thanks for the help! My follow up questions are how might I limit the number of Programs in "mod" Let's say I want to restrict the number of Offices to <= 1? Also, how difficult would it be for me to allow multiple programs in the same room so long as the combinations are still less than the maximum sf?
@medavis6 If you have follow-on questions, in general it's best to use the "Ask Question" button to ask a new question, showing the code you have so far, your attempts at answering the question yourself, and where you're getting stuck. This helps each question stay focused and prevents questions and answers from getting very large. Both of the constraints you mention can certainly be added to the integer program.

Collectives™ on Stack Overflow

Optimization with Multiple Constraints in R

1 Answer 1

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Related