Нужен алгоритм для поиска минимальной стоимости в подмножестве элементов

Question

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

например: - Представьте себе, что A B C - это розничные торговцы, а W X Y Z - это продукты, целью которых является минимизация посещений и снижение цены.

A B C 
W 4 9 2 
X 1 3 4 
Y 9 3 9 
Z 7 1 1 

So it appears my top two choices are 
a) B:{XYZ} - 7 C:{W} - 2 
b) C:{WXZ} - 7 B:{Y} - 3 

So a) is picked because since it has a lower cost, i.e 9. 

Эта проблема кажется похожей на вершинную оболочку и другие алгоритмы линейного программирования, но я не могу определить правильный.

Update:

Кажется, мне нужно добавить дополнительную переменную. Введение t. Если расходы на посещение наименьшего числа розничных продавцов и ближайших меньших -> t, выбирается следующий первый.

Continuing with the example. 

say t = 5, 

The largest subset containing all elements would be B:{WXYZ} with a cost of 16. 
The next largest subset(s) is B:{XYZ} - 7 C:{W} - 2 with a cost of 9. 

t = 16 - 9 > 5. So we pick B:{XYZ} - 7 C:{W} - 2 

but if we did A:{X}, B:{Y}, C:{WZ} - 5, t = 9 - 5 < 5. 

So B:{XYZ} - 7 C:{W} - 2 is picked 

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

Answer 1

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

Несколько целей довольно распространены в этих типах задач программирования Integer. See MCDM. Чтобы решить эту проблему, вам нужно иметь два видов затрат (вы в настоящее время есть только один.)

1. Стоимость покупки продукт р от розничного г (который вы указали) C_rp
2. Стоимость посещения магазина: C_r

Интуиция: Если C_r очень высока, мы купим все продукты у одного продавца. Если C_r невелик, мы переходим к нескольким ритейлерам и покупаем у тех, кто продает его наиболее дешево.

Ваша проблема может быть смоделирована как вариант «Assignment Problem». Кроме того, прочитайте на так называемом fixed-charge transportation problems (FCTP), если вам нужно больше ссылок. (Там фиксированная плата для посещения розничного раз.)

Так к формулировке программирования Integer:

Решение Переменные

Binary 
    X_rp = if product p is purchased from retailer r, 0 otherwise 
    Y_r = 1 if retailer r is visited, 0 otherwise 

Цель функции

Min C_rp X_rp + C_r Y_r 

Ограничения

(Sum over r) X_rp = 1 for all p (Every product must be bought from some retailer) 

Далее, мы должны убедиться, что Y_r является один, если даже один из X_rp является 1 для для этого продавца. Обычно мы прибегаем к методу Big M, но в этой проблеме это проще.

X_rp <= Y_r for all p, for all r. 

Если какой-либо из X переменных становится 1, что вынуждает Y_r стать 1. Модель будет платить цену C_r.

Чтобы решить, вы можете использовать любой решатель LP. Хорошей новостью является то, что проблема имеет свойство целостности, что означает, что целые решения естественным образом возникают даже при использовании методов линейного программирования.

Надеюсь, что помогает.