如何在線性優化中使用二元約束？

我有兩個輸入矩陣，dt（10,3）& wt（3,3），我需要用它來找到最優決策矩陣（相同維數），Par（10,3），以便最大化目標功能。下面R代碼裏面將提供一些方向進入的問題（使用的示例這裏輸入） -如何在線性優化中使用二元約束？

#Input Matrices 
dt <- matrix(runif(300),100,3) 
wt <- matrix(c(1,0,0,0,2,0,0,0,1),3,3) #weights 

#objective function  
Obj <- function(Par) { 
    P = matrix(Par, nrow = 10, byrow=F) # Reshape 
    X = t((dt%*%wt)[,1])%*%P[,1] 
    Y = t((dt%*%wt)[,2])%*%P[,2] 
    Z = t((dt%*%wt)[,3])%*%P[,3] 
    as.numeric(X+Y+Z) #maximize 
    }

現在我很努力的按照以下基本條件的問題：

1) Matrix, Par can only have binary values (0 or 1) 
2) rowSums(Par) = 1 (Basically a row can only have 1 in one of the three columns) 
3) colSums(Par[,1]) <= 5, colSums(Par[,2]) <= 6, & colSums(Par[,3]) <= 4 
4) X/(X+Y+Z) < 0.35, & Y/(X+Y+Z) < 0.4 (X,Y,Z are defined in the objective function)

我試圖編碼的約束constrOptim，但不知道如何輸入二進制&整數約束。我正在閱讀lpSolve，但無法弄清楚。任何幫助非常感謝。謝謝！

來源

2016-09-14 Rohit

二元變量是唯一可能。這通常在凸優化設置（混合整數，混合QP，混合QCQP，混合SOCP;以及只有一些研究解決方案可以解決混合SDP）中完成。在非凸面設置中，Couenne＆Knitro沒有太多的功能（問題非常嚴重）。 constrOptim/optim不能做到這一點！ lpSolve只能對MIP執行此操作。因爲我不熟悉R，所以我不能推斷你的問題的凸性。但是，如果X，Y，Z是變量（不是常量），它看起來不好！ – sascha

嗨Sascha，感謝您的迴應。欣賞你的時間。我不太熟悉不同的優化設置。基於Erwin的迴應，我使用lpSolve進行編碼並能夠對模型進行框架化（在一個約束下掙扎）。雖然我現在擔心處理，因爲我必須在一百萬條記錄上運行這個操作。我可能不得不尋找可以處理這些數據的R以外的選項。對此有何想法？謝謝！ – Rohit

我相信這確實是一個MIP所以沒有凸性的問題。如果我是正確的模型可以是這樣的：

該模型可以很容易地轉錄成R.注意，LP/MIP求解器不使用的功能爲目標和約束（而不是NLP求解器）。在R中，通常用LP係數建立矩陣。

注意：我不得不對列數的限制要大得多（我用了50,60,40）。

來源

2016-09-14 22:37:20

感謝Erwin制定模型。我感謝你的時間。我可以在R中使用lpSolve（一個MIP解算器）來轉錄大部分上述內容，但仍然努力在xlim＆ylim（我的問題上面的第四個約束）上應用約束。由於這個約束依賴於目標函數/值（X/Obj <= 0.35等），我不知道如何在模型中添加這個約束。我已經分享了下面的代碼。如果你能從這裏引導，那將是非常棒的。謝謝！ – Rohit

我在模型中添加了變量w和z來完成這些操作。 –

最後能夠編碼第4個約束。謝謝你的幫助！ – Rohit

基於Erwin的回答，我能夠在R中使用lpSolve制定模型。但仍然在向模型中添加最終約束（上述問題中的第四個約束）。下面是我能夠這麼遠代碼：

#input dimension 
r <- 10 
c <- 3 

#input matrices 
dt <- matrix(runif(r*c),r,c) 
wt <- matrix(c(1,0,0,0,2,0,0,0,1),3,3) #weights 

#column controller 
c.limit <- c(60,50,70) 

#create structure for lpSolve 
ncol <- r*c 
lp.create <- make.lp(ncol=ncol) 
set.type(lp.create, columns=1:ncol, type = c("binary")) 

#create objective values 
obj.vals <- as.vector(t(dt%*%wt)) 
set.objfn(lp.create, obj.vals) 
lp.control(lp.create,sense='max') 

#Add constraints to ensure sum of parameters for every row (rowSum) <= 1 
for (i in 1:r){ 
add.constraint(lp.create, xt=c(1,1,1), 
      indices=c(3*i-2,3*i-1,3*i), rhs=1, type="<=") 
} 

#Add constraints to ensure sum of parameters for every column (colSum) <= column limit (defined above) 
for (i in 1:c){ 
add.constraint(lp.create, xt=rep(1,r), 
      indices=seq(i,ncol,by=c), rhs=c.limit[i], type="<=") 
} 

#Add constraints to ensure sum of column objective (t((dt%*%wt)[,i])%*%P[,i) <= limits defined in the problem) 
#NOT SURE HOW TO APPLY A CONSTRAINT THAT IS DEPENDENT ON THE OBJECTIVE FUNCTION 

solve(lp.create) 
get.objective(lp.create) #20 
final.par <- matrix(get.variables(lp.create), ncol = c, byrow=T) # Reshape

任何幫助，可以讓我到終點，非常感謝:)

感謝，如果求解器支持這些

來源

2016-09-15 14:16:21 Rohit

如何在線性優化中使用二元約束？

回答

相關問題