使用谷歌运营研究工具进行约束优化

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.

我在使用谷歌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

我不明白为什么你要最小化值（cfg['items'][i][2] = value）。你想要最高的价值。

你的模型类似于背包。只有您需要为成本（小于总成本）和标志（总标志大于 5）添加额外的约束。另外，你说你会选择20个项目。但您的限制限制为 15 个项目（最大项目）。

OR 工具页面在装箱标题下有背包问题的详细解释。

我认为你编辑了你的问题。对于“is_blue”属性，您只需要一个约束。但现在你的模型有不同的问题。

1. 如果您列出的成本名称是“成本”，则您的约束必须更改，因为您使用“成本”命名列表。

   for i in range(num_recipes):solver.Add(x[i] * cost[i] <= max_cost) 另外，我从这个约束中了解到 max_cost 是为每个项目定义的，而不是为成本总和定义的。

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)