使用 google 运筹学工具进行约束优化

Question

我有一组很多（10000+）项，我必须从中选择恰好 20 项。每个项目我只能选择一次。我的物品有利润和成本，以及几个布尔属性（如颜色）。

我已经阅读并完成了 https://developers.google.com/optimization/mip/integer_opt_cp and 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) 设置为真或假。

在制定约束和 objective 方面的任何帮助都会非常有帮助。谢谢！

Answer 1

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

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

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

我想你编辑了你的问题。 "is_blue" 属性只需要一个约束条件。但是现在你的模型有不同的问题。

如果成本的列表名称是 "costs"，您的约束必须更改，因为您使用的是 "cost" 命名列表。

我在范围内（num_recipes）： solver.Add(x[i] * 成本[i] <= max_cost) 另外，我从这个约束中了解到 max_cost 是为每个项目定义的，而不是为成本总和定义的。

这是您的 objective 函数。

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

但是您只将前 20 项添加到 objective 函数。您需要将 total_chosen 更改为 MAX_ITEMS。如：

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

和最后一个is_blue约束。我了解到您想要 select 至少 5 件蓝色物品。

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

Answer 2

所以，经过一周的思考，我知道如何回答这个问题了：毕竟这很容易。

只需定义一个列表：

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)

到约束列表。

使用 google 运筹学工具进行约束优化

Constraint optimisation with google operations research tools

python

mathematical-optimization

constraint-programming

or-tools