如何让 Gurobi（使用 R）显示所有解决方案
How can I make Gurobi (Using R) show all solutions
如问题所述：我知道有几种解决方案（查看 GA 的输出并检查值和约束是否正确），但我无法将它们从 Gurobi 中取出。
在@Paleo13 的回答后编辑：正如他所说，他的回答是一个很好的解决方法。但是，如果有更有效的选择，我也很想看看。因此，我增加了赏金。有关我所知道的，请参阅 and 。
可重现的例子：
my_fun <- function(x) {
f <- sum(model$obj * x)
penalty <- sum(abs(model$A %*% x - model$rhs))
return_value <- -f - 1e8 * penalty # sum(model$obj^2) * // 1e7 *
return(return_value)
}
model <- structure(
list(modelsense = "min",
obj = c(0, 40, 20, 40, 0, 20, 20, 20, 0),
A = structure(c(0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 1, 0, 0, 1,
1, 0, -1, 0, 0, 0, 0, -1, 1, 0, 0, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 1, -1, 0, 0, 1, 0, -1, 0, 1, 0,
0, 1, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0),
.Dim = c(7L, 9L),
.Dimnames = list(
c("constraint1", "constraint2", "", "", "", "", ""),
NULL)),
rhs = c(1, 1, 0, 0, 0, 1, 1),
sense = c("=", "=", "=", "=", "=", "=", "="),
vtype = "B"),
.Names = c("modelsense", "obj", "A", "rhs", "sense", "vtype"))
# Gurobi:
params <- list(OutputFlag = 1, Presolve = 2, LogToConsole = 1, PoolSearchMode = 2, PoolSolutions = 10)
ilp_result <- gurobi::gurobi(model, params)
print(ilp_result$x)
# GA for cross-check
GA <- GA::ga(type = "binary", fitness = my_fun, nBits = length(model$obj),
maxiter = 3000, run = 2000, popSize = 10, seed = 12)
# Crosscheck:
summary(GA)
my_fun(ilp_result$x)
my_fun(GA@solution[1, ])
my_fun(GA@solution[2, ])
sum(abs(model$A %*% ilp_result$x - model$rhs))
sum(abs(model$A %*% GA@solution[1, ] - model$rhs))
sum(abs(model$A %*% GA@solution[2, ] - model$rhs))
Gurobi 确实可以存储它在寻找最佳解决方案（或者更确切地说是适合指定的opitmality 差距的解决方案）时遇到的可行解决方案。这些解决方案存储在 "solution pool" 中。不幸的是，gurobi R 包没有访问解决方案池中解决方案的功能，因此如果我们正在寻找仅使用 R[=22 的解决方案=] 那么我们不能使用解决方案池。此外，值得注意的是，解池不一定包含所有可行解，它只包含Gurobi一路找到的解，所以如果我们需要所有可行解，那么我们不能仅仅依赖 Gurobi.
的单个 运行 中的解决方案池
因此，关于您的问题，一种策略是使用称为 "Bender's cuts" 的方法。这基本上涉及解决问题，添加约束以禁止我们刚刚获得的解决方案，然后再次解决问题，并重复此过程，直到没有更多可行的解决方案。我已经使用下面的 gurobi R 包编写了一个实现此方法的函数，并将其应用于您的示例。这种方法可能无法很好地扩展到具有大量可行解决方案的问题，因为理想情况下我们会访问解决方案池以减少 Gurobi 运行 的总数，但是据我所知，这是最好的方法（但我很想听听是否有人有更好的想法）。
# define functions
find_all_feasible_solutions <- function(model, params) {
# initialize variables
counter <- 0
solutions <- list()
objs <- numeric(0)
# search for feasible solutions until no more exist
while (TRUE) {
# increment counter
counter <- counter + 1
# solve problem
s <- gurobi::gurobi(model, params)
# break if status indicates that no feasible solution found
if (s$status %in% c("INFEASIBLE")) break()
# store set of solutions
solutions[[counter]] <- s$x
objs[[counter]] <- s$objval
# add constraint to forbid solution this solution
model$rhs <- c(model$rhs, sum(s$x) - 1)
model$sense <- c(model$sense, "<=")
model$A <- rbind(model$A, (s$x * 2) - 1)
}
# throw error if no feasible sets of solutions found
if (length(solutions) == 0) {
stop("no feasible solutions found.")
}
# return solutions as matrix
list(x = do.call(rbind, solutions), obj = objs)
}
# create initial model
model <- list(
modelsense = "min",
obj = c(0, 40, 20, 40, 0, 20, 20, 20, 0),
A = structure(c(0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 1, 0, 0, 1,
1, 0, -1, 0, 0, 0, 0, -1, 1, 0, 0, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 1, -1, 0, 0, 1, 0, -1, 0, 1, 0,
0, 1, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0),
.Dim = c(7L, 9L),
.Dimnames = list(c("constraint1", "constraint2", "", "", "", "", ""),
NULL)),
rhs = c(1, 1, 0, 0, 0, 1, 1),
sense = c("=", "=", "=", "=", "=", "=", "="),
vtype = "B")
# create parameters
params <- list(OutputFlag = 1, Presolve = 2, LogToConsole = 1)
# find all feasible solutions
output <- find_all_feasible_solutions(model, params)
# print number of feasible solutions
print(length(output$obj))
您描述的内容可以用 Solution Pool. Gurobi added the R API for the solution pool in version 8.0. You set parameters to control the solution pool; the multiple solutions are returned in the Solution Pool named components. This is illustrated in the poolsearch.R example 完成，也可以在 examples\R 子目录中找到。
免责声明：我管理 Gurobi 的技术支持。
如问题所述：我知道有几种解决方案（查看 GA 的输出并检查值和约束是否正确），但我无法将它们从 Gurobi 中取出。
在@Paleo13 的回答后编辑：正如他所说，他的回答是一个很好的解决方法。但是，如果有更有效的选择，我也很想看看。因此，我增加了赏金。有关我所知道的，请参阅
可重现的例子：
my_fun <- function(x) {
f <- sum(model$obj * x)
penalty <- sum(abs(model$A %*% x - model$rhs))
return_value <- -f - 1e8 * penalty # sum(model$obj^2) * // 1e7 *
return(return_value)
}
model <- structure(
list(modelsense = "min",
obj = c(0, 40, 20, 40, 0, 20, 20, 20, 0),
A = structure(c(0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 1, 0, 0, 1,
1, 0, -1, 0, 0, 0, 0, -1, 1, 0, 0, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 1, -1, 0, 0, 1, 0, -1, 0, 1, 0,
0, 1, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0),
.Dim = c(7L, 9L),
.Dimnames = list(
c("constraint1", "constraint2", "", "", "", "", ""),
NULL)),
rhs = c(1, 1, 0, 0, 0, 1, 1),
sense = c("=", "=", "=", "=", "=", "=", "="),
vtype = "B"),
.Names = c("modelsense", "obj", "A", "rhs", "sense", "vtype"))
# Gurobi:
params <- list(OutputFlag = 1, Presolve = 2, LogToConsole = 1, PoolSearchMode = 2, PoolSolutions = 10)
ilp_result <- gurobi::gurobi(model, params)
print(ilp_result$x)
# GA for cross-check
GA <- GA::ga(type = "binary", fitness = my_fun, nBits = length(model$obj),
maxiter = 3000, run = 2000, popSize = 10, seed = 12)
# Crosscheck:
summary(GA)
my_fun(ilp_result$x)
my_fun(GA@solution[1, ])
my_fun(GA@solution[2, ])
sum(abs(model$A %*% ilp_result$x - model$rhs))
sum(abs(model$A %*% GA@solution[1, ] - model$rhs))
sum(abs(model$A %*% GA@solution[2, ] - model$rhs))
Gurobi 确实可以存储它在寻找最佳解决方案（或者更确切地说是适合指定的opitmality 差距的解决方案）时遇到的可行解决方案。这些解决方案存储在 "solution pool" 中。不幸的是，gurobi R 包没有访问解决方案池中解决方案的功能，因此如果我们正在寻找仅使用 R[=22 的解决方案=] 那么我们不能使用解决方案池。此外，值得注意的是，解池不一定包含所有可行解，它只包含Gurobi一路找到的解，所以如果我们需要所有可行解，那么我们不能仅仅依赖 Gurobi.
的单个 运行 中的解决方案池因此，关于您的问题，一种策略是使用称为 "Bender's cuts" 的方法。这基本上涉及解决问题，添加约束以禁止我们刚刚获得的解决方案，然后再次解决问题，并重复此过程，直到没有更多可行的解决方案。我已经使用下面的 gurobi R 包编写了一个实现此方法的函数，并将其应用于您的示例。这种方法可能无法很好地扩展到具有大量可行解决方案的问题，因为理想情况下我们会访问解决方案池以减少 Gurobi 运行 的总数，但是据我所知，这是最好的方法（但我很想听听是否有人有更好的想法）。
# define functions
find_all_feasible_solutions <- function(model, params) {
# initialize variables
counter <- 0
solutions <- list()
objs <- numeric(0)
# search for feasible solutions until no more exist
while (TRUE) {
# increment counter
counter <- counter + 1
# solve problem
s <- gurobi::gurobi(model, params)
# break if status indicates that no feasible solution found
if (s$status %in% c("INFEASIBLE")) break()
# store set of solutions
solutions[[counter]] <- s$x
objs[[counter]] <- s$objval
# add constraint to forbid solution this solution
model$rhs <- c(model$rhs, sum(s$x) - 1)
model$sense <- c(model$sense, "<=")
model$A <- rbind(model$A, (s$x * 2) - 1)
}
# throw error if no feasible sets of solutions found
if (length(solutions) == 0) {
stop("no feasible solutions found.")
}
# return solutions as matrix
list(x = do.call(rbind, solutions), obj = objs)
}
# create initial model
model <- list(
modelsense = "min",
obj = c(0, 40, 20, 40, 0, 20, 20, 20, 0),
A = structure(c(0, 0, 0, 0, 0, 0, 0, 0, 0, 1, -1, 0, 1, 0, 0, 1,
1, 0, -1, 0, 0, 0, 0, -1, 1, 0, 0, 1, 0, 0, 0, 0,
0, 0, 0, 0, 1, 0, 1, -1, 0, 0, 1, 0, -1, 0, 1, 0,
0, 1, 0, 0, -1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0),
.Dim = c(7L, 9L),
.Dimnames = list(c("constraint1", "constraint2", "", "", "", "", ""),
NULL)),
rhs = c(1, 1, 0, 0, 0, 1, 1),
sense = c("=", "=", "=", "=", "=", "=", "="),
vtype = "B")
# create parameters
params <- list(OutputFlag = 1, Presolve = 2, LogToConsole = 1)
# find all feasible solutions
output <- find_all_feasible_solutions(model, params)
# print number of feasible solutions
print(length(output$obj))
您描述的内容可以用 Solution Pool. Gurobi added the R API for the solution pool in version 8.0. You set parameters to control the solution pool; the multiple solutions are returned in the Solution Pool named components. This is illustrated in the poolsearch.R example 完成，也可以在 examples\R 子目录中找到。
免责声明：我管理 Gurobi 的技术支持。