本文深入探讨OptaPlanner中处理过约束规划的两种核心策略：使用可空（nullable）规划变量和引入虚拟值。我们将对比这两种方法在资源分配、约束评估和问题归属方面的差异，并提供何时选择哪种策略的指导，帮助开发者根据实际业务需求构建高效且符合逻辑的解决方案。
理解过约束规划
在资源规划问题中，过约束（overconstrained planning）指的是当可用资源无法满足所有需求时的情况。例如，医院只有9张床位，却有10位或更多患者需要住院。在这种情况下，optaplanner不能简单地拒绝分配，而是需要一种机制来识别和量化“未满足”的需求，并将其纳入评分体系，从而找到一个最优的“次优”解决方案。处理过约束问题，通常有两种主要策略：使用可空规划变量（nullable=true）和引入虚拟值（virtual values）。
策略一：使用可空规划变量 (nullable=true)
当规划实体无法被分配到任何合适的资源时，nullable=true 允许其规划变量保持为空（null）。这种方法的核心思想是，未分配的实体被视为“外部问题”或其服务被简单地拒绝。
适用场景：
阿里云-虚拟数字人
阿里云-虚拟数字人是什么？ …
2 查看详情 服务拒绝： 当资源不足时，未被分配的实体直接被拒绝服务，且这不直接导致额外的成本或需要你解决的后续问题。例如，有限的停车位，未分配到车位的车辆就无法停车，这不是规划系统需要进一步解决的问题。责任转移： 未分配的实体被认为是其他系统或部门的问题。
实现方式：
规划变量设置： 在你的规划实体中，将规划变量标记为可空。
// 示例：一个任务（Task）需要分配一个时间段（Timeslot）@PlanningEntitypublic class Task { // ... 其他属性 @PlanningVariable(valueRangeProviderRefs = {"timeslotRange"}, nullable = true) private Timeslot timeslot; // ... getter/setter}
约束设置： 添加一个中等（Medium）约束来惩罚那些未被分配到任何时间段的实体。
// 伪代码：使用ConstraintFactory创建约束public Constraint unassignedTaskPenalty(ConstraintFactory factory) { return factory.forEach(Task.class) .filter(task -> task.getTimeslot() == null) .penalize(HardMediumSoftScore.ONE_MEDIUM, "每个未分配任务的惩罚") .asConstraint("Unassigned Task Penalty");}
特点：
最大化利用率： OptaPlanner会尽力在现有资源下最大化分配数量，同时满足硬约束。约束作用范围： 硬约束和软约束通常不适用于未分配（null）的实体。这意味着，如果一个任务未被分配时间段，它就不会因为违反了与时间段相关的硬约束而受到惩罚。
策略二：引入虚拟值 (Virtual Values)
虚拟值是一种更复杂的过约束处理方式，它模拟了“额外”的、通常带有成本的资源。当实际资源不足时，实体可以被分配给这些虚拟值，表示其需求得到了满足，但需要付出额外的代价。
适用场景：
问题仍需解决： 未分配的实体仍然是你的问题，需要通过额外成本（如加班、外包、租赁额外资源）来解决。例如，医院床位不足，患者可以被安排到合作医院的床位（虚拟床位），但这会产生额外的租赁费用。成本量化： 你需要量化因资源不足而产生的额外成本或不便。
实现方式：
领域模型扩展： 在你的领域模型中定义虚拟资源。这些虚拟资源与实际资源属于同一类型，或者实现相同的接口。
// 示例：Timeslot接口和其实现类public interface Timeslot {}public class RealTimeslot implements Timeslot { // ... 实际时间段属性}public class VirtualTimeslot implements Timeslot { // ... 虚拟时间段属性，例如成本因子 private int costFactor; // 表示使用该虚拟时间段的额外成本 // ...}// 在规划实体中，规划变量现在可以分配给RealTimeslot或VirtualTimeslot@PlanningEntitypublic class Task { // ... 其他属性 @PlanningVariable(valueRangeProviderRefs = {"timeslotRange"}) // 注意：这里nullable=false或不设置 private Timeslot timeslot; // ... getter/setter}
规划问题定义： 在你的问题域中，预先创建并包含一定数量的虚拟值。这些虚拟值的数量需要根据业务逻辑进行估计，通常是最大可能需求的两倍或更多，以确保有足够的“备用”资源。
// 示例：在问题初始化时创建时间段列表List allTimeslots = new ArrayList();// 添加实际时间段allTimeslots.addAll(realTimeslots);// 添加虚拟时间段，例如，假设我们最多需要额外50个时间段for (int i = 0; i < 50; i++) { allTimeslots.add(new VirtualTimeslot(i + 1)); // 虚拟时间段可以有自己的标识或成本}// 将allTimeslots作为timeslotRange提供给规划变量
约束设置： 添加一个中等约束来惩罚那些被分配给虚拟值的实体。这个惩罚可以根据虚拟值的类型或数量进行调整。
// 伪代码：使用ConstraintFactory创建约束public Constraint virtualTimeslotAssignmentPenalty(ConstraintFactory factory) { return factory.forEach(Task.class) .filter(task -> task.getTimeslot() instanceof VirtualTimeslot) // 惩罚可以根据VirtualTimeslot的costFactor或其他属性来计算 .penalize(HardMediumSoftScore.ONE_MEDIUM, task -> ((VirtualTimeslot) task.getTimeslot()).getCostFactor(), "分配给虚拟时间段的惩罚") .asConstraint("Virtual Timeslot Assignment Penalty");}
特点：
问题内部解决： 未分配的实体通过分配给虚拟值，将问题“内部化”，并量化其成本。约束作用范围： 硬约束和软约束仍然作用于分配给虚拟值的实体。这意味着，即使任务被分配给了虚拟时间段，它仍然需要遵守与时间段相关的其他硬约束（例如，虚拟时间段不能同时处理两个冲突任务），否则将产生硬惩罚。
两种策略的对比与选择
问题归属未分配实体被视为外部问题，不直接由规划系统解决。未分配实体仍是规划系统的问题，通过额外资源解决，并量化成本。资源建模仅使用实际资源，null 代表无资源分配。实际资源 + 模拟的额外（有成本的）虚拟资源。约束作用硬约束和软约束通常不作用于未分配（null）的实体。硬约束和软约束作用于分配给虚拟值的实体。成本量化只能通过惩罚 null 来间接表示未分配的成本。可以精确量化使用额外资源的成本。复杂性相对简单，只需设置 nullable=true 和 null 惩罚。需要扩展领域模型，预估并生成虚拟值，约束逻辑稍复杂。搜索空间搜索空间较小，因为 null 是一个固定状态。搜索空间可能增大，因为虚拟值增加了可选的资源数量。
何时选择：
选择 nullable=true： 当你的业务场景中，资源不足导致的需求未被满足时，这被认为是可接受的，或者后续处理不由当前规划系统负责。你主要关注在现有资源下最大化分配，且未分配实体不应触发与资源相关的其他硬约束。选择虚拟值： 当你的业务场景中，资源不足导致的需求仍需被满足，但需要付出额外成本。你需要量化这些额外成本，并且这些“额外满足”的需求仍需遵守某些规划约束（例如，即使是虚拟床位，也可能需要考虑患者类型或护理人员可用性）。
注意事项
分数类型： 在两种策略中，惩罚未分配或分配给虚拟值的实体通常使用 HardMediumSoftScore 的中等（Medium）分数。这确保了在满足所有硬约束的前提下，尽可能减少未分配或使用虚拟值的数量。虚拟值的数量： 预估和创建足够多的虚拟值至关重要。如果虚拟值数量不足，系统仍可能面临无法分配所有实体的局面；如果过多，则可能不必要地增加搜索空间。约束设计： 仔细设计约束，确保硬约束和软约束在两种策略下都能正确反映业务逻辑。特别是对于虚拟值，要明确哪些硬约束仍适用于分配给虚拟值的实体。性能考量： 引入大量虚拟值可能会增加OptaPlanner的搜索空间，从而影响求解性能。在实际应用中，需要权衡虚拟值的数量与求解效率。
总结
OptaPlanner提供了灵活的机制来处理过约束规划。nullable=true 策略简洁明了，适用于未分配实体被视为外部问题或直接拒绝的场景；而虚拟值策略则更为强大，能够将资源不足的成本内部化并量化，适用于未分配实体仍需解决且需遵守特定约束的复杂场景。理解这两种策略的优缺点及适用场景，是构建高效且符合业务逻辑的OptaPlanner解决方案的关键。开发者应根据具体业务需求，权衡问题归属、成本量化和约束作用范围，选择最合适的策略。
以上就是OptaPlanner 过约束规划：虚拟值与空值变量的策略选择的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/221017.html
微信扫一扫 
支付宝扫一扫 
