如何按具有约束条件的组拆分

Question

我正在尝试解决优化问题。

比如我们有10组人：

第 1 组：20

第 2 组：5

第 3 组：15

第 4 组：10

第 5 组：12

第 6 组：26

第 7 组：41

第 8 组：15

第 9 组：69

第 10 组：9

我们正在尝试将这些人群载入多辆公共汽车，但无法分散人群。每辆公共汽车只能载80人。关于 r code/function 的任何建议，可以让我获得所需的最少公交车数量。谢谢！

Answer 1

这是一个 bin-packing 问题，您可以在网上找到很多解决方法。

无论如何，这是一个贪心算法的解决方案。这并不能保证最佳解决方案，但应该足够好 -

grp <- c(20, 5, 15, 10, 12, 26, 41, 15, 69, 9)
cap <- 80

sorted_grp <- sort(grp, decreasing = T)

buses <- list("bus_1" = NULL)
for(g in seq_along(sorted_grp)) {
  balance_cap <- cap - sapply(buses, function(x) sum(x))
  if(any(balance_cap >= sorted_grp[g])) {
    feasible_bus <- which(balance_cap >= sorted_grp[g])[1]
    buses[[paste0("bus_", feasible_bus)]] <- c(buses[[paste0("bus_", feasible_bus)]], sorted_grp[g])
  } else {
    buses[[paste0("bus_", length(buses) + 1)]] <- sorted_grp[g]
  }
}

# > paste0("Number of buses: ", length(buses))
# [1] "Number of buses: 3"
# > buses
# $`bus_1`
# [1] 69 10
# 
# $bus_2
# [1] 41 26 12
# 
# $bus_3
# [1] 20 15 15  9  5

Answer 2

对于固定数量的容器，这可以表述为整数线性规划问题。如果 g 是 10 个组号的向量， cap 是容量，即 80，则必须至少有 k=ceiling(sum(g) / cap) 个容器，并且不超过 k=length(g) 。因此，我们从最小到最大数量连续地适应容器，一旦我们适应就停止。对于问题中显示的数据（请参阅末尾的注释），只需要一次迭代。

在 lp 问题中有 k x n 个二进制变量，如果我们将它们排列在 k x n 矩阵中，那么如果第 i 个容器包含元素 j 和 0，则 i，j-th 为 1除此以外。

lp 问题有 k+n 个约束条件。前 k 个约束将 k 个容器中每个容器的总和限制为 cap，其余 n 个约束确保每个元素只能出现在一个容器中。

library(lpSolve)
stopifnot(all(g <= cap))

n <- length(g)
kmin <- ceiling(sum(g) / cap)
for(k in seq(kmin, n)) {
  objective.in <- rep(1, k * n)
  const.mat <- rbind(diag(k) %x% t(g), t(rep(1, k)) %x% diag(n))
  const.dir <- c(rep("<=", k), rep("==", n))
  const.rhs <- c(rep(cap, k), rep(1, n))
  res <- lp("min", objective.in, const.mat, const.dir, const.rhs, all.bin = TRUE)
  if (res$status == 0) break
}

# iterations
k - kmin + 1
## [1] 1

# solution - each col is an element, each row is a container 
matrix(res$solution, k, byrow = TRUE)
##      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
## [1,]    1    1    1    1    1    0    0    1    0     0
## [2,]    0    0    0    0    0    1    1    0    0     1
## [3,]    0    0    0    0    0    0    0    0    1     0

备注

使用的输入是这样的：

Lines <- "Group 1: 20
Group 2: 5
Group 3: 15
Group 4: 10
Group 5: 12
Group 6: 26
Group 7: 41
Group 8: 15
Group 9: 69
Group 10: 9"
g <- read.table(text = Lines)$V3

cap <- 80

如何按具有约束条件的组拆分

How to split by a group with constraints

r

mathematical-optimization

备注