优化中的顺序约束
Order constraints in optimisation
我有一组很多(10000+)项,我必须从中选择恰好 20 项。每个项目我只能选择一次。我的物品有利润和成本,以及几个布尔属性(如颜色)。我需要按特定顺序输出结果:特别是我需要第一项和第三项为蓝色,第二项和第四项为红色。
每个项目都表示为一个元组:
item = ('item name', cost, profit, is_blue, is_red)
举个例子
vase = ['Ming Vase', 1000, 10000, 0, 1]
plate = ['China Plate', 10, 5, 1, 0]
项目的总集合是一个列表列表:
items = [item1, item2, ..., itemN].
我的利润和成本也列了:
profits = [x[2] for x in items]
costs = [x[1] for x in items]
对于每个选择的项目,它需要有一个最小值,并且至少 5 个项目必须将 属性 (is_blue) 标志设置为 1。
我想选择价值最高的 20 件最便宜的商品,其中 5 件的 is_blue 标志设置为 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)
blues = [x[3] for x in items]
solver.Add(solver.Sum([blues[i] * x[i] for i in .
范围(MAX_ITEMS)]) >= 5)
max_cost = 5.0
for i in range(MAX_ITEMS):
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 个项目,这些项目在成本约束下最大化利润,但我坚持如何将其扩展到以保证第一个是蓝色等的方式选择项目。
在制定约束和 objective 方面的任何帮助都会非常有帮助。谢谢!
不使用 BoolVar 来表示选择的项目,而是考虑制作一个包含 20 个 IntVar 且域为 0..MAX_ITEMS 的列表。从那里做这样的事情应该相当容易:
solver.Add(chosens[0].IndexOf(all_items)[3] == 1)
solver.Add(chosens[2].IndexOf(all_items)[3] == 1)
chosens[i].IndexOf(all_items) 仅表示 all_items[IndexOfChosen],即:第 I 个位置选择哪个项目。如果您采用这种方法,请不要忘记 MakeAllDifferent!
我有一组很多(10000+)项,我必须从中选择恰好 20 项。每个项目我只能选择一次。我的物品有利润和成本,以及几个布尔属性(如颜色)。我需要按特定顺序输出结果:特别是我需要第一项和第三项为蓝色,第二项和第四项为红色。
每个项目都表示为一个元组:
item = ('item name', cost, profit, is_blue, is_red)
举个例子
vase = ['Ming Vase', 1000, 10000, 0, 1]
plate = ['China Plate', 10, 5, 1, 0]
项目的总集合是一个列表列表:
items = [item1, item2, ..., itemN].
我的利润和成本也列了:
profits = [x[2] for x in items]
costs = [x[1] for x in items]
对于每个选择的项目,它需要有一个最小值,并且至少 5 个项目必须将 属性 (is_blue) 标志设置为 1。
我想选择价值最高的 20 件最便宜的商品,其中 5 件的 is_blue 标志设置为 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)
blues = [x[3] for x in items]
solver.Add(solver.Sum([blues[i] * x[i] for i in .
范围(MAX_ITEMS)]) >= 5)
max_cost = 5.0
for i in range(MAX_ITEMS):
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 个项目,这些项目在成本约束下最大化利润,但我坚持如何将其扩展到以保证第一个是蓝色等的方式选择项目。
在制定约束和 objective 方面的任何帮助都会非常有帮助。谢谢!
不使用 BoolVar 来表示选择的项目,而是考虑制作一个包含 20 个 IntVar 且域为 0..MAX_ITEMS 的列表。从那里做这样的事情应该相当容易:
solver.Add(chosens[0].IndexOf(all_items)[3] == 1)
solver.Add(chosens[2].IndexOf(all_items)[3] == 1)
chosens[i].IndexOf(all_items) 仅表示 all_items[IndexOfChosen],即:第 I 个位置选择哪个项目。如果您采用这种方法,请不要忘记 MakeAllDifferent!