Линейное программирование - уникальное количество категорий - PullRequest
Новая
       0

Линейное программирование - уникальное количество категорий

1 голос
/ 19 октября 2019

TL; DR: Я пытаюсь найти самый дешевый набор предметов в коллекции, которые удовлетворяют определенным линейным ограничениям. Тем не менее, каждый элемент может быть частью нескольких «категорий», и я также хочу иметь сочетание этих уникальных категорий, и я не совсем уверен, может ли это быть реализовано способом LP или нет, и в случае, как к нему подойти.

Пример - часть 1 Допустим, у меня есть 7 предметов, которые имеют разные затраты и разные значения, связанные с ними. 

library(tidyverse)
library(lpSolve)

# Fake data
kd = tibble(
  Item = 1:7,
  Cost = c(1, 1, 1, 1, 2, 3, 4),
  Value =c(1, 1, 3, 4, 6, 3, 2),
  Type = c("A", "A", "A", "B", "C", "D", "E")
)

Я хочу выбрать 3 из этих элементов, чтобы стоимость была минимизирована, а их значение>> 5. Я легко могу сделать это с помощью lp с помощью следующего кода: 

# Objective function
knapsack.obj = kd$Cost

# Constraints
knapsack.con = matrix(
  c(
    rep(1, nrow(kd)), 
    kd$Value 
  ),
  nrow = 2, byrow = TRUE
)
knapsack.dir = c("==", ">=")
knapsack.rhs = c(3, 5)

# Solve
knapsackSolution = lp("min", knapsack.obj, knapsack.con, knapsack.dir, knapsack.rhs, all.bin = TRUE) 

# Results
kd[knapsackSolution$solution == 1, ]

Как и ожидалось, это возвращает элементы 1, 2 и 3, которые имеют объединенное значение = 5 и, очевидно, сводят к минимуму цену.

Пример - часть 2

дополнительная сложность, которую я не совсем знаю, как решить сейчас, это добавить код, чтобы убедиться, что выбранные предметы принадлежат как минимум к 2 уникальным категориям. Теперь решение, которое я ожидал бы, это пункты 1, 2 и 4 (или 1, 3 и 4), которые по-прежнему имеют совокупную стоимость 3 и значение 6 (или 8), равное> = 5, но не все "Aэлементы, но содержат также элемент 4, который является элементом "B".

Есть идеи о том, как реализовать это в платформе LP?

Ответы [ 3 ]

1 голос
/ 22 октября 2019

Математическая модель

Если мы введем матрицу ноль-один (данные) 

Category[i,j] = 1  if item i has type j
                0  otherwise

и двоичную переменную: 

y[j] = 1 if an item with type j is selected
       0 otherwise

, мы можем разработать простуюматематическая модель:

enter image description here

Символы синего цвета представляют данные, а красные - переменные решения.

Обратите внимание, что переменная y[j] может быть смягчен, чтобы быть непрерывным между 0 и 1.

Преимущество первой записи математической модели состоит в том, что ее легче рассуждать, чем связка кода R (по крайней мере, для меня).

Реализация

Я использую OMPR здесь по двум причинам:

  • Прямой способ реализации модели на основе уравнений. Мы остаемся ближе к математической модели.
  • Доступ к лучшим решателям, чем LpSolve.

Вот код R: 

library(tidyverse)
library(ROI)
library(ROI.plugin.symphony)
library(ompr)
library(ompr.roi)

# Fake data
kd = tibble(
  Item = 1:7,
  Cost = c(1, 1, 1, 1, 2, 3, 4),
  Value =c(1, 1, 3, 4, 6, 3, 2),
  Type = c("A", "A", "A", "B", "C", "D", "E")
)

Types <- c("A","B","C","D","E")
Category <- 1*outer(kd$Type,Types,FUN="==")
Type <- 1:length(Types)

numItems <- 3
MinValue <- 5
MinItems <- 2

m <- MIPModel() %>%
  add_variable(x[i], i=kd$Item, type="binary") %>%
  add_variable(y[j], j=Type, type="binary") %>%
  add_constraint(sum_expr(x[i], i=kd$Item) == numItems) %>% 
  add_constraint(sum_expr(kd$Value[i]*x[i], i=kd$Item) >= MinValue) %>% 
  add_constraint(y[j] <= sum_expr(Category[i,j]*x[i], i=kd$Item), j=Type) %>% 
  add_constraint(sum_expr(y[j], j=Type) >= MinItems) %>% 
  set_objective(sum_expr(kd$Cost[i]*x[i], i=kd$Item),"min") %>% 
  solve_model(with_ROI(solver = "symphony", verbosity=1))

cat("Status:",solver_status(m),"\n")
cat("Objective:",objective_value(m),"\n")
m$solution

Возможно, самая сложная частьВот расчет матрицы категорий.

Решение

Решение выглядит так: 

Status: optimal 
Objective: 3 
x[1] x[2] x[3] x[4] x[5] x[6] x[7] y[1] y[2] y[3] y[4] y[5] 
   1    1    0    1    0    0    0    1    1    0    0    0
0 голосов
/ 19 октября 2019

На самом деле нам не нужно заставлять решение иметь k-1 или меньше элементов из каждой группы. Вместо этого мы можем заставить каждую группу иметь максимум g_i-1 элементов, где g_i - это количество элементов в каждой группе.

Вот реализация: 

library(purrr)
library(lpSolve)
library(fastmatch)

# Fake data
  kd = tibble(
  Item = 1:7,
  Cost = c(1, 1, 1, 1, 2, 3, 4),
  Value =c(1, 1, 3, 4, 6, 3, 2),
  Type = c("A", "A", "A", "B", "C", "D", "E")
)

# number of elements to choose
k = 3

  type_match <- fmatch(kd$Type, unique(kd$Type))
  unique_cat <- unique(type_match)

  add_con <- map(unique_cat,function(x) {
    type_match[type_match != x] = 0
    type_match[type_match > 0] = 1
    return(type_match)}) %>% 
    do.call(rbind,.)

  knapsack.obj = kd$Cost
  knapsack.con = 
    rbind(
      rep(1, nrow(kd)), 
      kd$Value,
      add_con
    )
rhs_add <- apply(add_con, 1, function(x) ifelse(sum(x)>1,sum(x) - 1,1))

  knapsack.dir = c("==", ">=", rep("<=",length(rhs_add)))
  knapsack.rhs = c(k, 5, rhs_add)

  knapsackSolution = lp("min", 
                        knapsack.obj, 
                        knapsack.con, 
                        knapsack.dir, 
                        knapsack.rhs, 
                        all.bin = TRUE) 
  knapsackSolution$solution
>   knapsackSolution$solution
[1] 1 1 0 1 0 0 0
0 голосов
/ 19 октября 2019

Поскольку мы знаем, что в решении должно быть k = 3 элемента, в каждой группе должно быть k-1 или меньше элементов, что требует использования как минимум 2 групп. 

incid <- +outer(unique(kd$Type), kd$Type, "==")
ntypes <- nrow(incid)

knapsack.con = rbind(
    rep(1, nrow(kd)), 
    kd$Value,
    incid)

k <- 3
knapsack.dir = c("==", ">=", rep("<=", ntypes))
knapsack.rhs = c(k, 5, rep(k-1, ntypes))
res <- lp("min", knapsack.obj, knapsack.con, knapsack.dir, knapsack.rhs, all.bin = TRUE) 

res$status
## [1] 0

res$solution
## [1] 1 1 0 1 0 0 0

Упрощение

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

res2 <- lp("min", knapsack.obj, knapsack.con[1:3, ], knapsack.dir[1:3], 
  disknapsack.rhs[1:3], all.bin = TRUE) 

res2$status
## [1] 0

res2$solution
## [1] 1 1 0 1 0 0 0

Обобщение

Как мы обсуждали в комментариях, для обобщения давайте предположим, что мы хотим иметь как минимум 3 разные категории в решении, а не 2. В этих конкретных данных нам может потребоваться просто, чтобы решение имело не более 1 из каждой категории, но вВ общем, это не сработает, поэтому давайте возьмем все комбинации групп 2 одновременно и приведем ограничения, показанные ниже. 5 - общее количество категорий в задаче, а 2 - на единицу меньше, чем количество категорий, необходимых для решения. 

combos <- combn(5, 2, function(x) colSums(incid[x, ]))

Для каждого из этих ограничений, то есть для каждой строки в комбинациях, мы требуемчтобы оно было меньше или равно 2, чтобы исключить любое решение, имеющее только 1 или 2 категории. Затем мы строим LP аналогичным образом, как и до добавления оставшихся ограничений.

...