optimization - Google 优化工具是否支持软约束？

Question

我想知道是否有人熟悉 Google 优化工具可以解决这个问题。我在看谷歌 examples员工调度和 N 皇后区。这两个示例似乎都让优化器仅在硬约束下运行(例如，必须是这种情况)但似乎没有解决(这是首选但不是必需的)。是否支持软约束？或者是此时软约束的唯一实现optaplanner ？

我不反对 optaplanner。它只是需要更多的努力来学习足够的 java 和使用的“drools”语法。

Answer 1

软约束的实现

正如 Erwin 指出的那样，要实现软约束，我们需要将松弛变量添加到我们的模型并将它们放入目标函数中。为此，我们为问题中的每个软约束变量再添加两个决策变量。这些决策变量代表了我们感兴趣的变量中的松弛。然后我们可以使用以下公式来创建我们的软约束:

x1 + x1_surplus - x1_deficit = goal

其中x1是我们的决策变量，x1_surplus和x1_deficit分别是我们的正负松弛变量，goal是我们的数量针对我们的决策变量 x1。

一旦我们有了这个约束，我们必须添加一个最小化总百分比偏差的目标，看起来像这样:

minimize:
    (1/goal) * x1_surplus + (1/goal) * x1_deficit

注意:

我们使用百分比偏差是因为我们经常处理以不同单位衡量的变量(例如，下例中的千克与磅)。如果我们不使用百分比偏差，我们的变量中的松弛效应将是不平衡的。

Google 或工具中的示例

这是 Google OR 工具中的一个基本工作示例。在这里，我们正在生产两种产品 A 和 B，并且我们想要生产的每种产品都有一定数量。我们还有与制造这些产品相关的成本以及我们希望在制造产品上花费的金额的目标(在本例中为 +/- 10000)。

from ortools.linear_solver import pywraplp

solver = pywraplp.Solver("Soft Constraint Example", pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

product_a = solver.IntVar(0, 10000, "Pounds of Product A:")
product_b = solver.IntVar(0, 10000, "Pounds of Product B:")

product_a_surplus = solver.IntVar(0, 100, "Product A Surplus:")
product_a_deficit = solver.IntVar(0, 100, "Product A Deficit:")

product_b_surplus = solver.IntVar(0, 100, "Product B Surplus:")
product_b_deficit = solver.IntVar(0, 100, "Product B Deficit:")

cost_surplus = solver.IntVar(0, 10000, "Cost Surplus:")
cost_deficit = solver.IntVar(0, 10000, "Cost Deficit:")

product_a_goal = solver.Add(product_a - product_a_surplus + product_a_deficit == 500)
product_b_goal = solver.Add(product_b - product_b_surplus + product_b_deficit == 250)

cost_goal = solver.Add(product_a * 100 + product_b * 200 - cost_surplus + cost_deficit == 75000)

solver.Minimize(
    (1/100) * product_a_surplus
    + (1/100) * product_a_deficit 
    + (1/200) * product_b_surplus 
    + (1/200) * product_b_deficit
    + (1/75000) * cost_surplus
    + (1/75000) * cost_deficit
)

status = solver.Solve()

print(status == solver.OPTIMAL)

final_cost = product_a.solution_value() * 100 + product_b.solution_value() * 200

print("Final Cost:", final_cost)

var = [product_a, product_b, product_a_surplus, product_a_deficit, 
       product_b_surplus, product_b_deficit,
       cost_surplus, cost_deficit]

for v in var:
    print(v.name(), v.solution_value())