每个组织都面临规划问题:为产品或服务提供有限的受约束的资源(员工、资产、时间和金钱)。OptaPlanner用来优化这种规划,以实现用更少的资源来做更多的业务。 这被称为Constraint Satisfaction Programming(约束规划,这是运筹学学科的一部分)。
OptaPlanner 是一个轻量级、可嵌入的约束满足问题求解引擎,可优化规划问题。它适用的场景例如:
规划问题存在一个基于有限资源和特定规则的最优解。最优解可以是任何数量的事务,例如:
实现这些目标的能力取决于可用资源的数量,例如:
还必须考虑与这些资源相关的特定限制,例如一个人的工作小时数、他们使用某些机器的能力或设备之间的兼容性。
OptaPlanner可以帮助Java程序员有效地解决约束满足问题。它使用非常有效的得分计算,将优化启发式和元启发式算法结合在一起。
NP-Hard问题是指在多项式时间内无法解决的问题。这些问题通常是非常困难的,因为它们的解决需要大量的计算资源。NP-Hard问题的例子包括旅行推销员问题、分治问题等。 NP-Complete问题是指在多项式时间内可以解决,但在NP-Hard问题的解决过程中可以被解决的问题。这些问题的解决通常比NP-Hard问题的解决要快,但仍然需要大量的计算资源。NP-Complete问题的例子包括完全背包问题、分支界限问题等。
前面提到的所有场景都可能是NP-Complete或者NP-Hard的,也就是说:
这意味着解决问题可能比你预期的要困难,因为常用的技术不足以解决问题:
通过使用先进的优化算法,OptaPlanner 可以在合理的时间内为这类规划问题找到接近最优的解决方案。
通常,规划问题存在至少两个级别的约束:
某些问题也可能存在积极的约束:
某些基础问题(例如N皇后问题)只存在硬约束。某些问题存在三个或更多级别的约束,例如硬、中等、软约束。 这些约束定义了规划问题的得分计算(也称为适应度函数)。规划问题的每个解决方案都可以用得分评级。在 OptaPlanner 中,得分约束用面向对象的语言(例如Java代码)编写。这样的代码易于编写、灵活且可扩展。
规划问题有许多解决方案。 这些解决方案可划分为以下几类:
与直觉相反,即使数据集很小,可能方案的数量也是巨大的(如果计算正确的话)。正如你在例子中看到的,大多数案例比已知宇宙中原子的数量(10^80)有更多的可能方案。由于没有找到最优解决方案的灵丹妙药,因此任何实现都必须评估一部分的可能方案。
OptaPlanner支持多种优化算法,可以有效地处理大量可能方案。 根据用例的不同,某些优化算法的性能优于其他算法,但无法提前判断。使用 OptaPlanner,只需几行XML或代码来修改求解器的配置,即可轻松切换优化算法。