OptaPlanner过约束处理：虚拟值与空值解析

偷偷努力，悄无声息地变强，然后惊艳所有人！哈哈，小伙伴们又来学习啦~今天我将给大家介绍《OptaPlanner过约束规划：虚拟值与空值处理解析》，这篇文章主要会讲到等等知识点，不知道大家对其都有多少了解，下面我们就一起来看一吧！当然，非常希望大家能多多评论，给出合理的建议，我们一起学习，一起进步！

OptaPlanner过约束规划概述

在资源有限的规划问题中，有时会出现需求量超过可用资源容量的情况，这被称为“过约束规划”（Overconstrained Planning）。例如，医院只有9张病床，却有10名患者需要住院。在这种情况下，我们不能简单地拒绝服务，而是需要一种机制来识别并管理这些超出容量的需求。OptaPlanner提供了两种主要策略来应对这类问题：将规划变量设为可空（nullable=true）或引入“虚拟值”（Virtual Values）。

策略一：使用可空（nullable=true）规划变量

当某些实体无法被分配到资源时，可以将其对应的规划变量设置为null。这种方法适用于以下场景：

• 业务目标：未分配的实体可以被视为“无法满足的需求”，其处理责任可能转移给其他系统或被直接拒绝。例如，如果一个任务无法被安排，它可能被推迟到下一个规划周期，或者被视为一个失败的请求。

• 工作原理：

  1. 将规划实体上的规划变量（例如，Task的timeslot）的nullable属性设置为true。
  2. 在分数计算中，对那些被分配到null值的实体施加一个中等（Medium）惩罚。这样，求解器会尝试最大化分配数量，同时满足所有硬约束。

• 约束处理：

  • 当一个实体被分配到null时，与该实体相关的硬约束和软约束将不再对该实体生效。这意味着，如果一个任务没有被分配timeslot，那么关于该任务在timeslot上的任何时间冲突、资源限制等约束都将不被考虑。
  • 求解器会优先满足所有硬约束，然后尽量减少分配到null的实体数量（通过减少中等惩罚）。

• 示例代码（概念性）：

  // 规划实体类：Task
  @PlanningEntity
  public class Task {
      private String id;
      // timeslot是规划变量，可以为null
      @PlanningVariable(valueRangeProviderRefs = {"timeslotRange"}, nullable = true)
      private Timeslot timeslot;
      // ... 其他属性和方法
  }
  
  // 分数计算器（Drools或ConstraintStreams）
  // 假设使用ConstraintStreams
  class MyConstraintProvider implements ConstraintProvider {
      @Override
      public Constraint[] defineConstraints(ConstraintFactory factory) {
          return new Constraint[] {
              // 硬约束：例如，一个timeslot不能同时处理两个任务
              factory.forEachUniquePair(Task.class,
                      // 两个任务不能在同一个timeslot且timeslot不为null
                      Joiners.equal(Task::getTimeslot),
                      Joiners.filtering((task1, task2) -> task1.getTimeslot() != null))
                  .penalize("Timeslot冲突", HardSoftScore.ONE_HARD),
  
              // 中等约束：惩罚未分配timeslot的任务
              factory.forEach(Task.class)
                  .filter(task -> task.getTimeslot() == null)
                  .penalize("未分配任务", HardMediumSoftScore.ONE_MEDIUM) // 使用HardMediumSoftScore
          };
      }
  }

  在这种模式下，求解器会尽量将任务分配给实际的timeslot，以避免MEDIUM惩罚，但如果无法满足所有硬约束，则允许部分任务被分配到null。

策略二：引入虚拟值（Virtual Values）

虚拟值是一种更高级的过约束处理机制，它模拟了“额外”或“外部”资源的存在，用于吸收超出实际容量的需求。这适用于以下场景：

• 业务目标：所有实体都必须得到处理，即使这意味着需要付出额外成本（例如，租用外部设施、雇佣临时工）。未分配的实体被视为“你的问题”，需要找到解决方案。

• 概念解释：虚拟值不是真正的资源，而是规划域中代表“应急”或“溢出”容量的抽象值。例如，如果医院有9张实际病床，但有10名患者，我们可以创建1个“虚拟病床”，表示第10名患者将被安排到外部合作医院的床位。

• 工作原理：

  1. 不将规划变量设为nullable=true。所有实体都必须被分配到一个值。
  2. 在规划变量的值域中，除了实际资源外，额外添加一些“虚拟值”。这些虚拟值需要有一个标识，表明它们是虚拟的。
  3. 在分数计算中，对那些被分配到虚拟值的实体施加一个中等（Medium）惩罚。

• 约束处理：

  • 关键区别：即使实体被分配到虚拟值，所有硬约束和软约束仍然对其生效。这意味着，如果一个任务被分配到一个虚拟timeslot，它仍然必须遵守所有与timeslot相关的规则（例如，一个虚拟timeslot不能同时安排两个任务，或者虚拟timeslot也有其特定的容量限制）。
  • 求解器会优先满足所有硬约束，然后尽量减少分配到虚拟值的实体数量（通过减少中等惩罚）。

• 如何估算虚拟值数量：

  • 虚拟值的数量需要根据领域特定公式进行估算。通常建议多于理论最大溢出需求，例如，将需求量的两倍或更多作为虚拟值的数量，以确保求解器有足够的空间进行探索。

• 示例代码（概念性）：

  // Timeslot类需要一个属性来标识是否是虚拟Timeslot
  public class Timeslot {
      private String id;
      private boolean isVirtual; // 标识是否为虚拟timeslot
      // ... 其他属性和方法
  }
  
  // 规划实体类：Task
  @PlanningEntity
  public class Task {
      private String id;
      // timeslot是规划变量，不能为null，因为它必须被分配到真实或虚拟timeslot
      @PlanningVariable(valueRangeProviderRefs = {"timeslotRange"}, nullable = false) // 注意这里是false
      private Timeslot timeslot;
      // ... 其他属性和方法
  }
  
  // 规划解决方案类：定义值域提供者
  @PlanningSolution
  public class MyPlanningSolution {
      // ... 其他属性
      private List allTimeslots; // 包含真实和虚拟Timeslot
  
      @ValueRangeProvider(id = "timeslotRange")
      public List getTimeslotRange() {
          return allTimeslots;
      }
  
      // 假设在初始化时，allTimeslots会被填充
      public void initializeTimeslots(List realTimeslots, int virtualTimeslotCount) {
          this.allTimeslots = new ArrayList<>(realTimeslots);
          for (int i = 0; i < virtualTimeslotCount; i++) {
              Timeslot virtual = new Timeslot("VIRTUAL_" + i, true);
              this.allTimeslots.add(virtual);
          }
      }
      // ...
  }
  
  // 分数计算器（Drools或ConstraintStreams）
  class MyConstraintProvider implements ConstraintProvider {
      @Override
      public Constraint[] defineConstraints(ConstraintFactory factory) {
          return new Constraint[] {
              // 硬约束：一个timeslot（无论是真实还是虚拟）不能同时处理两个任务
              factory.forEachUniquePair(Task.class,
                      Joiners.equal(Task::getTimeslot))
                  .penalize("Timeslot冲突", HardSoftScore.ONE_HARD),
  
              // 中等约束：惩罚分配到虚拟timeslot的任务
              factory.forEach(Task.class)
                  .filter(task -> task.getTimeslot().isVirtual())
                  .penalize("使用虚拟Timeslot", HardMediumSoftScore.ONE_MEDIUM)
          };
      }
  }

  在这种模式下，所有任务都会被分配到一个timeslot，但那些被分配到虚拟timeslot的任务会产生MEDIUM惩罚。由于硬约束仍然适用于虚拟timeslot，求解器必须确保即使使用虚拟资源，所有规则也得到遵守。

选择策略的考量

在决定使用nullable=true还是虚拟值时，应考虑以下几个关键因素：

1. 业务目标与责任归属：
   • 如果未分配的实体可以被“拒绝服务”或成为“别人的问题”（例如，客户的请求被拒绝），则nullable=true可能更合适。
   • 如果所有实体都必须得到处理，即使这意味着额外的成本或资源（例如，所有患者都必须有床位，即使是外部租用的），则虚拟值是更好的选择。
2. 约束的适用性：
   • 核心差异：对于nullable=true，被分配到null的实体通常不参与硬约束和软约束的评估。
   • 对于虚拟值，即使实体被分配到虚拟资源，所有硬约束和软约束仍然对其生效。这意味着虚拟资源本身也必须遵守规划规则（例如，一个虚拟床位不能同时给两个人）。
3. 解决方案的解释性：
   • 虚拟值提供了一个明确的“溢出”或“应急”资源视图，有助于理解哪些需求超出了常规容量，以及这些超出的需求将如何被满足（尽管是虚拟的）。
   • nullable=true则简单地表示“未分配”，可能需要额外的逻辑来解释这些未分配的实体将如何被处理。
4. 实现复杂性：
   • nullable=true在实现上通常更简单，只需设置一个属性和添加一个惩罚约束。
   • 虚拟值需要额外的数据模型设计（标识虚拟资源）、值域的构建（包含虚拟资源）以及相应的惩罚约束，相对复杂一些。

总结

OptaPlanner在处理过约束规划时，提供了nullable=true和虚拟值两种有效策略。nullable=true适用于那些可以被“拒绝服务”或转移责任的未分配实体，其核心特点是未分配实体不计入硬软约束。而虚拟值则适用于所有实体都必须得到处理的场景，即使这意味着引入“额外”成本，其关键优势在于即使是虚拟资源，也必须遵守所有规划规则。

在实际应用中，开发者应根据具体的业务需求、对未分配实体的处理方式以及对约束严格性的要求，审慎选择最合适的过约束规划策略。正确地应用这些策略，将有助于构建更健壮、更符合实际业务需求的OptaPlanner解决方案。

到这里，我们也就讲完了《OptaPlanner过约束处理：虚拟值与空值解析》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！