Google 优化工具支持软约束吗？

Question

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

我并不反对 optaplanner。只是需要付出更多的努力来学习足够的 java 和所使用的“流口水”语法。

Answer 1

软约束的实现

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

x1 + x1_surplus - x1_deficit = goal

其中x1是我们的决策变量，x1_surplus分别x1_deficit是我们的正松弛变量和负松弛变量，目标是我们的决策变量的目标数字x1。

一旦我们有了这个约束，我们必须添加一个目标来最小化总偏差百分比，如下所示：

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

笔记：

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

Google 或工具中的示例

这是 Google OR Tools 中的一个基本工作示例。在这里，我们正在生产两种产品，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())