Как работать с двоичными контурами в линейной оптимизации?

Question

У меня есть две входные матрицы, 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, но не могу понять. Любая помощь очень ценится. Благодаря!

Answer 1

Я считаю, что это действительно MIP, поэтому проблем с выпуклостью не возникает. Если я правильно модель может выглядеть следующим образом:

Эта модель может быть легко расшифрованы в R. Заметим, что LP/MIP решателя не использовать функции для цели и ограничений (в отличие от NLP решателей). В R обычно строятся матрицы с коэффициентами LP.

Примечание: Я должен был сделать ограничения на суммы столбцов намного большими (я использовал 50,60,40).

Answer 2

Основываясь на ответе Эрвина, я могу сформулировать модель, используя lpSolve в R. Однако все еще пытаюсь добавить окончательное ограничение к модели (4-е ограничение в моем вопросе выше). Вот что я могу закодировать до сих пор:

#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 

Любая помощь, которая может получить меня к финишу очень ценится :)

Благодаря