一组一阶 DE 的二进制整数规划问题

计算科学 混合整数规划
2021-12-25 05:31:29

最近，我遇到了一个二元决策变量的优化问题，该问题受到一组一阶微分方程的约束（由连续时间马尔可夫链模型产生）。目标函数是通过一阶微分方程组获得的部分概率集的总和。根据特定的状态转换图，二进制变量强加是否可以从一种状态转换到另一种状态。

由于存在求解一阶微分方程组的求解方法，因此该问题的一种简单求解方法是搜索二元决策变量的可行域，并求解得到的一阶微分方程组以获得目标函数值. 但是，我仍然想知道是否有任何确切的解决方法。

所以，我的问题有两个：

  1. 解决此类问题的其他（最好是确切的）可用解决方案是什么？

  2. 这类问题是否有解决方案（开源或商业）？

任何有关建模和解决此类问题的介绍的参考都受到高度赞赏。

附言。我已经看到了一些关于受偏微分方程约束的优化问题的资料，这些资料似乎植根于控制理论。这两类问题之间有什么关系吗？

2个回答

免责声明：我不是该领域的专家；我刚刚和做这种事情的人一起工作过。

二元决策总是使用美化的猜测和检查算法来解决

暂时不考虑微分方程，混合整数线性（或非线性）规划求解器的任何整数分量都可能会使用某种分支定界或分支切割方法来求解混合整数问题的一部分。这些方法是进行猜测和检查的复杂方法，并且存在将测试二元决策变量的每个可能值的病态情况。

您提到的第一种方法是精确的（前提是您可以精确地求解微分方程），并且可以解决问题。在实践中，我认为只要您能够以高精度数值求解微分方程，您可能会获得正确的最优目标函数值。

解决此类问题的其他可用解决方案是什么？

我知道的有几个：

  • 离散化，然后优化：微分方程通常以数值方式求解（除非您可以以其他方式构造解），并且这些数值解是由离散方程构造的。也称为搭配方法，您基本上会选择一个求积规则（例如，类似于 Radau 方法）以及为您的微分方程指定的时间步长。求积法则和时间步长将微分方程系统转换为非线性代数方程系统，因此您的优化问题变成了一个混合整数非线性程序，然后您可以求解。这种方法可能并不精确，除非时间步长足够小，以至于 ODE 的数值解是准确的。它通常会创建一个庞大的约束系统。Larry Biegler 的论文可能是这种方法的很好参考。
  • 优化，然后离散化：用约束条件下的必要最优性条件替换您的优化问题。一种重新表述使用 Karush-Kuhn-Tucker (KKT) 条件和 Slater 点约束条件；还有其他人。然后离散化得到的 KKT 条件并求解。对于二元决策变量，我不确定这种方法将如何工作，因为 KKT 条件不适用，但如果您的决策变量是连续的，那么这种方法会更有意义。除非目标函数和约束是凸的，否则 KKT 条件不足以达到最优；通常，ODE 约束的优化问题不满足这些凸性条件。
  • 优化而不离散化：构建原始问题的一系列松弛和限制，同时使用类似于非凸优化中的分支定界方法。Paul Barton 使用这种方法发表论文；他是我的博士生导师之一。这种方法是精确的，但需要大量的数学和编程基础设施。

与 PDE 约束优化的关系

我在上面列表中提到的前两种方法也用于 PDE 约束优化。第三个尚未针对 PDE 案例开发。我怀疑它可能是可行的，但我不知道它是否可行。

Geoff 提到的“离散化，然后优化”方法是解决混合整数微分代数方程系统的APM MATLAB 或 APM Python包的一部分。我们正在杨百翰大学的研究小组中开发这个软件。下面是我们最近在 2012 INFORMS 会议上发布的演示文稿的链接，该演示文稿提供了更多详细信息和几​​个示例应用程序。

Hedengren, JD, Mojica, JL, Cole, W., Edgar, TF, APOPT：具有基准测试的微分代数系统的 MINLP 求解器，INFORMS全国会议，亚利桑那州凤凰城，2012 年 10 月。

如果您对这类问题的数值解法感兴趣，APMonitorCom YouTube 频道上有许多教程视频。

其它你可能感兴趣的问题
上一篇迭代方案的根收敛率 下一篇在matlab中求解两个耦合二阶微分方程的输出问题