Google优化工具是否支持软约束? [英] Do Google Optimization Tools support Soft Constraints?

问题描述

我想知道熟悉Google优化工具的人是否可以解决这个问题.我当时在看Google 示例，既有员工调度，也有N-queens.这两个示例似乎都使优化器仅在严格的约束条件下运行(例如，必须是这种情况)，但似乎无法解决(这是首选，但不是必需的).是否支持软约束?还是目前唯一的软约束实现 optaplanner ?

I was wondering if anyone familiar with Google Optimization tools can address this. I was looking at the Google examples both employee scheduling and N-queens. Both example seem to have the optimizer running only on hard constraints (e.g. this must be the case) but doesn't seem to solve (this is the preferred but not required). Is there support for soft-constraints? Or is the only implementation of soft constraints at this time optaplanner?

我不反对optaplanner.要学习足够的Java和所使用的"drools"语法，将需要付出更多的努力.

I'm not opposed to optaplanner. It just will require a lot more effort to learn enough java and the "drools" syntax used.

推荐答案

软约束的实现

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

Implementation of soft constraint

As Erwin points out, to implement soft constraints, we need to add slack variables to our model and place them in the objective function. To do this, we add two more decision variables for each soft-constrained variable we have in our problem. These decision variables represent the slack in our variable of interest. We can then use the following formula to create our soft constraint:

x1 + x1_surplus - x1_deficit = goal

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

Where x1 is our decision variable, x1_surplus and x1_deficit are our positive and negative slack variables respectively, and goal is the number we are aiming for on our decision variable x1.

一旦有了此约束，就必须添加一个目标，以使总百分比偏差最小化，该偏差类似于:

Once we have this constraint in place, we must add an objective that minimizes the total percentage deviance which would look something like:

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

注意:

我们使用百分比偏差，因为我们经常处理以不同单位衡量的变量(例如，在下面的示例中为公斤vs.磅).如果不使用百分比偏差，则变量松弛的影响将不平衡.

We use percentage deviation because we often deal with variables that are measured in different units (e.g. kilograms vs. pounds in the example below). If we do not use percentage deviation the effect of slack in our variables will be unbalanced.

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

Here is a basic working example in Google OR Tools. Here, we are making two products, A and B, and have a certain number of each product we would like to make. We also have a cost associated with making these products and a goal for the amount that we would like to spend on making the products (+/- 10000 in this case).

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())

这篇关于Google优化工具是否支持软约束?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！