R中整数变量的非线性优化/规划

7
我想知道有没有人能够建议一些包来解决一个非线性优化问题,可以提供整数变量的最优解?该问题是在一些下限和上限约束条件下最小化具有等式约束的函数。
我已经使用了R中的“nloptr”包来解决非线性优化问题,效果很好,但现在希望将该方法扩展为其中一些变量为整数。从我目前对nloptr的使用和理解来看,它只能返回连续的最优解,而不能返回整数变量的最优解。
我认为这种问题需要使用混合整数非线性规划来解决。
以下是一个适用于nloptr的问题示例:
min f(x) (x-y)^2/y + (p-q)^2/q
so that (x-y)^2/y + (p-q)^2/q = 10.2

where 
x and p are positive integers not equal to 0 
and 
y and q may or may not be positive integers not equal to 0

在R中,这个nloptr代码会像这样:

library('nloptr')

x1 <- c(50,25,20,15)

fn <- function(x) {
  (((x[1] - x[2])^2)/x[2]) + (((x[3] - x[4])^2)/x[4])
  }

heq <- function(x) {
  fn(x)-10.2
}

lower_limit <- c(0,0,0,0)
upper_limit <- c(67.314, 78, 76.11, 86)


slsqp(x1, fn, lower = lower_limit, upper = upper_limit,  hin = NULL, heq = heq, control = list(xtol_rel = 1e-8, check_derivatives = FALSE))

这将输出以下内容:
$par
[1] 46.74823 29.72770 18.93794 16.22137

$value
[1] 10.2

$iter
[1] 6

$convergence
[1] 4

$message
[1] "NLOPT_XTOL_REACHED: Optimization stopped because xtol_rel or xtol_abs (above) was reached."

这是我要找的结果,但如上所述,我需要x和p为整数。
我查看了https://cran.r-project.org/web/views/Optimization.html,其中列出了一些混合整数非线性规划的优秀软件包,但想知道是否有人使用过它们,并认为哪个最适合解决上述问题。
大约7年前在这里发表了一个类似的问题,但最终只得到了指向cran页面的链接,因此认为重新提问是值得的。
非常感谢您的意见。
谢谢,
安德鲁

你能否提供过时的问答链接?也许从Stack Exchange的角度来看,更好的方法是有人对原始问题添加赏金,以获得最新的建议。然后,您可以尝试其中推荐的任何内容,并在经验不满意时更新此问题。 - Mark Neal
1
嗨,马克,感谢您的回复。这是先前问题的链接:https://dev59.com/30_Sa4cB1Zd3GeqP8gZc。当您说要在问题上添加赏金时,您是什么意思?干杯,安德鲁 - andrew_overflow
ps - 要对CVXR进行温和的介绍,请查看此处,但要结合此处描述的更新语法进行阅读。如果这行得通,或者不行,您可能需要在帖子中更新结果。 - Mark Neal
1
嗨,马克,非常感谢您的回复 - 我真的很感激您的时间。我修改了原来的问题,并增加了一些限制条件。 - andrew_overflow
1
一种方法是将此模型视为非凸二次约束模型进行求解。 (请注意,a = x⋅y⋅z 可以通过 b = x⋅y,a = b⋅z 变成二次型)。例如,求解器Gurobi可以处理此问题。 Gurobi具有R接口。 - Erwin Kalvelagen
显示剩余3条评论
6个回答

5
这是一个使用CVXR不起作用的例子,没有一个更简单的目标函数。我怀疑问题即使在约束条件下也不是凸问题,因此需要另一种选择。
#base example from https://cvxr.rbind.io/cvxr_examples/cvxr_gentle-intro/
#install.packages("CVXR")
library(CVXR)

#modified for Stackoverflow integer MIQP ####
#Solves, but terms not normalised by y and q respectively

# Variables minimized over
x <- Variable(1, integer=TRUE)
y <- Variable(1)
p <- Variable(1, integer=TRUE)
q <- Variable(1)

# Problem definition (terms not normalised by y and q respectively)
objective <- Minimize((x - y)^2 + (p - q)^2)
constraints <- list(x >= 0, y >= 0, p >= 0, q >= 0, 
                    x <= 67.314, y <= 78, p <= 76.11, q <= 86)
prob2.1 <- Problem(objective, constraints)

# Problem solution
solution2.1 <- solve(prob2.1)
solution2.1$status
solution2.1$value
solution2.1$getValue(x)
solution2.1$getValue(y)
solution2.1$getValue(p)
solution2.1$getValue(q)


#modified for Stackoverflow integer NLP (not integer) ####
#Does not solve, not convex?

# Variables minimized over
x <- Variable(1)
y <- Variable(1)
p <- Variable(1)
q <- Variable(1)

# Problem definition
objective <- Minimize((x - y)^2/y + (p - q)^2/q)
constraints <- list(x >= 0, y >= 0, p >= 0, q >= 0, 
                    x <= 67.314, y <= 78, p <= 76.11, q <= 86)
prob2.1 <- Problem(objective, constraints)

# Problem solution
solution2.1 <- solve(prob2.1, gp = TRUE)
solution2.1 <- solve(prob2.1, gp = FALSE)
# solution2.1$status
# solution2.1$value
# solution2.1$getValue(x)
# solution2.1$getValue(y)
# solution2.1$getValue(p)
# solution2.1$getValue(q)


#modified for Stackoverflow integer MINLP ####
#Does not solve

# Variables minimized over
x <- Variable(1, integer=TRUE)
y <- Variable(1)
p <- Variable(1, integer=TRUE)
q <- Variable(1)

# Problem definition
objective <- Minimize((x - y)^2/y + (p - q)^2/q)
constraints <- list(x >= 0, y >= 0, p >= 0, q >= 0, 
                    x <= 67.314, y <= 78, p <= 76.11, q <= 86)
prob2.1 <- Problem(objective, constraints)

# Problem solution
solution2.1 <- solve(prob2.1, gp = TRUE)
solution2.1 <- solve(prob2.1, gp = FALSE)
# solution2.1$status
# solution2.1$value
# solution2.1$getValue(x)
# solution2.1$getValue(y)
# solution2.1$getValue(p)
# solution2.1$getValue(q)


#modified for Stackoverflow integer NLP (not integer) ####
#objective multiplied by y*q, Does not solve, not convex?

# Variables minimized over
x <- Variable(1)
y <- Variable(1)
p <- Variable(1)
q <- Variable(1)

# Problem definition
objective <- Minimize((x - y)^2*q + (p - q)^2*y)
constraints <- list(x >= 0, y >= 0, p >= 0, q >= 0, 
                    x <= 67.314, y <= 78, p <= 76.11, q <= 86)
prob2.1 <- Problem(objective, constraints)

# Problem solution
solution2.1 <- solve(prob2.1, gp = TRUE)
solution2.1 <- solve(prob2.1, gp = FALSE)
# solution2.1$status
# solution2.1$value
# solution2.1$getValue(x)
# solution2.1$getValue(y)
# solution2.1$getValue(p)
# solution2.1$getValue(q)

3

ROI 是解决MINLP问题的一个选项。我相信它可以访问一些合适的求解器。它允许访问NEOS(在您问题的另一个答案中有描述)。

如果您想看一下ROI优化是什么样子,请参考这个LP(线性规划)示例:

#ROI example https://epub.wu.ac.at/5858/1/ROI_StatReport.pdf
#install.packages("ROI")
library(ROI)
ROI_available_solvers()

ROI_registered_solvers() #has one solver loaded by default

## Get and load "lpsolve" solver
#install.packages("ROI.plugin.lpsolve", repos=c("https://r-forge.r-project.org/src/contrib",
#                                   "http://cran.at.r-project.org"),dependencies=TRUE)
library(ROI.plugin.lpsolve)
ROI_registered_solvers() #Now it is available to use

## Describe model
A <- rbind(c(5, 7, 2), c(3, 2, -9), c(1, 3, 1))
dir <- c("<=", "<=", "<=")
rhs <- c(61, 35, 31)
lp <- OP(objective = L_objective(c(3, 7, -12)),
         constraints = L_constraint(A, dir = dir, rhs = rhs),
         bounds = V_bound(li = 3, ui = 3, lb = -10, ub = 10, nobj = 3),
         maximum = TRUE)

## When you have a model, you can find out which solvers can solve it
ROI_available_solvers(lp)[, c("Package", "Repository")]

## Solve model
lp_sol <- ROI_solve(lp, solver = "lpsolve")

2

我尝试使用您的示例代码来复制原始问题中的nloptr示例:

#base example from https://cvxr.rbind.io/cvxr_examples/cvxr_gentle-intro/
#install.packages("CVXR")
library(CVXR)

#modified for Stackoverflow integer MINLP (MIQP) ####
#Solves

# Variables minimized over
x <- Variable(1, integer=TRUE)
y <- Variable(1)
p <- Variable(1, integer=TRUE)
q <- Variable(1)
z <- Variable(1)

# Problem definition (terms not normalised by y and q respectively)
objective <- Minimize((x - y)^2 + (p - q)^2 -z)
constraints <- list(x <= 67.314, y <= 78, p <= 76.11, q <= 86, z == 10.2)
prob2.1 <- Problem(objective, constraints)

# Problem solution
solution2.1 <- solve(prob2.1)
solution2.1$status
solution2.1$value
solution2.1$getValue(x)
solution2.1$getValue(y)
solution2.1$getValue(p)
solution2.1$getValue(q)
solution2.1$getValue(z)

然而,我得到的a值为-10.19989,但它应该是0。
> solution2.1$status
[1] "optimal"
> solution2.1$value
[1] -10.19989
> solution2.1$getValue(x)
[1] -1060371
> solution2.1$getValue(y)
[1] -1060371
> solution2.1$getValue(p)
[1] -1517
> solution2.1$getValue(q)
[1] -1517.002
> solution2.1$getValue(z)
[1] 10.2

我无法弄清楚如何使上述内容像nloptr示例一样工作,但确保x和p是整数值!

谢谢,安德鲁


请查看我的更新答案,它实际上并不是一个答案! - Mark Neal

2
由于这个问题属于难以解决的类型,任何通用算法都不能保证对这个确切问题表现良好(参见无免费午餐定理)。事实上,许多算法甚至不太可能收敛于困难问题的全局最优解。有趣的是,在问题空间中进行随机搜索至少最终会收敛,因为最终它会搜索整个空间!
简而言之,尝试枚举问题空间。例如,如果您的四个变量是0到80之间的整数,则只有大约80^4 = ~ 4000万种组合,您可以循环遍历它们。一个中间选项可能是(如果只有两个变量是整数),在给定两个整数的值的情况下,通过优化方法解决剩余两个变量的问题(也许现在它是一个凸问题?),并循环遍历整数值。

0

rneos 是一个包,可以让你访问 neos,这是一个免费的求解服务,并且有众多算法,其中包括适用于 MINLP 问题(如 BONMIN 和 Couenne,请参见列表here)的一些算法。不幸的是,问题需要以 GAMS 或 AMPL 模型格式化。对你来说,这可能意味着学习一些基本的 GAMS,如果是这种情况,也许你可以使用 GAMS 软件see here?免费版本可能足以满足您的需求。它可以作为命令行运行,因此如果需要,您可以从 R 中调用它。

如果你想看看 neos 优化的样子,这里有一个 LP(线性规划)示例:

#rneos example
#from p11 of https://www.pfaffikus.de/talks/rif/files/rif2011.pdf

#install.packages("rneos")
library(rneos)
#library(devtools)
#install_github("duncantl/XMLRPC")
library(XMLRPC)
## NEOS: ping
Nping()
## NEOS: listCategories
NlistCategories()
## NEOS: listSolversInCategory
NlistSolversInCategory(category = "lp")
## NEOS: getSolverTemplate
template <- NgetSolverTemplate(category = "lp", solvername = "MOSEK", inputMethod = "GAMS")
template
#gams file below sourced from https://github.com/cran/rneos/blob/master/inst/ExGAMS/TwoStageStochastic.gms
modc <- paste(paste(readLines("TwoStageStochastic.gms"), collapse = "\n"), "\n")
cat(modc)
argslist <- list(model = modc, options = "", wantlog = "", comments = "")
xmls <- CreateXmlString(neosxml = template, cdatalist = argslist)
## NEOS: printQueue
NprintQueue()
## NEOS: submitJob
(test <- NsubmitJob(xmlstring = xmls, user = "rneos", interface = "", id = 0))
## NEOS: getJobStatus
NgetJobStatus(obj = test)
## NEOS: getFinalResults
NgetFinalResults(obj = test)

-1

R 不是解决这个问题的工具。它需要用于非线性编程的高级功能。我将注意力转向 Julia 语言。我使用了 JuMP 包以及 Juniper 和 Ipopt 算法。它对我的 MINLP 问题效果很好。


1
这是一个主观的看法。你有什么证据来支持这个大胆的陈述吗? - eduardokapp
1
你好@eduardokapp,感谢留言。 我成功地通过Julia可用的库解决了一个问题。请提供一种在R中执行MINLP的方法给我。我是R的忠实粉丝,但我无法解决我的非线性优化问题。 - Ramiro Canchucaja

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接