具有字符和列总和约束的 R 中的 lpSolve
lpSolve in R with Character and Column Sum Contraints
我有一个房间列表、房间的最大平方英尺、程序、程序的最大平方英尺以及房间与预期程序用途匹配（匹配#）的值。在帮助下，我已经能够最大限度地利用每个房间的一个程序使用 match # 和平方英尺。但是，我想将此分析更进一步，允许在同一个房间中使用多个程序，或者如果具有最高匹配 #，则允许同一程序的多个程序，只要多个程序仍然符合平方英尺要求。此外，我想总体上告诉 lpSolve，我只想要 "x" 数量的办公室，"y" 数量的工作室，等等。到目前为止，这是我的数据和代码：
program.size <- c(120,320,300,800,500,1000,500,1000,1500,400,1500,2000)
room.size <- c(1414,682,1484,2938,1985,1493,427,1958,708,581,1485,652,727,2556,1634,187,2174,205,1070,2165,1680,1449,1441,2289,986,298,590,2925)
(obj.vals <- matrix(c(3,4,2,8,3,7,4,8,6,4,7,7,
3,4,2,8,3,7,4,8,6,4,7,7,
4,5,3,7,4,6,5,7,5,3,6,6,
2,3,1,7,2,6,3,7,7,5,6,6,
4,5,3,7,4,6,5,7,5,3,6,6,
3,6,4,8,5,7,4,8,7,7,7,7,
3,4,2,8,3,7,4,8,6,4,7,7,
4,5,3,7,4,6,5,7,5,3,6,6,
6,7,5,7,6,6,7,7,5,3,6,6,
6,7,5,7,6,6,7,7,5,3,6,6,
5,6,6,6,5,7,8,6,4,2,5,5,
6,7,5,7,6,6,7,7,5,3,6,6,
6,7,5,7,6,6,7,7,5,3,6,6,
3,4,4,8,3,9,6,8,6,4,7,7,
3,4,2,6,3,5,4,6,6,4,5,5,
4,5,3,5,4,4,5,5,5,3,4,4,
5,6,4,8,5,7,6,8,6,4,7,7,
5,6,4,8,5,7,6,8,6,4,7,7,
4,5,5,7,4,8,7,7,5,3,6,6,
5,6,4,8,5,7,6,8,6,4,7,7,
3,4,2,6,3,5,4,6,6,4,5,5,
5,6,4,8,5,7,6,8,6,4,7,7,
5,6,4,8,5,7,6,8,6,4,7,7,
5,4,4,6,5,5,6,6,6,6,7,5,
6,5,5,5,6,4,5,5,5,7,6,4,
4,5,3,7,4,6,5,7,7,5,6,6,
6,5,5,5,6,4,5,5,5,7,6,4,
3,4,4,6,3,7,6,6,6,4,5,5), nrow=12))
rownames(obj.vals) <- c("Enclosed Offices", "Open Office", "Reception / Greeter", "Studio / Classroom",
"Conference / Meeting Room", "Gallery", "Public / Lobby / Waiting",
"Collaborative Space", "Mechanical / Support", "Storage / Archives",
"Fabrication", "Performance")
(obj.adj <- obj.vals * outer(program.size, room.size, "<="))
nr <- nrow(obj.adj)
nc <- ncol(obj.adj)
library(lpSolve)
obj <- as.vector(obj.adj)
con <- t(1*sapply(1:nc, function(x) rep(1:nc == x, each=nr)))
dir <- rep("<=", nc)
rhs <- rep(1, nc)
mod <- lp("max", obj, con, dir, rhs, all.bin=TRUE)
final <- matrix(mod$solution, nrow=nr)
所以现在我的问题是如何让求解器最大限度地使用平方英尺并在每个房间（列）内匹配 # 并允许多个相同的程序或程序的组合来完成此操作？我知道我必须解除 "mod" 中的“<= 1”限制，但我无法弄清楚如何让它在每个房间中找到最合适的，然后最终，整体。
房间[1]的解决方案是：
$optimum
33
并且它将尝试在房间内安装 11 个封闭办公室，其最佳匹配度比 1 个协作 Space（8 个匹配）和 1 个存储/档案室（4 个匹配）总得分高得多共 12 场比赛。
因此这引出了我的下一个问题，即限制我的解决方案矩阵中某些程序的总数。我假设它会包括某种
as.numeric(data$EnclosedOffices "<=" 5)
但我也不知道如何限制它。这些数字对于所有程序都是不同的。
感谢您提供的所有帮助，如有任何疑问，请随时提出要求。
更新：
约束
- 最大化每个房间的匹配 # (obj.vals)。
- 最大化每个 room.size 平方内的 program.size 平方英尺
脚。通过多次使用相同的程序（5 x
封闭式办公室）或组合程序（1 协作 Space 和
1 性能）。
- 限制and/or强制返回程序数
解决方案。只要不超过我在所有房间中为该节目提供的最大数量，节目就可以在房间之间分开。 （在所有 28 列中只能选择 5 个封闭办公室、8 个 Studios/Classrooms、1 个制造等。
如果您使用 R 包 lpSolveAPI（lpSolve 的包装器），那么它会变得更容易一些。
首先，看一下数学公式（整数程序），然后我会向您展示解决问题的代码。
公式
设 X_r_p 为取正整数值的决策变量。
X_r_p = 分配给房间 r 的类型 p 的程序数
（在你所有的问题中将有 28*12=336 个决策变量）
Objective函数
最大化匹配分数
Max sum(r) sum(p) C_r_p * X_r_p #这里C_r_p是将p分配到房间r的分数
以
为准
房间面积限制约束
Sum(p) Max_area_p * X_r_p <= Room Size (r) for each room r
（我们会有28个这样的约束）
限制节目数量Constraint
Sum(r) X_r_p <= Max_allowable(p) for each program p
（我们会有12个这样的约束）
X_r_p >= 0, Integer
总的来说就是这样。 336 列和 40 行。
在 R 中实现
这是 R 中的一个实现，使用 lpSolveAPI。
注意：由于 OP 没有在建筑物中提供 max_allowable 程序，因此我为 max_programs.
生成了自己的数据
program.size <- c(120,320,300,800,500,1000,500,1000,1500,400,1500,2000)
room.size <- c(1414,682,1484,2938,1985,1493,427,1958,708,581,1485,652,727,2556,1634,187,2174,205,1070,2165,1680,1449,1441,2289,986,298,590,2925)
(obj.vals <- matrix(c(3,4,2,8,3,7,4,8,6,4,7,7,3,4,2,8,3,7,4,8,6,4,7,7,
4,5,3,7,4,6,5,7,5,3,6,6,2,3,1,7,2,6,3,7,7,5,6,6, 4,5,3,7,4,6,5,7,5,3,6,6,
3,6,4,8,5,7,4,8,7,7,7,7,3,4,2,8,3,7,4,8,6,4,7,7, 4,5,3,7,4,6,5,7,5,3,6,6,
6,7,5,7,6,6,7,7,5,3,6,6,6,7,5,7,6,6,7,7,5,3,6,6, 5,6,6,6,5,7,8,6,4,2,5,5,
6,7,5,7,6,6,7,7,5,3,6,6, 6,7,5,7,6,6,7,7,5,3,6,6, 3,4,4,8,3,9,6,8,6,4,7,7,
3,4,2,6,3,5,4,6,6,4,5,5, 4,5,3,5,4,4,5,5,5,3,4,4, 5,6,4,8,5,7,6,8,6,4,7,7,
5,6,4,8,5,7,6,8,6,4,7,7, 4,5,5,7,4,8,7,7,5,3,6,6, 5,6,4,8,5,7,6,8,6,4,7,7,
3,4,2,6,3,5,4,6,6,4,5,5, 5,6,4,8,5,7,6,8,6,4,7,7, 5,6,4,8,5,7,6,8,6,4,7,7,
5,4,4,6,5,5,6,6,6,6,7,5, 6,5,5,5,6,4,5,5,5,7,6,4, 4,5,3,7,4,6,5,7,7,5,6,6,
6,5,5,5,6,4,5,5,5,7,6,4, 3,4,4,6,3,7,6,6,6,4,5,5), nrow=12))
rownames(obj.vals) <- c("Enclosed Offices", "Open Office", "Reception / Greeter", "Studio / Classroom",
"Conference / Meeting Room", "Gallery", "Public / Lobby / Waiting",
"Collaborative Space", "Mechanical / Support", "Storage / Archives",
"Fabrication", "Performance")
对于 12 个程序中的每一个，让我们设置可以分配给所有房间的最大重复次数。请注意，这是我添加的内容，因为该数据不是由 OP 提供的。 （限制他们被分配到太多房间。）
max_programs <- c(1,2,3,1,5,2,3,4,1,3,1,2)
library(lpSolveAPI)
nrooms <- 28
nprgs <- 12
ncol = nrooms*nprgs
lp_matching <- make.lp(ncol=ncol)
#we want integer assignments
set.type(lp_matching, columns=1:ncol, type = c("integer"))
# sum r,p Crp * Xrp
set.objfn(lp_matching, obj.vals) #28 rooms * 12 programs
lp.control(lp_matching,sense='max')
#' Set Max Programs constraints
#' No more than max number of programs over all the rooms
#' X1p + x2p + x3p ... + x28p <= max(p) for each p
Add_Max_program_constraint <- function (prog_index) {
prog_cols <- (0:(nrooms-1))*nprgs + prog_index
add.constraint(lp_matching, rep(1,nrooms), indices=prog_cols, rhs=max_programs[prog_index])
}
#Add a max_number constraint for each program
lapply(1:nprgs, Add_Max_program_constraint)
#' Sum of all the programs assigned to each room, over all programs
#' area_1 * Xr1+ area 2* Xr2+ ... + area12* Xr12 <= room.size[r] for each room
Add_room_size_constraint <- function (room_index) {
room_cols <- (room_index-1)*nprgs + (1:nprgs) #relevant columns for a given room
add.constraint(lp_matching, xt=program.size, indices=room_cols, rhs=room.size[room_index])
}
#Add a max_number constraint for each program
lapply(1:nrooms, Add_room_size_constraint)
解决这个问题：
> solve(lp_matching)
> get.objective(lp_matching)
[1] 195
get.variables(lp_matching) # to see which programs went to which rooms
> print(lp_matching)
Model name:
a linear program with 336 decision variables and 40 constraints
您也可以将 IP 模型写入文件进行检查：
#Give identifiable column and row names
rp<- t(outer(1:nrooms, 1:nprgs, paste, sep="_"))
rp_vec <- paste(abc, sep="")
colnames<- paste("x_",rp_vec, sep="")
# RowNames
rownames1 <- paste("MaxProg", 1:nprgs, sep="_")
rownames2 <- paste("Room", 1:nrooms, "AreaLimit", sep="_")
dimnames(lp_matching) <- list(c(rownames1, rownames2), colnames)
write.lp(lp_matching,filename="room_matching.lp")
希望对您有所帮助。
根据后续问题更新
跟进问题 1：修改代码以确保每个房间至少有一个程序。
添加以下约束集：
X_r_p >= 1 for all r
注意：由于这是一个最大化问题，因此默认情况下最优解应遵守此约束。换句话说，如果可以的话，它总是会把一个程序分配给任何房间，假设分配的分数是正数。
跟进问题2：另外一个问题是我是否可以要求它总共有超过28个程序？例如，如果我想要 28 个封闭式办公室，它们几乎都可以放在一个 2938 平方英尺的房间里。如果最大值设置为 28，我如何让 R 仍然找到其他程序？
为了实现这个目标，你可以做一些不同的事情。根本没有所有程序的总和 <= 28 约束。 （如果您在上面的解决方案中注意到，我的约束略有不同。）
约束条件：
Sum(r) X_r_p <= Max_allowable(p) for each program p
仅限制每个 type 程序的最大值。总量没有限制。此外，您不必为每种类型的程序编写一个这样的约束。只有当你想限制它的出现时才写这个约束。
为了概括这一点，您可以为每种类型的程序的总数设置下限和上限。这将使您可以很好地控制分配。
min_allowable(p) <= sum(over r) X_r_p <= max_allowable(p) for any program type p
我有一个房间列表、房间的最大平方英尺、程序、程序的最大平方英尺以及房间与预期程序用途匹配（匹配#）的值。在帮助下，我已经能够最大限度地利用每个房间的一个程序使用 match # 和平方英尺。但是，我想将此分析更进一步，允许在同一个房间中使用多个程序，或者如果具有最高匹配 #，则允许同一程序的多个程序，只要多个程序仍然符合平方英尺要求。此外，我想总体上告诉 lpSolve，我只想要 "x" 数量的办公室，"y" 数量的工作室，等等。到目前为止，这是我的数据和代码：
program.size <- c(120,320,300,800,500,1000,500,1000,1500,400,1500,2000)
room.size <- c(1414,682,1484,2938,1985,1493,427,1958,708,581,1485,652,727,2556,1634,187,2174,205,1070,2165,1680,1449,1441,2289,986,298,590,2925)
(obj.vals <- matrix(c(3,4,2,8,3,7,4,8,6,4,7,7,
3,4,2,8,3,7,4,8,6,4,7,7,
4,5,3,7,4,6,5,7,5,3,6,6,
2,3,1,7,2,6,3,7,7,5,6,6,
4,5,3,7,4,6,5,7,5,3,6,6,
3,6,4,8,5,7,4,8,7,7,7,7,
3,4,2,8,3,7,4,8,6,4,7,7,
4,5,3,7,4,6,5,7,5,3,6,6,
6,7,5,7,6,6,7,7,5,3,6,6,
6,7,5,7,6,6,7,7,5,3,6,6,
5,6,6,6,5,7,8,6,4,2,5,5,
6,7,5,7,6,6,7,7,5,3,6,6,
6,7,5,7,6,6,7,7,5,3,6,6,
3,4,4,8,3,9,6,8,6,4,7,7,
3,4,2,6,3,5,4,6,6,4,5,5,
4,5,3,5,4,4,5,5,5,3,4,4,
5,6,4,8,5,7,6,8,6,4,7,7,
5,6,4,8,5,7,6,8,6,4,7,7,
4,5,5,7,4,8,7,7,5,3,6,6,
5,6,4,8,5,7,6,8,6,4,7,7,
3,4,2,6,3,5,4,6,6,4,5,5,
5,6,4,8,5,7,6,8,6,4,7,7,
5,6,4,8,5,7,6,8,6,4,7,7,
5,4,4,6,5,5,6,6,6,6,7,5,
6,5,5,5,6,4,5,5,5,7,6,4,
4,5,3,7,4,6,5,7,7,5,6,6,
6,5,5,5,6,4,5,5,5,7,6,4,
3,4,4,6,3,7,6,6,6,4,5,5), nrow=12))
rownames(obj.vals) <- c("Enclosed Offices", "Open Office", "Reception / Greeter", "Studio / Classroom",
"Conference / Meeting Room", "Gallery", "Public / Lobby / Waiting",
"Collaborative Space", "Mechanical / Support", "Storage / Archives",
"Fabrication", "Performance")
(obj.adj <- obj.vals * outer(program.size, room.size, "<="))
nr <- nrow(obj.adj)
nc <- ncol(obj.adj)
library(lpSolve)
obj <- as.vector(obj.adj)
con <- t(1*sapply(1:nc, function(x) rep(1:nc == x, each=nr)))
dir <- rep("<=", nc)
rhs <- rep(1, nc)
mod <- lp("max", obj, con, dir, rhs, all.bin=TRUE)
final <- matrix(mod$solution, nrow=nr)
所以现在我的问题是如何让求解器最大限度地使用平方英尺并在每个房间（列）内匹配 # 并允许多个相同的程序或程序的组合来完成此操作？我知道我必须解除 "mod" 中的“<= 1”限制，但我无法弄清楚如何让它在每个房间中找到最合适的，然后最终，整体。
房间[1]的解决方案是：
$optimum
33
并且它将尝试在房间内安装 11 个封闭办公室，其最佳匹配度比 1 个协作 Space（8 个匹配）和 1 个存储/档案室（4 个匹配）总得分高得多共 12 场比赛。
因此这引出了我的下一个问题，即限制我的解决方案矩阵中某些程序的总数。我假设它会包括某种
as.numeric(data$EnclosedOffices "<=" 5)
但我也不知道如何限制它。这些数字对于所有程序都是不同的。
感谢您提供的所有帮助，如有任何疑问，请随时提出要求。
更新： 约束
- 最大化每个房间的匹配 # (obj.vals)。
- 最大化每个 room.size 平方内的 program.size 平方英尺 脚。通过多次使用相同的程序（5 x 封闭式办公室）或组合程序（1 协作 Space 和 1 性能）。
- 限制and/or强制返回程序数 解决方案。只要不超过我在所有房间中为该节目提供的最大数量，节目就可以在房间之间分开。 （在所有 28 列中只能选择 5 个封闭办公室、8 个 Studios/Classrooms、1 个制造等。
如果您使用 R 包 lpSolveAPI（lpSolve 的包装器），那么它会变得更容易一些。
首先，看一下数学公式（整数程序），然后我会向您展示解决问题的代码。
公式
设 X_r_p 为取正整数值的决策变量。
X_r_p = 分配给房间 r 的类型 p 的程序数
（在你所有的问题中将有 28*12=336 个决策变量）
Objective函数
最大化匹配分数
Max sum(r) sum(p) C_r_p * X_r_p #这里C_r_p是将p分配到房间r的分数
以
为准房间面积限制约束
Sum(p) Max_area_p * X_r_p <= Room Size (r) for each room r
（我们会有28个这样的约束）
限制节目数量Constraint
Sum(r) X_r_p <= Max_allowable(p) for each program p
（我们会有12个这样的约束）
X_r_p >= 0, Integer
总的来说就是这样。 336 列和 40 行。
在 R 中实现
这是 R 中的一个实现，使用 lpSolveAPI。
注意：由于 OP 没有在建筑物中提供 max_allowable 程序，因此我为 max_programs.
program.size <- c(120,320,300,800,500,1000,500,1000,1500,400,1500,2000)
room.size <- c(1414,682,1484,2938,1985,1493,427,1958,708,581,1485,652,727,2556,1634,187,2174,205,1070,2165,1680,1449,1441,2289,986,298,590,2925)
(obj.vals <- matrix(c(3,4,2,8,3,7,4,8,6,4,7,7,3,4,2,8,3,7,4,8,6,4,7,7,
4,5,3,7,4,6,5,7,5,3,6,6,2,3,1,7,2,6,3,7,7,5,6,6, 4,5,3,7,4,6,5,7,5,3,6,6,
3,6,4,8,5,7,4,8,7,7,7,7,3,4,2,8,3,7,4,8,6,4,7,7, 4,5,3,7,4,6,5,7,5,3,6,6,
6,7,5,7,6,6,7,7,5,3,6,6,6,7,5,7,6,6,7,7,5,3,6,6, 5,6,6,6,5,7,8,6,4,2,5,5,
6,7,5,7,6,6,7,7,5,3,6,6, 6,7,5,7,6,6,7,7,5,3,6,6, 3,4,4,8,3,9,6,8,6,4,7,7,
3,4,2,6,3,5,4,6,6,4,5,5, 4,5,3,5,4,4,5,5,5,3,4,4, 5,6,4,8,5,7,6,8,6,4,7,7,
5,6,4,8,5,7,6,8,6,4,7,7, 4,5,5,7,4,8,7,7,5,3,6,6, 5,6,4,8,5,7,6,8,6,4,7,7,
3,4,2,6,3,5,4,6,6,4,5,5, 5,6,4,8,5,7,6,8,6,4,7,7, 5,6,4,8,5,7,6,8,6,4,7,7,
5,4,4,6,5,5,6,6,6,6,7,5, 6,5,5,5,6,4,5,5,5,7,6,4, 4,5,3,7,4,6,5,7,7,5,6,6,
6,5,5,5,6,4,5,5,5,7,6,4, 3,4,4,6,3,7,6,6,6,4,5,5), nrow=12))
rownames(obj.vals) <- c("Enclosed Offices", "Open Office", "Reception / Greeter", "Studio / Classroom",
"Conference / Meeting Room", "Gallery", "Public / Lobby / Waiting",
"Collaborative Space", "Mechanical / Support", "Storage / Archives",
"Fabrication", "Performance")
对于 12 个程序中的每一个，让我们设置可以分配给所有房间的最大重复次数。请注意，这是我添加的内容，因为该数据不是由 OP 提供的。 （限制他们被分配到太多房间。）
max_programs <- c(1,2,3,1,5,2,3,4,1,3,1,2)
library(lpSolveAPI)
nrooms <- 28
nprgs <- 12
ncol = nrooms*nprgs
lp_matching <- make.lp(ncol=ncol)
#we want integer assignments
set.type(lp_matching, columns=1:ncol, type = c("integer"))
# sum r,p Crp * Xrp
set.objfn(lp_matching, obj.vals) #28 rooms * 12 programs
lp.control(lp_matching,sense='max')
#' Set Max Programs constraints
#' No more than max number of programs over all the rooms
#' X1p + x2p + x3p ... + x28p <= max(p) for each p
Add_Max_program_constraint <- function (prog_index) {
prog_cols <- (0:(nrooms-1))*nprgs + prog_index
add.constraint(lp_matching, rep(1,nrooms), indices=prog_cols, rhs=max_programs[prog_index])
}
#Add a max_number constraint for each program
lapply(1:nprgs, Add_Max_program_constraint)
#' Sum of all the programs assigned to each room, over all programs
#' area_1 * Xr1+ area 2* Xr2+ ... + area12* Xr12 <= room.size[r] for each room
Add_room_size_constraint <- function (room_index) {
room_cols <- (room_index-1)*nprgs + (1:nprgs) #relevant columns for a given room
add.constraint(lp_matching, xt=program.size, indices=room_cols, rhs=room.size[room_index])
}
#Add a max_number constraint for each program
lapply(1:nrooms, Add_room_size_constraint)
解决这个问题：
> solve(lp_matching)
> get.objective(lp_matching)
[1] 195
get.variables(lp_matching) # to see which programs went to which rooms
> print(lp_matching)
Model name:
a linear program with 336 decision variables and 40 constraints
您也可以将 IP 模型写入文件进行检查：
#Give identifiable column and row names
rp<- t(outer(1:nrooms, 1:nprgs, paste, sep="_"))
rp_vec <- paste(abc, sep="")
colnames<- paste("x_",rp_vec, sep="")
# RowNames
rownames1 <- paste("MaxProg", 1:nprgs, sep="_")
rownames2 <- paste("Room", 1:nrooms, "AreaLimit", sep="_")
dimnames(lp_matching) <- list(c(rownames1, rownames2), colnames)
write.lp(lp_matching,filename="room_matching.lp")
希望对您有所帮助。
根据后续问题更新
跟进问题 1：修改代码以确保每个房间至少有一个程序。
添加以下约束集：
X_r_p >= 1 for all r
注意：由于这是一个最大化问题，因此默认情况下最优解应遵守此约束。换句话说，如果可以的话，它总是会把一个程序分配给任何房间，假设分配的分数是正数。
跟进问题2：另外一个问题是我是否可以要求它总共有超过28个程序？例如，如果我想要 28 个封闭式办公室，它们几乎都可以放在一个 2938 平方英尺的房间里。如果最大值设置为 28，我如何让 R 仍然找到其他程序？
为了实现这个目标，你可以做一些不同的事情。根本没有所有程序的总和 <= 28 约束。 （如果您在上面的解决方案中注意到，我的约束略有不同。）
约束条件：
Sum(r) X_r_p <= Max_allowable(p) for each program p
仅限制每个 type 程序的最大值。总量没有限制。此外，您不必为每种类型的程序编写一个这样的约束。只有当你想限制它的出现时才写这个约束。
为了概括这一点，您可以为每种类型的程序的总数设置下限和上限。这将使您可以很好地控制分配。
min_allowable(p) <= sum(over r) X_r_p <= max_allowable(p) for any program type p