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

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。

我很难用谷歌或其他工具来描述这一点。

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\u 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['Item'][i][2]=value）。你想要最高的值。

你的型号与背包相似。只有您将为成本（小于总成本）和标志（总标志大于5）添加额外约束。还有，你说过你会选20件。但您的约束限制为15项（最多项）。

或工具页面在箱子包装标题下有背包问题的详细说明。

我想你编辑了你的问题。“is\u blue”属性只需要一个约束。但现在你的模型有不同的问题。

>

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

对于范围内的i（num\u配方）：解算器。添加（x【i】*成本【i】

这是你的目标函数。

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

但您只将前20项添加到目标函数中。您需要更改使用MAX\u项选择的total\u。例如：

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

最后一个是蓝色约束。我知道您想选择至少5个蓝色项目。

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