天道酬勤,学无止境

Does OptaPlanner support optimizations and constraints on continuous variables?

I'm reading contradictory things in the documentation.

On one hand, this passage seems to indicate that continuous planning variables are possible:

A planning value range is the set of possible planning values for a planning variable. This set can be a discrete (for example row 1, 2, 3 or 4) or continuous (for example any double between 0.0 and 1.0).

On the other hand, when defining a Planning Variable, you must specify a ValueRangeProvider annotation on a field to use for the value set:

The Solution implementation has method which returns a Collection. Any value from that Collection is a possible planning value for this planning variable.

Both of these snippets are in the same section of the documentation (http://docs.jboss.org/drools/release/latest/optaplanner-docs/html_single/#d0e2518)

So, which is it? Can I use a full double as my planning variable, or do I need to restrict its range to the values in a specific Collection?

Looking at the actual algorithms are provided, I don't see any that are actually suitable for optimizing continuous variables, so I doubt it's possible, but it'd be nice to have that clarified and made explicit.

评论

We're working towards fully supporting continuous variables. But currently (in 6.0.0.CR2) it's not decently supported yet.

Value ranges can indeed be continuous ranges, but the plumbing to actually use them isn't there yet. We have made good progress recently, see https://issues.jboss.org/browse/PLANNER-160.

Here's how it will work: You 'll be able to use a @ValueRangeProvider annotation on a method that returns a ValueRange (instead of a Collection) too.

A ValueRange will be an interface supports selecting a random value, getting a size, ... Out-of-the-box we will support IntValueRange, DoubleValueRange, BigDecimalValueRange, ... (Implementation detail: we'll retro-fit those Collection-returning methods into a CollectionValueRange.)

Then the ValueSelector implementations will use that directly.

As for the suitability to optimize continuous variables:

  • JIT random selection will be blazing fast and be very memory-efficient.
  • If you have an NP-complete/NP-hard problem, then OptaPlanner will be a great match. If you have only continuous variables (and not a single discrete variable), then it's unlikely that your problem is NP-complete (unless your constraints counterprove that) and in that case you're better off with a custom, handmade, polynomial algorithm anyway (because it's not NP-complete, so there's an "easy" solution).

受限制的 HTML

  • 允许的HTML标签:<a href hreflang> <em> <strong> <cite> <blockquote cite> <code> <ul type> <ol start type> <li> <dl> <dt> <dd> <h2 id> <h3 id> <h4 id> <h5 id> <h6 id>
  • 自动断行和分段。
  • 网页和电子邮件地址自动转换为链接。

相关推荐
  • 带 OptaPlanner 的自行车信使 / TSPPD(Bicycle messenger / TSPPD with OptaPlanner)
    问题 尊敬的 OptaPlanner 专家! 我想使用 OptaPlanner(或类似的开源 Java 框架)来优化自行车信使服务的路线。 让我们假设 5 个信使必须从某个来源拿起 30 个信封并将它们送到某个目的地: X(FROM) Y(FROM) X(TO) Y(TO) envelope 1 13745 55419 13883 55756 envelope 2 8406 53246 13937 55854 envelope 3 15738 57396 35996 79499 envelope 4 12045 60418 19349 57118 envelope 5 13750 56416 35733 78403 envelope 6 13190 57068 11860 59749 envelope 7 15021 55768 14098 57379 envelope 8 11513 58543 11501 59683 envelope 9 12013 64155 14120 59301 envelope 10 15006 57578 35511 78426 envelope 11 11450 58819 11916 58338 envelope 12 13728 56304 35524 79013 envelope 13 15104 60923 17937 57066
  • Using Optaplanner to solve VRPTWPD
    I'm new to optaplanner, and am hoping to use it to solve the VRPTW problem with pickups and deliveries (VRPTWPD). I started by taking the VRPTW code from the examples repo. I am trying to add to it to solve my problem. However, I'm unable to return a solution that honors the precedence/vehicle constraints (pickups must be done before deliveries, and both must be done by the same vehicle). I am consistently returning a solution where the hard score is what I would expect for such a solution (i.e. I can add up all the violations in a small sample problem and see that the hard score matches the
  • 使用 Optaplanner 解决 VRPTWPD(Using Optaplanner to solve VRPTWPD)
    问题 我是 optaplanner 的新手,希望用它来解决取货和送货 (VRPTWPD) 的 VRPTW 问题。 我首先从示例存储库中获取 VRPTW 代码。 我正在尝试添加它以解决我的问题。 但是,我无法返回尊重优先级/车辆限制的解决方案(必须在交付前完成提货,并且两者都必须由同一辆车完成)。 我一直在返回一个解决方案,其中硬分是我对这种解决方案所期望的(即,我可以将所有违规添加到一个小样本问题中,并看到硬分与我为这些违规分配的惩罚相匹配)。 我尝试的第一种方法是遵循 Geoffrey De Smet 在这里概述的步骤 - https://stackoverflow.com/a/19087210/351400 每个Customer都有一个变量customerType ,用于描述它是取货 (PU) 还是送货 (DO)。 它还具有一个名为parcelId的变量,用于指示正​​在提取或交付的包裹。 我向Customer添加了一个 shadow 变量,名为parcelIdsOnboard 。 这是一个 HashSet,它保存了司机在访问给定Customer时随身携带的所有 ParcelIds。 我保持parcelIdsOnboard更新的VariableListener如下所示: public void afterEntityAdded(ScoreDirector
  • optaplanner 开箱即用是否支持具有多次旅行且没有仓库的 VRP(Does optaplanner out of box support VRP with multiple trips and no depot)
    问题 我正在研究具有以下特征的 VRP: 车辆一次只能接1名顾客车辆在某个地点接客户并在目的地下客下客后,车辆继续接客没有车辆在两次旅行之间需要去的站点。 车辆在一天内尽可能多地前往接送客户在一天结束时,车辆返回其指定的停车站 本质上,它就像一个出租车系统。 在我看来,它是一个具有多次旅行 (VRPMT) 且没有仓库 (Open VRP) 的 VRP。 我想知道 optaplanner 是否支持 VPRMT 和 OVRP 开箱即用? 如果开箱即用不支持 VPRMT 和 OVRP,那么修改现有的 CVRP/CVRPTW 示例使其解决 OVRP 和 VPRMT 有多容易? 也许我在错误的轨道上,它甚至不是 VRP。 如果是这样,出租车类系统的正确规划问题是什么? 提前谢谢了! 回答1 不,示例还不包括取货和送货或多次旅行用户之前已经完成添加取货和送货(如果多个客户不能同时在车上,这很容易(否则会更难,我可能会在某天添加一个示例)。多次旅行和开放 VRP 应该由容易(虽然我认为您的停车场是一个停车场,您可能没有多次旅行,只是在同一次旅行中依次有多个客户)。 这绝对是 VRP 的变体。 请注意,每个企业都有自己的 VRP 风格。 您总会发现一些自定义约束(在开发过程中现在或以后)。 OptaPlanner 允许您根据需要添加这些自定义约束。 试试这个:以 OptaPlanner VRP
  • OptaPlanner 车辆路线和客户访问之间的关系(OptaPlanner vehicle routing and relations between customer visits)
    问题 我正在使用 OptaPlanner 来优化与提供的示例非常相似的车辆路径问题。 我面临以下挑战,并会欣赏一些想法。 一些对客户的访问与其他访问有关系,例如: 一次访问必须与另一次访问同时开始。 访问必须在另一次访问结束后 2 小时开始。 一次访问必须分配给分配给另一次访问的同一辆车。 挑战是:如何允许访问的移动而不会在移动其中一个时导致较低的分数? 每次访问可能在不同的 chine 上(分配给不同的车辆),因此所有提供的移动选择器很可能会提供仅更改一次访问的移动。 由于依赖性,此类移动很可能会导致较低的分数,并且永远不会被选中。 相同的开始场景:任何改变一次访问开始时间的动作都会导致较低的分数。 相同的车辆场景:任何改变一次访问不同车辆的移动都会导致较低的分数。 目前我正在使用 Tabu Search,结果令人满意。 延迟接受可能是答案。 谢谢。 回答1 你所描述的是一种得分陷阱。 虽然当存在分数陷阱时,延迟接受可能比禁忌搜索产生更好的结果(并且只是更改 2 行以切换到它),但它仍然会严重影响结果。 这些文档描述了 2 个摆脱分数陷阱的答案: 1) 在这种情况下,提高评分函数粒度不起作用。 2)在这种情况下,课程粒度移动将起作用。 例如,您可以添加自定义移动工厂(但也保留原始的 moveSelectors - 或者更好地使用和不使用原始 moveSelectors
  • Optaplanner: Iterate over list variable in drools rule file
    I am solving a problem similar to employee rostering. I have an additional constraint. The employees have a "type" value assigned to them. It's a hard constraint that atleast 1 employee of each "type" be there everyday. I have modelled it as follows: rule "All employee types must be covered" when $type: Constants.EmployeeType() from Constants.EmployeeType.values() not Shift(employeeId != null, $employee: getEmployee(), $employee.getType() == $type.getValue()) then scoreHolder.addHardConstraintMatch(kcontext, -100); end This rule however, does not consider that the constraint be satisfied on
  • OptaPlanner throwing IllegalStateException on CompositeMove created by CartesianProductMoveSelector
    so basically my problem is, that OptaPlanner is throwing this: java.lang.IllegalStateException: The entity (...) has a variable (previousEntry) with value (...) which has a sourceVariableName variable (nextEntry) with a value (...) which is not null. Verify the consistency of your input problem for that sourceVariableName variable. at org.optaplanner.core.impl.domain.variable.inverserelation.SingletonInverseVariableListener.insert(SingletonInverseVariableListener.java:72) at org.optaplanner.core.impl.domain.variable.inverserelation.SingletonInverseVariableListener.afterVariableChanged
  • OptaPlanner 在 CartesianProductMoveSelector 创建的 CompositeMove 上抛出 IllegalStateException(OptaPlanner throwing IllegalStateException on CompositeMove created by CartesianProductMoveSelector)
    问题 所以基本上我的问题是,OptaPlanner 正在抛出这个: java.lang.IllegalStateException: The entity (...) has a variable (previousEntry) with value (...) which has a sourceVariableName variable (nextEntry) with a value (...) which is not null. Verify the consistency of your input problem for that sourceVariableName variable. at org.optaplanner.core.impl.domain.variable.inverserelation.SingletonInverseVariableListener.insert(SingletonInverseVariableListener.java:72) at org.optaplanner.core.impl.domain.variable.inverserelation.SingletonInverseVariableListener.afterVariableChanged(SingletonInverseVariableListener.java
  • Optaplanner:迭代drools规则文件中的列表变量(Optaplanner: Iterate over list variable in drools rule file)
    问题 我正在解决一个类似于员工排班的问题。 我有一个额外的限制。 员工有一个分配给他们的“类型”值。 每天至少有 1 名每种“类型”的员工在场是一个硬约束。 我已经建模如下: rule "All employee types must be covered" when $type: Constants.EmployeeType() from Constants.EmployeeType.values() not Shift(employeeId != null, $employee: getEmployee(), $employee.getType() == $type.getValue()) then scoreHolder.addHardConstraintMatch(kcontext, -100); end 然而,这条规则并不认为约束在每一天都得到满足。 我有一个日期字符串列表。 如何以与我在 EmployeeType 枚举中相同的方式在 drools 文件中迭代它们? 编辑:我想出了一种方法,但感觉就像一个黑客。 在初始化日期字符串列表时,我还将它分配给一个静态变量。 然后我就可以使用类似于枚举的静态变量。 rule "All employee types must be covered" when $type: Constants.EmployeeType() from
  • Bicycle messenger / TSPPD with OptaPlanner
    Dear OptaPlanner experts! I would like to use OptaPlanner (or a similar Open Source Java Framework) to optimize routes for a bicycle messenger service. Let's assume 5 messengers have to pick up 30 envelopes FROM a certain origin and deliver them TO a certain destination: X(FROM) Y(FROM) X(TO) Y(TO) envelope 1 13745 55419 13883 55756 envelope 2 8406 53246 13937 55854 envelope 3 15738 57396 35996 79499 envelope 4 12045 60418 19349 57118 envelope 5 13750 56416 35733 78403 envelope 6 13190 57068 11860 59749 envelope 7 15021 55768 14098 57379 envelope 8 11513 58543 11501 59683 envelope 9 12013
  • 使用springboot optaplanner-spring-boot-starter时如何使用多个ConstraintProvider(How can we use multiple ConstraintProviders, when using the springboot optaplanner-spring-boot-starter)
    问题 optaplanner-spring-boot-starter 会自动发现ContraintProvider,不需要solverConfig.xml,所以如果我们想针对不同的问题使用多个contraintProvider,比如问题A,需要使用problemAContraintProvider ,问题B,需要使用ProblemBContraintProvider ,是有任何限定符类型的注释,我可以使用并告诉solverManger 使用特定的 ConstraintProvider 实现 public class ProblemAConstraintProvider implements ConstraintProvider { @Override public Constraint[] defineConstraints(ConstraintFactory constraintFactory) { return new Constraint[] { typeMatch(constraintFactory), timeSlotMatch(constraintFactory), }; } } public class ProblemBConstraintProvider implements ConstraintProvider { @Override public
  • optaplanner 可以使用 Drools 规则解决部分预先分配的规划实体吗?(Can optaplanner solve partly pre-assigned planning entities using Drools rules?)
    问题 我们正在使用 Optaplanner 6.2 的时间相关车辆路径问题示例。 在我们的例子中,领域模型由活动(对应于客户)和技术人员(对应于车辆)组成。 是否可以使用部分预先分配给某些技术人员的活动来初始化优化,而其余活动则不分配? 当我们停止求解或等待求解时,这将对应于 optaplanner (cvrptw-case) 的情况,然后在已解决的 xml 文件末尾添加未分配的活动。 该文件随后将作为输入文件用于进一步优化。 此处必须锁定已分配的活动。 可以这样的起始状态:在链起始处最初锁定不应重新排列的预定义活动的连续链部分- 而其余活动应进行优化并将预先分配的活动放入现有链中,处理增量约束规则(使用 Drools)? 回答1 阅读手册重复计划章节的不可移动计划实体和非易失性重新计划部分。 它解释得相当好。
  • Can optaplanner solve partly pre-assigned planning entities using Drools rules?
    We are using the time dependent vehicle routing problem example of Optaplanner 6.2. In our case the domain model consists of activities (corresponding to customers) and technicians (corresponding to vehicles). Is it possible to initialize an optimization with partly pre-assigned activities to certain technicians, whereby the rest of activities is not assigned? This would correspond to the case of optaplanner (cvrptw-case) when we stop the solving or wait for the solution, and then add at the end of the solved xml-file not assigned activities. This file would then be used for the further
  • 如何在 optaplanner 中跟踪规划变量分配(how to keep track of planning variable assignment in optaplanner)
    问题 有没有办法在计划期间访问计划变量的分配? 在我的用例中,我只想在计划期间仅分配一次具有特定状态的计划变量。 之后我不想使用该计划变量。 我知道在 optaplanner 中,计划变量/问题事实无法更改,因此我无法更改其状态。 有没有办法在计划期间获取计划变量分配列表,以便在java代码或drools文件中,如果已经使用过一次,我可以避免重新分配? 谢谢! 回答1 使用硬约束来强制执行。 是的,您也可以使用 MoveFilters,但这不是一个好主意,因为有时您需要打破硬约束以逃避局部最优。
  • SMO(序列最小优化)算法论文及原理详述
    今日拜读了Platt的关于SMO的论文:Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines。直译过来就是:序列最小优化:一种训练支持向量机的快速方法。然后根据论文及查询的相关资料整理了这篇内容。 文章目录 一、论文内容概述论文摘要1 简介部分1.2 以前的支持向量方法 2 序列最小优化2.1求解两个拉格朗日乘数2.2选择优化哪个乘数的启发式方法2.3阈值计算2.4线性支持向量机的优化2.5 代码细节2.6与以往算法的关系 3基准SMO3.1 收入预测 4 论文结论 二、SMO算法数学原理及过程推导1 SVM问题回顾:2 SMO算法2.1两个朗格朗日乘子的解析解2.2 选择哪两个乘子需要被优化的启发方法2.3 更明确的优化方法说明2.3.1 第一个变量的选择2.3.2 第二个变量的选择 2.4 计算阈值b和差值2.5 论文中计算阈值的推导 3 线性SVM的一个优化 三、SVM算法总结四、SMO解决对偶问题的二次规划 一、论文内容概述 论文摘要 本文提出了一种新的训练支持向量机的算法:序列最小优化算法。训练一个支持向量机需要解决一个非常大的二次规划(quadratic programming ,QP)优化问题。SMO将这个大的QP问题分解为一系列可能的最小的QP问题
  • Implementing a planning optimization algorithm on hierarchical problem
    I am working on a planning problem involving: a collection of planning entities each containing the planning variable A a global planning variable B (contained in the planning solution) Since I am a beginner with Optaplanner and planning optimization in general, I started on a simpler version problem, focusing on optimizing A with B modeled as a planning fact. Now that I have a program successfully optimizing A given B. I want to implement a new solver optimizing both A and B. It turns out that the best optimization search strategy is to first select a B value, and then optimize A given that B
  • Java数学优化库-免费还是开放源码建议? [关闭](mathematical optimization library for Java — free or open source recommendations? [closed])
    问题 从目前的情况来看,这个问题不适合我们的问答形式。 我们希望答案会得到事实,参考或专业知识的支持,但是这个问题可能会引起辩论,争论,民意调查或扩展讨论。 如果您认为此问题可以解决并且可以重新提出,请访问帮助中心以获取指导。 7年前关闭。 有谁知道执行数学优化(线性编程,凸优化或更常见的问题类型)的库吗? 我正在寻找类似MATLAB的东西,但具有处理更大问题的能力。 我必须编写自己的实现,还是购买其中一种商业产品(CPLEX等)? 回答1 一个好的答案取决于您所说的“凸”和“更一般”的含义。如果您试图解决大型或具有挑战性的线性或凸二次二次优化问题(尤其是对它们使用离散分量),那么很难克服主要的商业解决方案,古罗比,cplex和Dash,除非金钱对您来说是一个大问题。 它们都具有干净的JNI接口,并且可在大多数主要平台上使用。 coin-or项目有多个优化器,并且有一个用于JNI接口的项目。 它是完全免费的(EPL许可证),但设置起来会花费更多的工作,并且可能不会给您带来相同的性能。 回答2 有一个称为lpsolve的线性优化工具。 它是用C编写的(我认为),但是带有Java / JNI包装器(API不是非常面向对象,但它确实可以完成工作)。 它非常易于使用,并且在过去的一年中,我让它在实时系统中运行得非常愉快且稳定。 回答3 您可以尝试JOptimizer
  • OptaPlanner 中的详尽搜索不适用于非常简单的示例(Exhaustive Search in OptaPlanner does not work on very simple example)
    问题 我们正在尝试创建一个简单的示例来测试 OptaPlanner 的功能。 下面我们将展示我们的想法。 我们示例的问题在于,当我们选择详尽的搜索算法来解决问题时,OptaPlanner 会以错误的答案迅速终止,该答案始终为零,即使零不是 ValueRangeProvider 提供的可能解决方案。 此外,与使用本地搜索时相反,在求解期间未设置 PlanningVariable。 我们尝试更改 OptaPlanner(例如 TSP)附带的示例中的算法,该算法有效。 因此我们的问题是:为什么我们的代码不起作用? MyPlanningEntity.java: import org.optaplanner.core.api.domain.entity.PlanningEntity; import org.optaplanner.core.api.domain.variable.PlanningVariable; @PlanningEntity public class MyPlanningEntity { @PlanningVariable(valueRangeProviderRefs = {"myListValueRangeProvider"}) private int myPlanningVariable; public int getMyPlanningVariable() {
  • 没有静态方法元工厂(OptaPlanner)(No static method metafactory (OptaPlanner))
    问题 最近,我在 build.gradle 中添加了 OptaPlanner 依赖项,以便使用库的 Vehicle Routing Problem。 当我尝试使用求解器时,我收到以下错误 java.lang.NoSuchMethodError: No static method metafactory(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodType;Ljava/lang/invoke/MethodHandle;Ljava/lang/invoke/MethodType;)Ljava/lang/invoke/CallSite; in class Ljava/lang/invoke/LambdaMetafactory; or its super classes (declaration of 'java.lang.invoke.LambdaMetafactory' appears in /apex/com.android.art/javalib/core-oj.jar) 我有谷歌,发现我需要启用 JDK 1.8 与我在 build.gradle 中所做的相同,但它似乎仍然没有消失。 我也附上了 build
  • 如何在 optaplanner 中动态添加/删除约束(how to dynamically add / remove constraints in optaplanner)
    问题 我们正在为 VRP 使用 optaplanner。 我们面临的一个挑战是我们的许多限制都特定于当地。 例如,在一个州,技术人员不能跨越州界,而在其他州,技术人员可以跨越州界。 在这种情况下,我们希望创建一个通用解决方案,用户可以在其中添加硬约束,通用解决方案从数据库中选择该约束以提供解决方案。 有没有人设计过这样的解决方案? 谢谢 回答1 要么使用不同的<scoreDrl>元素: 通用文件 ny-specific.drl ca-specific.drl tx-specific.drl ... 或者,如果您需要解决同时包含 tx 和 ny 员工的单个数据集,请执行以下操作 class Employee { State state; } rule noCross when Employee(state = "Texas") // doesn't apply to California // ... crosses lines then ... end