Комбинаторная оптимизация с несколькими ограничениями

Вы можете сформулировать свою проблему как целочисленную программу 0-1 и решить ее с помощью GLPK или другого решателя линейного программирования (glpk предоставляется бесплатно). Единственный вопрос: вы берете пустые сумки? Позволять

i = {1,2,3,4} -- set of item types
j -- set of items
x_ij = {0,1} -- decision variable for jth item of ith type
w_ij and p_ij -- weights and profits

max sum_ij p_ij*x_ij

subject to:
sum_j x_ij <= 6 for all i  // at most 6 items in a bag
// if you need empty bags:
sum_ij w_ij*x_ij + 4*50 <= 700 kg  // total weight

x_ij = {0,1} for all i and j.

если вам не нужны пустые пакеты, то рецептура усложняется

max sum_ij p_ij*x_ij

subject to:
sum_j x_ij <= 6    for all i  // at most 6 items in a bag
sum_ij w_ij*x_ij + 50*(sum_i y_i) <= 700 kg  // total weight
y_i <= sum_j x_ij    for all i  
N*y_i >= sum_j x_ij    for all i  // N -- total number of items of ith type, 
                                  // fixed value, not a variable; e.g., 
                                  // you have 10 items of each kind then N=10

y_i = {0,1} for all i
x_ij = {0,1} for all i and j.

Если вам нужно решить программу один раз, я предлагаю написать файл cplex .lp http://www-01.ibm.com/support/knowledgecenter/SS9UKU_12.4.0/com.ibm.cplex.zos.help/FileFormats/topics/LP.html и решите эту проблему с помощью glpsolve; в противном случае используйте вызываемые библиотеки c ++ или python glpk.

Обновление 1:

Можно линеаризовать ограничение min{50, sum_i x_i*w_i} в два этапа. Для простоты рассмотрим один рюкзак. Позволять

M -- the total possible weight (sum up all input items' weights)
y={0,1} -- when sum_i x_i*w_i >= 50 y=1, otherwise y=0

min{50, sum_i x_i*w_i} <= 100    is equivalent to
(0): (1-y)*50 + y*(sum_i x_i*w_i) <= 100
(1): My >= sum_i x_i*w_i - 50
(2): M(1-y) >= 50 - sum_i x_i*w_i

это немного необычно, но правильно. Действительно, когда sum_i x_i*w_i >= 50 решатель должен установить y в 1 ограничением (1), в то же время (2) просто 0 >= 50-sum_i x_i*w_i <= 0, т.е. является избыточным; когда sum_i x_i*w_i < 50, y = 0 на (2), и теперь (1) является избыточным.

Следующим шагом является линеаризация второго члена в (0). Пусть z_i = {0,1}, это будет y*x_i термин. Обратите внимание, что y*x_i равно 1 только тогда, когда оба члена равны 1, в противном случае - 0. Следовательно,

y*(sum_i x_i*w_i)  is equivalent to

sum_i z_i*w_i
2*z_i <= x_i + y,  for all i
z_i >= x_i + y - 1,  for all i

как и раньше, легко проверить, что z_i = 1, только если x_i = y = 1, в противном случае - 0.

После линеаризации ваше ограничение выглядит следующим образом:

(0): (1-y)*50 + (sum_i z_i*w_i) <= 100

(1): My >= sum_i x_i*w_i - 50
(2): M(1-y) >= 50 - sum_i x_i*w_i

(3): 2*z_i <= x_i + y,  for all i
(4): z_i >= x_i + y - 1,  for all i

 y = {0,1}, z_i = {0,1}

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

W_j >= 50  for all j
W_j >= sum_i w_i * X_ij for all j
sum_j W_j <= 700

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

Удачи :)

Если вы ищете точный оптимальный ответ, эта проблема является NP-полной, однако я заметил, что вы описываете очень небольшой набор проблем.

Если ваша проблема такая небольшая, возможен поиск методом перебора: вы можете просто сгенерировать все возможные решения, вычислить стоимость решения и выбрать лучшее.

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

Интересно отметить, что вы можете преобразовать свои ограничения в числовые «Взыскать» и использовать неограниченные методы оптимизации, немного упростив вашу задачу.

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

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

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