离散优化算法

Question

我正在努力决定解决问题的最佳方法，如下所示：

我有一组对象(约3k-5k)，我希望将它们唯一地分配给大约10个组(每个对象一个组)。每个对象都有一组与其在每一组中的匹配程度相对应的等级。每个组都有它可以管理的对象的容量(约束)。我的目标是最大限度地提高我的作业成绩的总和。

例如，假设我有3个对象(o1、o2、o3)和2个组(g1，g2)，它们都有一个上限。每个一个物体。现在假设年级是：

o1: g1=11，g2=8

o2: g1=10，g2=5

o3: g1=5，g2=6

在这种情况下，为了获得最优结果，g1应该接收o2，而g2应该接收o1，从而得到总共的10+8=18点。

请注意，对象的数量可以超过配额的总和(例如，将o3保留为“剩馀部分”)，或者无法填充配额。

我应该如何解决这个问题(旅行推销员，某种程度上的加权克纳普-袋等)？野蛮地强迫它在一台普通的计算机上需要多长时间？是否有任何标准工具，如Matlab中的linprog函数支持这类问题？

Answer 1

它可以用最小成本流算法求解。该图形可以以下列方式显示：

它应该是两部分的。左边的部分表示对象(每个对象有一个顶点)。右边的部分表示组(每个组有一个顶点)。从左边的每个顶点到右边的每个顶点都有一个边，这对capacity =1和cost = -grade。在capacity =1和cost = 0的情况下，从源顶点到左侧的每个顶点也有一个边，从右边的每个顶点到汇顶点(接收器和源是两个附加的顶点)都有一条边，该组的capacity =约束和cost =0。

答案是-the cheapest flow cost from the source to the sink。

它可以用O(N^2 * M * log(N + M))时间复杂度来实现(使用带势的Dijkstra算法)(N是对象的数量，M是组的数目)。

Answer 2

这可以用整数程序来解决。二进制变量x_{ij}如果对象i被赋值给组j。目标最大化\sum_{i，j} s_{ij} x_{ij}，其中s_{ij}是与将i赋值给j相关联的分数，x_{ij}是是否分配给j的。您有两种类型的约束：

• \sum_i x_{ij} <= c_j适用于所有j，组的容量约束
• \sum_j x_{ij} <= 1用于所有i，将对象分配给最多一个组

下面是在R中实现它的方法-- R中的lp函数非常类似于matlab中的linprog函数。

# Score matrix
S <- matrix(c(11, 10, 5, 8, 5, 6), nrow=3)
# Capacity vector
cvec <- c(1, 1)

# Helper function to construct constraint matrices
unit.vec <- function(pos, n) {
  ret <- rep(0, n)
  ret[pos] <- 1
  ret
}

# Capacity constraints
cap <- t(sapply(1:ncol(S), function(j) rep(unit.vec(j, ncol(S)), nrow(S))))

# Object assignment constraints
obj <- t(sapply(1:nrow(S), function(i) rep(unit.vec(i, nrow(S)), each=ncol(S))))

# Solve the LP
res <- lp(direction="max",
          objective.in=as.vector(t(S)),
          const.mat=rbind(cap, obj),
          const.dir="<=",
          const.rhs=c(cvec, rep(1, nrow(S))),
          all.bin=TRUE)

# Grab assignments and objective
sln <- t(matrix(res$solution, nrow=ncol(S)))
apply(sln, 1, function(x) ifelse(sum(x) > 0.999, which(x == 1), NA))
# [1]  2  1 NA
res$objval
# [1] 18

虽然这是用二进制变量建模的，但它将有效地解决假设积分容量的问题。