lpSolveAPI에 개수 제한 추가 R

Question

최적화에 뛰어 들고 lpSolveAPI 패키지를 사용하고 있습니다. 예제에서는 간단한 설정을 보여줍니다.

데이터 (모든 행이 다른 변수를 보유) :

dput(test.df) 
    structure(list(objective = c(-0.162235888601422, -0.168597233981057, 
    -0.165558234725657, -0.156096491294958, -0.15294764940114), constrain1 = c(1.045, 
    1.259, 1.792, 2.195, 2.802)), .Names = c("objective", "constrain1" 
    ), row.names = c(NA, -5L), class = "data.frame") 

library(lpSolveAPI) 

5 개 변수 (test.df 행)으로, 빈 모델을 만들어 내 목표를 극대화하고자합니다.

test.lp <- make.lp(0, NROW(test.df)) 
set.objfn(test.lp, test.df$objective) 
lp.control(test.lp,sense='max') 

몇 가지 제약 조건을 추가하십시오.

add.constraint(test.lp, test.df$constrain1, "=", 2) 
add.constraint(test.lp, rep(1, nrow(test.df)), "=", 1) 
set.bounds(test.lp, upper = rep(0.5, nrow(test.df))) 
set.bounds(test.lp, lower = rep(0, nrow(test.df))) 
RowNames <- c("constraint1", "constraint2") 
ColNames <- paste0("var", seq(1, nrow(test.df))) 
dimnames(test.lp) <- list(RowNames, ColNames) 

저는 하나의 변수를 사용하여 해결할 수있는 onemore 제약 조건을 만들고 싶습니다. 따라서 2로 설정하면 2 개의 변수로 최적의 솔루션을 만들 수 있습니다. 나는 set.type = "binary"을 시도했지만 성공하지 못했습니다.

Answer 1

여기서 @ErwinKalvelagen에서 언급 한 기술을 R의 lpSolveAPI에 적용하는 방법을 보여주는 코드입니다. 주요 포인트는 이진 변수를 문제에 추가하는 것입니다.

library(lpSolveAPI) 
fun1 <- function(n=3) { 
    nx <- 5 

    # set up lp 
    lprec <- make.lp(0, 2*nx) # one var for the value x(i) and one var y(i) binary if x(i) > 0 
    set.objfn(lprec, c(-0.162235888601422, -0.168597233981057, -0.165558234725657, -0.156096491294958, -0.15294764940114, rep(0, nx))) 
    lp.control(lprec,sense='max') 
    set.type(lprec, columns=seq(nx+1,2*nx), "binary") # y(i) are binary vars 

    # add constraints as in the question 
    set.bounds(lprec, upper=rep(0.5, nx), columns=seq(1,nx)) # lpsolve implicitly assumes x(i) >= 0, so no need to define bounds for that 
    add.constraint(lprec, c(1.045, 1.259, 1.792, 2.195, 2.802, rep(0, nx)), "=", 2) 
    add.constraint(lprec, c(rep(1, nx), rep(0, nx)), "=", 1) 

    # additional constraints as suggested by @ErvinKarvelagen 
    for (i in seq(1,nx)) add.constraint(lprec, xt=c(1, -0.5), type="<=", rhs=0, indices=c(i, nx+i)) # x(i)<=y(i)*0.5 
    add.constraint(lprec, c(rep(0,nx), rep(1,nx)), "<=", n) # sum(y(i))<=2 (if set to 3, it finds a solution) 

    # solve and print solution 
    status <- solve(lprec) 
    if(status!=0) stop("no solution found, error code=", status) 
    sol <- get.variables(lprec)[seq(1, nx)] 
    return(sol) 
} 

그러나 x (i)가 두 개만 0 일 것을 요구하면 문제가 발생하지 않습니다. 주어진 제약 조건을 충족하려면 최소한 세 가지가 필요합니다. (이것은 매개 변수 n에 의해 수행됩니다). 또한 set.row은 장기적으로 add.constraint보다 효율적입니다.

@ ErwinKalvelagen의 두 번째 설명을 정교하게 만드는 또 다른 접근법은 가능한 5 가지 변수 조합에서 모든 n을 취하여이 n 변수를 풀어내는 것입니다. R 코드로 변환이 그러나 최초의 솔루션이 훨씬 빠르고,

두 코드

fun2 <- function(n=3) { 
    nx <- 5 

    solve_one <- function(indices) { 
     lprec <- make.lp(0, n) # only n variables 
     lp.control(lprec,sense='max') 
     set.objfn(lprec, c(-0.162235888601422, -0.168597233981057, -0.165558234725657, -0.156096491294958, -0.15294764940114)[indices]) 
     set.bounds(lprec, upper=rep(0.5, n)) 
     add.constraint(lprec, c(1.045, 1.259, 1.792, 2.195, 2.802)[indices],"=", 2) 
     add.constraint(lprec, rep(1, n), "=", 1) 
     status <- solve(lprec) 
     if(status==0) 
      return(list(obj = get.objective(lprec), ind=indices, sol=get.variables(lprec))) 
     else 
      return(list(ind=indices, obj=-Inf)) 
    } 

    sol <- combn(nx, n, FUN=solve_one, simplify=FALSE) 
    best <- which.max(sapply(sol, function(x) x[["obj"]])) 
    return(sol[[best]]) 
} 

가 동일한 솔루션을 반환 될 것입니다 :

library(microbenchmark) 
microbenchmark(fun1(), fun2(), times=1000, unit="ms") 
#Unit: milliseconds 
# expr  min  lq  mean median  uq  max neval 
# fun1() 0.429826 0.482172 0.5817034 0.509234 0.563555 6.590409 1000 
# fun2() 2.514169 2.812638 3.2253093 2.966711 3.202958 13.950398 1000 

Answer 2

난 0이 아닌 변수 x(i)의 수를 제한하는 제약 조건을 추가하고자한다고 생각합니다. 실제로 카운팅은 LP로는 수행 할 수 없지만 MIP로 공식화 할 수 있습니다.

표준 배합으로 y(i) 이진 변수를 소개하는 것입니다 :

x(i) <= y(i)*xup(i)  (implication: y(i)=0 => x(i)=0) 
sum(i, y(i)) <= 2  
0 <= x(i) <= xup(i)  (bounds) 
y(i) in {0,1}   (binary variables) 

더 큰 문제를 들어이 훨씬 더 효율적 각각의 가능한 조합을 해결하는 것보다 할 수 있습니다. 중 N은 그렇게 나쁜 것은 아닙니다 : N choose k = N*(N-1)/2 가능한 조합.