Создание фиктивных переменных взаимодействия для ограничения lpSolve - PullRequest
Новая
       26

Создание фиктивных переменных взаимодействия для ограничения lpSolve

0 голосов
/ 08 июня 2018

У меня есть модель линейного программирования, которую я пытаюсь оптимизировать, и мне нужна помощь в настройке ограничений, чтобы получить то, что я хочу.Высокий уровень: я хочу выбирать элементы, только если их «тип» не «конфликтует» с определенным «типом» другого элемента.Более подробное объяснение на примере:

  1. Выберите всего 6 предметов, максимизируя стоимость и сохраняя стоимость ниже 17 тыс.
  2. Каждый предмет имеет 3 "типа".Они помечены type1 = X или Y, type2 и type3 = A, B или C. Для целей этого примера я пометил type2 = A2, B2, C2 и type3.= A3, B3, C3.
  3. 4 элемента должны быть типа X, 2 должны быть типа Y.

Конкретное ограничение, которое я пытаюсь установить, заключается в том, что все, что Type3Если выбранные переменные «Y» в конечном итоге становятся («A3», «B3», «C3»), Type2 из переменных «X» не могут соответствовать этой букве.Например, если Y 'B3', то X могут быть 'A2' или 'C2'.Если один Y - это «C3», а другой - «A3», то все X должны быть «B2».Два примера приемлемых решений: 

   id type1   type2 type3 value cost 
 3  3     Y     C2    A3   28   240
10 10     X     B2    C3   30   327
11 11     Y     A2    C3   28   350
18 18     X     B2    C3   29   372
40 40     X     B2    B3   29   338
45 45     X     B2    A3   29   277

   id type1   type2 type3 value cost 
 3  3     Y     C2    C3   28   240
10 10     X     B2    C3   30   327
11 11     Y     A2    C3   28   350
18 18     X     B2    C3   29   372
40 40     X     B2    B3   29   338
45 45     X     A2    A3   29   277

Мой текущий код работает только тогда, когда оба Y различны type3. Для этого я добавил вектор взаимодействия, Y_3X_2, где, если type3 соответствует Y, затем он получает значение 10000, а если type2 соответствует X, то он получает значение 1. Каждый вектор должен быть <= 100000, поэтому можно выбрать только один из этих Y или несколько X,<strong> Мне нужна помощь, чтобы оба Y были одинаковыми type3.

Рабочий пример 

library(dplyr)
library(lpSolve)

id <- 1:50
value <- round(runif(length(id), 10, 30),0)
cost <- round(runif(length(id), 200, 400),0)
type1 <- sample(c(rep('X', 3), 'Y'), length(id), replace = T)
type2 <- sample(c('A2', 'B2', 'C2'), length(id), replace = T)
type3 <- sample(c('A3', 'B3', 'C3'), length(id), replace = T)

df <- data.frame(id, value, cost, type1, type2, type3) %>% 
  mutate(selected = 1)

# Attach dummy vars
type1Dummy <- as.data.frame.matrix(table(df$id, df$type1))
type2Dummy <- as.data.frame.matrix(table(df$id, df$type2))
type3Dummy <- as.data.frame.matrix(table(df$id, df$type3))
df <- cbind(df, type1Dummy, type2Dummy, type3Dummy) 

# Interaction dummy vars
YA3XA2 <- ifelse(df$Y + df$A3 == 2, 10000,
                 ifelse(df$X + df$A2 == 2, 1,
                        0))
YB3XB2 <- ifelse(df$Y + df$B3 == 2, 10000,
                 ifelse(df$X + df$B2 == 2, 1,
                        0))
YC3XC2 <- ifelse(df$Y + df$C3 == 2, 10000,
                 ifelse(df$X + df$C2 == 2, 1,
                        0))

df <- cbind(df, YA3XA2, YB3XB2, YC3XC2)

# constraints
totalNum <- 6
totalCost <- 17000
totalX <- 4
totalY <- 2
intConXYA <- 10000
intConXYB <- 10000
intConXYC <- 10000
rhs <- c(totalNum, totalCost, totalX, totalY, intConXYA, intConXYB, intConXYC)

# Direction vector
numDir <- '=='
costDir <- '<='
xDir <- '=='
yDir <- '=='
intConA <- '<='
intConB <- '<='
intConC <- '<='
dir <- c(numDir, costDir, xDir, yDir, intConA, intConB, intConC)

# Setup opt
obj <- df$value
mat <- t(data.frame(df$selected, df$cost, df$X, df$Y, df$YA3XA2, df$YB3XB2, df$YC3XC2))


# Solver Setup
sol <- lpSolve::lp("max",   
                   objective.in = obj,
                   const.mat    = mat,
                   const.dir    = dir,
                   const.rhs    = rhs,
                   all.bin      = T
)

df$solver <- sol$solution
dfSolved <- df[df$solver == 1,]
dfSolved

Пошаговое руководствос кодом:

  • Создание фрейма данных с идентификатором, значением, стоимостью, тип1 / 2/3
  • Создание фиктивных переменных.Это необходимо для того, чтобы оптимизатор выбрал только 4 X и 2 Y, а также для установки фиктивной переменной взаимодействия.
  • Type1Dummy создаст 2 столбца.Df $ X == 1, если Type1 == 'X', df $ Y == 1, если Type2 == 'Y'.
  • Type2Dummy создаст 3 столбца.Df $ A2 == 1, если type2 == 'A2' и т. Д.
  • Type3Dummy создаст 3 столбца, аналогичных Type2Dummy
  • с фиктивными переменными на месте.Создайте 3 фиктивные переменные взаимодействия, YA3XA2 по сути читается так: if type1 == 'Y' & type3 == 'A3' |type1 == 'X' & type2 == 'A2' THEN присвоить значение, иначе 0. Значения, которые должны быть назначены: 10000, если type1 == 'Y', и 1, если type1 == 'X'.
  • Назначить ограничения для правой руки.Обратите внимание, что ограничения для макетов взаимодействия равны 10000. Это означает, что ЛИБО 1 Y может быть выбрано для этого конкретного типа 3, или любое число X может быть выбрано для этого конкретного Y2, но они никогда не могут быть выбраны оба.Если выбран Y, то сумма равна 10000, и больше ничего нельзя выбрать.
  • Моя проблема в в том, что указанное ограничение работает «слишком правильно».Он успешно предотвращает появление Y определенного типа 3 с X определенного типа 2, но это также означает, что у меня не может быть 2 Y того же типа 3.Если я увеличу ограничение до 20000, то оно разрешит 2 Y того же типа 3, но также позволит 1 Y типа 3 и 4 X этого типа 2 (сумма = 10004, что <20000). </li>
...