谷歌优化工具支持软约束吗？

Question

我想知道是否有人熟悉谷歌优化工具可以解决这一问题。我正在查看Google 示例的员工日程安排和N皇后。这两个示例似乎只在硬约束下运行优化器(例如，必须是这样的)，但似乎没有解决问题(这是首选的，但不是必需的)。是否支持软约束？或者是此时软性约束的唯一实现-- 视光机

我不反对光学规划师。它将需要更多的努力来学习足够的java和使用的"drools“语法。

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

Answer 2

In OptaPlanner，您不必再使用drools语法了，可以使用新的增量式ConstraintStreams。ConstraintStreams是快速和可伸缩的。

下面是一个如何在您询问的NQueens问题上使用它们的示例：

protected Constraint horizontalConflict(ConstraintFactory factory) {
    // Select a queen
    return factory.from(Queen.class)
            // Select a different queen on the same row
            .join(Queen.class,
                    equal(Queen::getRowIndex),
                    lessThan(Queen::getId))
            // Tell OptaPlanner not to put 2 queens on the same row
            .penalize("Horizontal conflict", HardSoftScore.ONE_HARD);
}

// For reference, the model:
@PlanningEntity
class Queen {
     long id;
     int columnIndex;
     @PlanningVariable
     int rowIndex;
     ... // getters/setters
}

同样，对于员工名册，您也会问：

protected Constraint skillLacking(ConstraintFactory factory) {
    // Select a shift
    return factory.from(Shift.class)
            // The shift's employee doesn't have the required skill
            .filter(shift -> !shift.getEmployee().getSkillSet()
                    .contains(shift.getRequiredSkill())
            // Tell OptaPlanner to avoid that
            .penalize("Skill lacking", HardSoftScore.ONE_SOFT,
                    // Lose one soft point per minute of the shift
                    shift -> shift.getDurationInMinutes());
}

// For reference, the model:
@PlanningEntity
class Shift {
     Skill requiredSkill;
     LocalDateTime start;
     LocalDateTime end;
     @PlanningVariable
     Employee employee;
     ... // getters/setters
}
class Employee {
     String name;
     Set<Skill> skillSet;
     ... // getters/setters
}