解决具有特定约束的分配问题
Solving the assignment problem with specific constraints
想象以下数据（重现所有输出的代码在最后）：
df
cars horsepower year safety
1 Toyota 140 2008 4
2 Chrysler 120 2009 4
3 Ford 140 2010 5
4 BMW 150 2008 3
5 Mercedes-Benz 150 2008 3
6 Hyundai 120 2009 4
7 Jaguar 150 2007 3
8 Tesla 120 2010 5
我想换车以获得类似的东西：
cars_initial cars_match horsepower year safety horsepowerMatch yearMatch safetyMatch
1 Toyota BMW 140 2008 4 150 2008 3
2 Tesla Chrysler 120 2010 5 120 2009 4
3 Mercedes-Benz Ford 150 2008 3 140 2010 5
4 Jaguar Hyundai 150 2007 3 120 2009 4
5 Hyundai Jaguar 120 2009 4 150 2007 3
6 Ford Mercedes-Benz 140 2010 5 150 2008 3
7 Chrysler Tesla 120 2009 4 120 2010 5
8 BMW Toyota 150 2008 3 140 2008 4
现在这是一个典型的分配问题，在上述情况下是随机解决的，即在所有情况下成本矩阵都设置为 0。
我感兴趣的是结果。在上述情况下，解决方案产生以下统计数据：
stats
horsepower year safety
1 0.25 0.25 0
也就是说，1/4 的交换具有相同的马力等
这是我的问题：如何通过直接对结果统计数据的确切内容设置约束来解决此类分配，而无需通过设置成本的反复试验方法？
例如，如果我想要一个解决方案，其中 safety 有超过 0.20 个匹配项，并且 year 至少有 0.10 个，如下所示？
desiredOutput
cars_initial cars_match
1 Toyota Chrysler
2 Tesla Mercedes-Benz
3 Mercedes-Benz BMW
4 Jaguar Toyota
5 Hyundai Tesla
6 Ford Hyundai
7 Chrysler Jaguar
8 BMW Ford
statsDesired
horsepower year safety
1 0.25 0.12 0.25
当然，在 safety 辆汽车相等的所有情况下，我都可以将成本矩阵设置为较低的数字。
但是有没有办法通过直接对结果统计数据设置约束来影响结果？
也许有一种方法可以优化成本以达到预期的结果？
代码：
library(lpSolve)
library(dplyr)
library(tidyr)
set.seed(1)
df <- data.frame(
cars = c("Toyota", "Chrysler", "Ford", "BMW", "Mercedes-Benz", "Hyundai", "Jaguar", "Tesla"),
horsepower = c(140, 120, 140, 150, 150, 120, 150, 120),
year = c(2008, 2009, 2010, 2008, 2008, 2009, 2007, 2010),
safety = c(4, 4, 5, 3, 3, 4, 3, 5)
)
mat <- df %>% select(cars) %>%
crossing(df %>% select(cars)) %>%
mutate(val = 0) %>%
spread(cars, val)
solved <- lp.assign(mat %>% select(-cars1) %>% as.matrix())$solution
matches <- as.data.frame(solved) %>%
setNames(., names(mat %>% select(-cars1))) %>%
bind_cols(mat %>% select(cars1)) %>%
gather(key, val, -cars1) %>%
filter(val == 1) %>% select(-val, cars_initial = cars1, cars_match = key)
nms <- c("cars", paste0(names(df %>% select(-cars)), "Match"))
matches <- matches %>%
left_join(df, by = c("cars_initial" = "cars")) %>%
left_join(df %>% setNames(., nms), by = c("cars_match" = "cars"))
stats <- matches %>%
summarise(
horsepower = round(sum(horsepower == horsepowerMatch) / n(), 2),
year = round(sum(year == yearMatch) / n(), 2),
safety = round(sum(safety == safetyMatch) / n(), 2)
)
desiredOutput <- data.frame(cars_initial = matches$cars_initial, cars_match = c("Chrysler", "Mercedes-Benz", "BMW", "Toyota", "Tesla", "Hyundai", "Jaguar", "Ford"))
statsDesired <- desiredOutput %>%
left_join(df, by = c("cars_initial" = "cars")) %>%
left_join(df %>% setNames(., nms), by = c("cars_match" = "cars")) %>%
summarise(
horsepower = round(sum(horsepower == horsepowerMatch) / n(), 2),
year = round(sum(year == yearMatch) / n(), 2),
safety = round(sum(safety == safetyMatch) / n(), 2)
)
我希望上面的例子足够了，这是我的第一个问题所以如果我需要提供更多的东西请告诉我。
代码在 R 中，但我还添加了标签 Python，因为我不太介意可能的解决方案的语言。
这是此问题作为整数规划 (IP) 问题的部分表述。
让I成为汽车类型的集合。对于 I 中的车型 i 和 j，令：
h[i,j] = 1 如果汽车 i 和 j 具有相同的马力y[i,j] = 1 如果汽车 i 和 j 的年份相同 s[i,j]（安全）
这些是参数，表示模型的输入。 （您需要编写代码来根据您的数据计算这些二进制量 table。）
现在介绍以下决策变量，即您的IP模型将选择值的变量：
x[i,j] = 1 如果我们指定汽车类型 j 作为类型 i 的匹配
现在，通常一个 IP 有一个我们想要最小化或最大化的 objective 函数。在这种情况下，没有 objective 函数——您只想找到一组满足您的约束条件的匹配项。所以你的 objective 函数可以是：
minimize 0
这是第一个约束条件。它说：至少 a 场比赛必须具有相同的马力。 （a 是一个分数。） left-hand 方是具有相同马力的匹配数：对于每对车型 i 和 j，如果 j被分配为i的比赛和他们有相同的马力，算一个1；否则，算一个 0。 right-hand 边是你想要的匹配数，即整个集合的 a 部分。
subject to sum {i in I, j in I} h[i,j] * x[i,j] >= a * |I|
现在为其他类别制定类似的约束条件。
接下来，您需要一个约束条件，表示每种车型 i 必须恰好分配给一种车型 j:
subject to sum {j in I} x[i,j] == 1 for all i in I
最后，您需要说明决策变量是二元的约束：
subject to x[i,j] in {0,1} for all i, j in I
现在，就解决这个问题而言，您将需要使用像 AMPL 或 GAMS 这样的数学建模语言，或者像 PuLP for Python.
这样的包
希望对您有所帮助。我可能咬的比你在这里咀嚼的还要多。
想象以下数据（重现所有输出的代码在最后）：
df
cars horsepower year safety
1 Toyota 140 2008 4
2 Chrysler 120 2009 4
3 Ford 140 2010 5
4 BMW 150 2008 3
5 Mercedes-Benz 150 2008 3
6 Hyundai 120 2009 4
7 Jaguar 150 2007 3
8 Tesla 120 2010 5
我想换车以获得类似的东西：
cars_initial cars_match horsepower year safety horsepowerMatch yearMatch safetyMatch
1 Toyota BMW 140 2008 4 150 2008 3
2 Tesla Chrysler 120 2010 5 120 2009 4
3 Mercedes-Benz Ford 150 2008 3 140 2010 5
4 Jaguar Hyundai 150 2007 3 120 2009 4
5 Hyundai Jaguar 120 2009 4 150 2007 3
6 Ford Mercedes-Benz 140 2010 5 150 2008 3
7 Chrysler Tesla 120 2009 4 120 2010 5
8 BMW Toyota 150 2008 3 140 2008 4
现在这是一个典型的分配问题，在上述情况下是随机解决的，即在所有情况下成本矩阵都设置为 0。
我感兴趣的是结果。在上述情况下，解决方案产生以下统计数据：
stats
horsepower year safety
1 0.25 0.25 0
也就是说，1/4 的交换具有相同的马力等
这是我的问题：如何通过直接对结果统计数据的确切内容设置约束来解决此类分配，而无需通过设置成本的反复试验方法？
例如，如果我想要一个解决方案，其中 safety 有超过 0.20 个匹配项，并且 year 至少有 0.10 个，如下所示？
desiredOutput
cars_initial cars_match
1 Toyota Chrysler
2 Tesla Mercedes-Benz
3 Mercedes-Benz BMW
4 Jaguar Toyota
5 Hyundai Tesla
6 Ford Hyundai
7 Chrysler Jaguar
8 BMW Ford
statsDesired
horsepower year safety
1 0.25 0.12 0.25
当然，在 safety 辆汽车相等的所有情况下，我都可以将成本矩阵设置为较低的数字。
但是有没有办法通过直接对结果统计数据设置约束来影响结果？
也许有一种方法可以优化成本以达到预期的结果？
代码：
library(lpSolve)
library(dplyr)
library(tidyr)
set.seed(1)
df <- data.frame(
cars = c("Toyota", "Chrysler", "Ford", "BMW", "Mercedes-Benz", "Hyundai", "Jaguar", "Tesla"),
horsepower = c(140, 120, 140, 150, 150, 120, 150, 120),
year = c(2008, 2009, 2010, 2008, 2008, 2009, 2007, 2010),
safety = c(4, 4, 5, 3, 3, 4, 3, 5)
)
mat <- df %>% select(cars) %>%
crossing(df %>% select(cars)) %>%
mutate(val = 0) %>%
spread(cars, val)
solved <- lp.assign(mat %>% select(-cars1) %>% as.matrix())$solution
matches <- as.data.frame(solved) %>%
setNames(., names(mat %>% select(-cars1))) %>%
bind_cols(mat %>% select(cars1)) %>%
gather(key, val, -cars1) %>%
filter(val == 1) %>% select(-val, cars_initial = cars1, cars_match = key)
nms <- c("cars", paste0(names(df %>% select(-cars)), "Match"))
matches <- matches %>%
left_join(df, by = c("cars_initial" = "cars")) %>%
left_join(df %>% setNames(., nms), by = c("cars_match" = "cars"))
stats <- matches %>%
summarise(
horsepower = round(sum(horsepower == horsepowerMatch) / n(), 2),
year = round(sum(year == yearMatch) / n(), 2),
safety = round(sum(safety == safetyMatch) / n(), 2)
)
desiredOutput <- data.frame(cars_initial = matches$cars_initial, cars_match = c("Chrysler", "Mercedes-Benz", "BMW", "Toyota", "Tesla", "Hyundai", "Jaguar", "Ford"))
statsDesired <- desiredOutput %>%
left_join(df, by = c("cars_initial" = "cars")) %>%
left_join(df %>% setNames(., nms), by = c("cars_match" = "cars")) %>%
summarise(
horsepower = round(sum(horsepower == horsepowerMatch) / n(), 2),
year = round(sum(year == yearMatch) / n(), 2),
safety = round(sum(safety == safetyMatch) / n(), 2)
)
我希望上面的例子足够了，这是我的第一个问题所以如果我需要提供更多的东西请告诉我。
代码在 R 中，但我还添加了标签 Python，因为我不太介意可能的解决方案的语言。
这是此问题作为整数规划 (IP) 问题的部分表述。
让I成为汽车类型的集合。对于 I 中的车型 i 和 j，令：
h[i,j]= 1 如果汽车i和j具有相同的马力y[i,j]= 1 如果汽车i和j的年份相同s[i,j]（安全）
这些是参数，表示模型的输入。 （您需要编写代码来根据您的数据计算这些二进制量 table。）
现在介绍以下决策变量，即您的IP模型将选择值的变量：
x[i,j]= 1 如果我们指定汽车类型j作为类型i的匹配
现在，通常一个 IP 有一个我们想要最小化或最大化的 objective 函数。在这种情况下，没有 objective 函数——您只想找到一组满足您的约束条件的匹配项。所以你的 objective 函数可以是：
minimize 0
这是第一个约束条件。它说：至少 a 场比赛必须具有相同的马力。 （a 是一个分数。） left-hand 方是具有相同马力的匹配数：对于每对车型 i 和 j，如果 j被分配为i的比赛和他们有相同的马力，算一个1；否则，算一个 0。 right-hand 边是你想要的匹配数，即整个集合的 a 部分。
subject to sum {i in I, j in I} h[i,j] * x[i,j] >= a * |I|
现在为其他类别制定类似的约束条件。
接下来，您需要一个约束条件，表示每种车型 i 必须恰好分配给一种车型 j:
subject to sum {j in I} x[i,j] == 1 for all i in I
最后，您需要说明决策变量是二元的约束：
subject to x[i,j] in {0,1} for all i, j in I
现在，就解决这个问题而言，您将需要使用像 AMPL 或 GAMS 这样的数学建模语言，或者像 PuLP for Python.
希望对您有所帮助。我可能咬的比你在这里咀嚼的还要多。