我想知道是否有熟悉谷歌优化工具的人可以解决这个问题。我正在查看谷歌的例子，包括员工调度和N-queens。这两个示例似乎都让优化器仅在硬约束上运行(例如，必须如此)，但似乎无法解决(这是首选但不是必需的)。是否支持软约束？还是目前唯一的软约束实现 optaplanner？
我不反对optaplanner。只是需要更多的努力来学习足够的Java和使用的"流口水"语法。
软约束的实现
正如 Erwin 指出的那样，为了实现软约束，我们需要将松弛变量添加到模型中，并将它们放在目标函数中。 为此，我们为问题中的每个软约束变量再添加两个决策变量。 这些决策变量代表了我们感兴趣的变量的松弛。 然后，我们可以使用以下公式来创建软约束：
x1 + x1_surplus - x1_deficit = goal
其中x1是我们的决策变量，x1_surplus和x1_deficit分别是我们的正和负松弛变量，目标是我们在决策变量x1上的目标数字。
一旦我们有了这个约束，我们必须添加一个目标，以最小化总百分比偏差，如下所示：
minimize:
(1/goal) * x1_surplus + (1/goal) * x1_deficit
注意：
我们使用百分比偏差，因为我们经常处理以不同单位测量的变量(例如，以下示例中的千克与磅)。 如果我们不使用百分比偏差，变量中松弛的影响将是不平衡的。
谷歌手术室工具中的示例
这是谷歌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())
在OptaPlanner中，您不必再使用drools语法。您可以改用新的增量约束流。约束流快速且可扩展。
下面是如何在您提出的 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
}