как посчитать количество отдельных элементов в задаче линейного программирования - PullRequest
0 голосов
/ 12 декабря 2018

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

Этопост, который я мог найти, который мне показался наиболее близким:

https://stats.stackexchange.com/questions/136608/constrained-assignment-problem-linear-programming-genetic-algorithm-etc

В этом случае подсчитываются «предметы», используемые центры снабжения.Я пытаюсь понять, подходит ли подход, предложенный в приведенном выше посте, для моих целей.

В ответе пользователя «TAS», пример - 3 магазина по 2 центрам снабжения, и идея такова (A) назначить один (и только один) центр снабжения каждому магазину так, чтобы: (B) пройденное расстояние было минимальным, (C) ни один центр снабжения не должен поставлять больше заданного максимального количества магазинов (в данном случае 3, т.е.без ограничений) и (D) максимальное общее количество используемых центров снабжения ограничено (в данном случае до 2).

Я попытался восстановить способ постановки задачи, начиная с набора данных, подобногоВ моем случае это было бы.

df <- cbind(expand.grid(shop=1:3,supply=1:2),distance=c(2.8,5.4,1.4,4.2,3.0,6.3))

df["Entry"] <- 1:dim(df)[[1]]

shop.mat <- table(df$shop,df$Entry)
shop.mat

    1 2 3 4 5 6
  1 1 0 0 1 0 0
  2 0 1 0 0 1 0
  3 0 0 1 0 0 1

supply.mat <- table(df$supply,df$Entry)
supply.mat

    1 2 3 4 5 6
  1 1 1 1 0 0 0
  2 0 0 0 1 1 1

N_supply <- dim(supply.mat)[[1]]
N_shop <- dim(shop.mat)[[1]]
N_entry <- dim(df)[[1]]

Вектор решения будет иметь длину N_entry + N_supply, и каждая строка матрицы ограничений должна иметь одинаковую длину.

constr.mat <- NULL
dir <- NULL
rhs <- NULL

(A) решается путем ограничения каждой строки в shop.mat на == 1:

constr.mat <- rbind(constr.mat,cbind(shop.mat,matrix(0,N_shop,N_supply)))
dir <- c(dir,rep("==",N_shop))
rhs <- c(rhs,rep(1,N_shop))

(B) адресуется путем задания целевого вектора для расстояния для каждой записи и 0 для каждогомагазин (потому что естьне нужно тратить время на добавление еще одного центра снабжения, хотя в действительности это может быть):

obj <- c(aggregate(distance~Entry,df,c)[["distance"]],rep(0,N_supply))

(C) решается путем перестановки уравнения и превращения его в ограничение <= 0: </p>

constr.mat <- rbind(constr.mat,cbind(supply.mat,-diag(table(df$supply))))
dir <- c(dir,rep("<=",N_supply))
rhs <- c(rhs,rep(0,N_supply))

(D) решается путем добавления ограничения <= 2: </p>

constr.mat <- rbind(constr.mat,c(rep(0,N_entry),rep(1,N_supply)))
dir <- c(dir,"<=")
rhs <- c(rhs,2)

Затем проблему можно решить с помощью lpSolve:

require(lpSolve)
sol <- lp("min", obj, constr.mat, dir, rhs, all.bin = TRUE,num.bin.solns = 1, use.rw=FALSE, transpose.constr=TRUE)

sol$solution
[1] 1 0 1 0 1 0 1 1

sol$objval
[1] 7.2

selected_Entry <- dimnames(shop.mat)[[2]][as.logical(sol$solution[1:N_entry])]
selected_Entry
[1] "1" "3" "5"

df[df$Entry %in% selected_Entry,]
  shop supply distance Entry
1    1      1      2.8     1
3    3      1      1.4     3
5    2      2      3.0     5

Я вижу, чтов этом конкретном случае вектор решения вынужден (с помощью ограничений (C)) иметь «1» в любой из переменных «предложения», для которых выбрана хотя бы одна соответствующая запись.Если бы это было не так, суммы строк для ограничений (C) были бы> 0.

Но: предположим, что расстояния были разными и только центр снабжения 1 был выбран для всех 3 магазинов.Что помешало бы переменной вектора решения для центра снабжения 2 установить значение «1»?

Текущее решение дает:

constr.mat %*% sol$solution
  [,1]
1    1
2    1
3    1
1   -1
2   -2
     2

Но это альтернативное решение все равно будет отвечать всем ограничениям:

constr.mat %*% c(1,1,1,0,0,0,1,1)
  [,1]
1    1
2    1
3    1
1    0
2   -3
     2

, несмотря на то, что центр поставщиков 2 не использовался.

В этом случае это не повлияет на решение, так как затраты на включение центров снабжения не связаны (соответствующаяэлементами целевого вектора являются 0).

Но если бы я хотел получить из решения подсчет различных используемых центров снабжения , я думаю, что это не сработало бы.

Несколько лет назад я попросил совета по этой проблеме на другом форуме, и кто-то немедленно дал мне решение, однако сказал, что он / она «не был уверен, что это было наиболее эффективным».

Это былследующее: все то же, что и выше, а затем для каждого из центров снабжения добавьте к constr.mat в два раза больше supply.mat, дополненное отрицательной диагональной матрицей числазаписей на центр снабжения, ограничив первые N_supply добавленных строк быть <= 0, а последние <code>N_supply строк быть> = 1 - диагональ упомянутой выше диагональной матрицы.

constr.mat <- rbind(constr.mat,cbind(supply.mat,-diag(table(df$supply))),cbind(supply.mat,-diag(table(df$supply))))
dir <- c(dir,rep("<=",N_supply),rep(">=",N_supply))
rhs <- c(rhs,rep(0,N_supply),1-table(df$supply))

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

Например, оригинальное решение все еще будет работать:

paste(t(unlist(constr.mat %*% sol$solution)),dir,rhs)
 [1] "1 == 1"   "1 == 1"   "1 == 1"   "-1 <= 0" 
 [5] "-2 <= 0"  "2 <= 2"   "-1 <= 0"  "-2 <= 0" 
 [9] "-1 >= -2" "-2 >= -2"

[Кстати, я бы не знал, как превратить это в оцененный логический вектор;Любая идея?]

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

paste(t(unlist(constr.mat %*% c(1,1,1,0,0,0,1,1))),dir,rhs)
 [1] "1 == 1"   "1 == 1"   "1 == 1"   "0 <= 0"  
 [5] "-3 <= 0"  "2 <= 2"   "0 <= 0"   "-3 <= 0" 
 [9] "0 >= -2"  "-3 >= -2"

(последнее ограничение не будет выполнено).

Q1 Считаете ли вы, что вышеизложенное имеет смысл, т. Е. Правда ли, что нам нужны дополнительные строки ограничений, которые я упомянул, чтобы убедиться, что переменные «питания» в векторе решения установлены правильно, илиЯ не прав?

Q2 Можете ли вы придумать более эффективный способ подсчета случаев появления различных предметов в таких задачах (пример здесь небольшой, но я часто имею дело с ОЧЕНЬ крупными,где добавление стольких ограничений не помогает, несмотря на все проблемы в мире)?

Спасибо!


Примечание: этот вопрос был изначально опубликованв другом сообществе.Я удалил его оттуда.


РЕДАКТИРОВАТЬ после просмотра страницы в Википедии по 'Проблема размещения некапитализированного объекта' , упомянутая в оригинальном сообщении, которое я связал выше.

На самом деле - это стоимость, связанная с открытием нового центра снабжения, поэтому вектор цели должен иметь не 0 в конце, а некоторую стоимость ($ f_i $ в формулировке Википедии).
Только тогда проблема $ \ sum_iy_i $, не всегда являющаяся числом открытых центров снабжения, исчезает, потому что ограничения $ \ sum_jx_ {i, j} \ le m \ cdot y_i $ по-прежнему гарантируют, что всякий раз, когда данный центриспользуется, соответствующий $ y_i $ равен 1;и не будет необходимости в других условиях, которые я наложил, потому что теперь есть стоимость, связанная с установкой 1 для каждого $ y_i $, поэтому только строго необходимые $ y_i $ s будут установлены в 1.

Короче говоря, если вектор цели построен правильно, с затратами на каждый центр снабжения, я могу обойтись без нескольких ограничений.
Фактически, в зависимости от значения для цены открытия центра снабжения, ограничение на максимальный итогчисло центров может быть даже заменено.
Тогда было бы интересно оценить предложение, сделанное в дискуссии в Википедии, а именно разделить ограничения «большого М» на несколько меньших.Если это правда, что это облегчает вычислительное решение проблемы, почему бы и нет ...

1 Ответ

0 голосов
/ 02 июля 2019

РЕДАКТИРОВАТЬ: алгоритм исправлен.

У меня была похожая проблема, я хотел минимизировать количество различных значений в решении.Вот как я придумал ответ, чтобы математически рассчитать количество различных элементов.

Предположим, у нас есть следующий набор:

11 12 13 11 11

Мы можем видеть, что втам (11, 12 и 13).Ниже приводится способ его вычисления.Напишите числа в треугольной матрице следующим образом:

11 12 13 11 11    row=0
   12 13 11 11    row=1
      13 11 11    row=2
         11 11    row=3

, если я получу разницу 11 и 12, и назначу двоичную переменную

1, если | a1 - a2 |! = 0

0, если | a1 - a2 |== 0

тогда у меня есть следующее:

1 1 0 0   --> 0
  1 1 1   --> 1
    1 1   --> 1
      0   --> 0

1 + 1 + (extra 1) = 3

если число отличается, то его строка должна быть все 1 с.Таким образом, в приведенном выше случае у нас есть 2 строки с полными 1, что означает, что у нас есть 2 числа, которые отличаются от первого числа.Итак, всего у нас есть 3.

Теперь для перевода в линейное программирование:

Предположим:

Variables = a(1), a(2), a(3), a(4), ..., a(n)
Binary Variables b(i,j) where i,j in [0...n]
Binary Variable c(i) where i in [0...n]

Линейная программа будет:

obj = 1
for i in range(0, n):
  for j in range(i+1, n):
    # This is |a(i) - a(j)| part
    addConstr( b(i,j) * BigM >= a(i) - a(j)) 
    addConstr( b(i,j) * BigM >= -(a(i) - a(j)))
  # So here c(i) will be 0 if there is any 0 in the row otherwise it is 1.
  addConstr(c(i) * BigM >= sum(b(i,j) for all j) - (n-i))
  obj = obj + c(i)
Minimize(Sum(obj))
...