Оптимизация ограничений с помощью инструментов исследования операций Google

Question

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

Я прочитал и работал над учебником в https://developers.google.com/optimization/mip/integer_opt_cp и https://developers.google.com/optimization/mip/integer_opt,, но мои ограничения немного отличаются от тех, которые там представлены.

Каждый элемент представлен в виде кортежа:

item = ('item name', cost, profit, is_blue)

в качестве примера

vase = ['Ming Vase', 1000, 10000, 0]

plate = ['China Plate', 10, 5, 1]

, а общий набор предметов представляет собой список списков:

items = [item1, item2, ..., itemN].

Мои доходы и расходы также перечислены:

profits = [x[2] for x in items]
costs = [x[1] for x in items]

Для каждого выбранного элемента он должен иметь минимальное значение, а минимум 5 элементов должны иметь флаг свойства (is_blue), равный 1.

Я хочу выбрать 20 самых дешевых предметов с наибольшим значением, чтобы у 5 из них флаг свойства был установлен на 1.

У меня проблемы с формулировкой с помощью инструментов Google OR.

from ortools.linear_solver import pywraplp

solver = pywraplp.Solver('SolveAssignmentProblemMIP',
                       pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)

x = {}

for i in range(MAX_ITEMS):
    x[i] = solver.BoolVar('x[%s]' % (i))

#Define the constraints 
total_chosen = 20
solver.Add(solver.Sum([x[i] for i in range(MAX_ITEMS)]) == total_chosen)

max_cost = 5.0

for i in range(num_recipes):
    solver.Add(x[i] * cost[i] <= max_cost)

solver.Maximize(solver.Sum([profits[i] * x[i] for i in range(total_chosen)]))
sol = solver.Solve()

Я могу получить набор предметов, которые я выбрал:

for i in range(MAX_ITEMS):
    if x[i].solution_value() > 0:
        print(item[i].item_name)

Это прекрасно работает - он выбирает набор из 20 элементов, которые максимизируют прибыль в зависимости от ограничения затрат, но я застрял, как расширить это, чтобы выбрать элементы с свойством (is_blue), установленным в true или false.

Любая помощь в формулировании ограничений и целей была бы действительно полезной. Спасибо!

Answer 1

Итак, после недели размышлений я знаю, как ответить на этот вопрос: и все-таки это действительно легко.

Просто определите список:

is_blue = [x[3] for x in items]

и затем добавьте:

solver.Add(solver.Sum([x[i] * is_blue[i] for i in range(MAX_ITEMS)] == num_blue)

в список ограничений.

Answer 2

Я не понимаю, почему вы минимизируете значения (cfg ['items'] [i] [2] = value). Вы хотите самое высокое значение.

Ваша модель похожа на рюкзак. Только вы добавите дополнительные ограничения для стоимости (меньше, чем общая стоимость) и флага (всего флаги больше 5). Также вы сказали, что выберете 20 предметов. Но ваше ограничение ограничено 15 предметами (максимум предметов).

На странице инструментов ИЛИ есть подробное объяснение проблемы с рюкзаком под заголовком упаковки.

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

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

   для i в диапазоне (num_recipes): решатель.Добавить (x [i] * стоит [i] <= max_cost) Кроме того, я понимаю, что из этого ограничения max_cost определяется для каждого элемента, а не для суммы затрат. </p>

2. Это ваша целевая функция.

   solver.Maximize(solver.Sum([profits[i] * x[i] for i in range(total_chosen)])) 
   

   Но вы добавляете только первые 20 пунктов к целевой функции. Вам нужно изменить total_chosen с MAX_ITEMS. Такие как:

   solver.Maximize(solver.Sum([profits[i] * x[i] for i in range(MAX_ITEMS)]))
   

3. И последнее ограничение is_blue. Я понимаю, что вы хотите выбрать как минимум 5 синих предметов.

   blues = [x[3] for x in items]
   solver.Add(solver.Sum([blues[i] * x[i] for i in range(MAX_ITEMS)]) >= 5)