Настройка линейного оптимизатора с ограничением «или» - PullRequest
Новая
       23

Настройка линейного оптимизатора с ограничением «или»

0 голосов
/ 13 мая 2018

У меня есть большой линейный оптимизатор, и мне нужна помощь в настройке ограничений, чтобы получить то, что я хочу. Мне сложно точно выразить это словами (отсюда и расплывчатое название), поэтому я написал пример, подробности:

  1. Выберите всего 5 предметов, максимизируя стоимость и сохраняя стоимость менее 5 тыс.
  2. Каждый предмет имеет 2 «типа». Они либо помечены type1 = A, B, C, D или E, либо либо type2 = X или Y.
  3. 4 элемента должны быть типа X, 1 должен быть типа Y

Приведенный ниже пример прекрасно работает, но я хочу добавить еще два ограничения, и я не совсем уверен, как это сделать. Два других ограничения:

  1. Я хочу, чтобы каждая оптимизация имела как минимум 2 экземпляра type1. Мне все равно, какой тип кратен или два разных типа кратны (например, 2 A и 2 C), поэтому я думаю об этом как об ограничении "или" (A> 2 ИЛИ> 2> ИЛИ ...). Это вообще выполнимо?
  2. Это может быть немного сложнее: какой бы тип "Y" ни был выбран, я не хочу, чтобы type1 появлялся снова. Так, скажем, элемент Y равен type1 = C, я хочу, чтобы все остальные выбранные элементы не были C. Я думаю, мне нужно добавить еще одну фиктивную матрицу, взаимодействующую type1 и type2

Пример желаемого результата: 

   id type1 type2 value cost 
10 10     B     X    19  865
11 11     C     Y    19 1097 
18 18     D     X    19 1005
40 40     B     X    20  956
45 45     A     X    20  980

ПРИМЕР РАБОТЫ: 

library(lpSolve)
library(dplyr)

# setup df
  id <- 1:50
  type1 <- sample(c('A', 'B', 'C', 'D', 'E'), length(id), replace = T)
  type2 <- sample(c('X', 'X', 'X', 'Y'), length(id), replace = T)
  value <- round(runif(length(id), 0, 20),0)
  cost <- round(runif(length(id), 750, 1250),0)

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

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

# constraints
  totalNum <- 5
  totalCost <- 5000
  totalX <- 4
  totalY <- 1
  rhs <- c(totalNum, totalCost, totalX, totalY)

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

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



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

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

Спасибо за вашу помощь!

...