计算科学 - 分离式编程软件 - 吾爱随笔录

分离式编程软件

计算科学二次规划软件推荐

2021-12-22 17:34:15

你能告诉我任何可以帮助解决析取编程问题的现有软件吗？

问题如下。

我们有单位 3D 平面（它们是已知的）。让我们将它们写成如下：。 $\Pi_{1}, \ldots, \Pi_{N}$ $U_{j} x = H_{j}, j = 1, \ldots, N$

有了固定的数字和，我们想要找到 3D 平面和 3D 点使得： $n$ $m$ $\pi_{1}, \ldots, \pi_{n}$ $x_{1}, \ldots, x_{m}$

平面和点满足关联结构：，其中是固定已知集。 $x_{i} \in \pi_{j}\;\;\forall(i, j) \in I$ $I$ $I \subseteq \{1, \ldots, m\} \times \{1, \ldots, n\}$
由平面界定的多面体是凸的。 $\pi_{1}, \ldots, \pi_{n}$

并最小化函数。 $\sum \limits_{j = 1}^{N}(H_{j} - \max \limits_{i = 1, \ldots, m} (x_{i}, U_{j}))^{2}$

由于我们在泛函中有一个，所以上述问题可以表述为一个析取编程程序，如下所示： $\max$

\begin{aligned} minimize \sum_{j = 1}^{N} (H_{j} - L_{j})^{2} \\ subject to (1 - 2) and \forall j = 1, \dots, N \exists i such that (x_{i}, U_{j}) = H_{j} . \end{aligned}

$\begin{align} &\text{minimize} \sum \limits_{j = 1}^{N}(H_{j} - L_{j})^{2}\\ &\text{subject to } \, (1-2) \text{ and } \forall j = 1, \ldots, N\; \exists i \text{ such that } (x_{i}, U_{j}) = H_{j} \enspace . \end{align}$

我从互联网上读到这样的问题被称为析取编程。你能给出任何提示可以使用哪个软件来解决它吗？

1个回答

我没用过，但是Pyomo，一个看似得到很好支持的建模软件，包含一个用于广义析取编程的模块。

他们在上述链接中提供的众多示例之一如下所示：

m = ConcreteModel()
m.s = RangeSet(4)
m.ds = RangeSet(2)
m.d = Disjunct(m.s)
m.djn = Disjunction(m.ds)
m.djn[1] = [m.d[1], m.d[2]]
m.djn[2] = [m.d[3], m.d[4]]
m.x = Var(bounds=(-2, 10))
m.d[1].c = Constraint(expr=m.x >= 2)
m.d[2].c = Constraint(expr=m.x >= 3)
m.d[3].c = Constraint(expr=m.x <= 8)
m.d[4].c = Constraint(expr=m.x == 2.5)
m.o = Objective(expr=m.x)

# Add the logical proposition
m.p = LogicalConstraint(
   expr=m.d[1].indicator_var.implies(m.d[4].indicator_var))
# Note: the implicit XOR enforced by m.djn[1] and m.djn[2] still apply

# Apply the Big-M reformulation: It will convert the logical
# propositions to algebraic expressions.
TransformationFactory('gdp.bigm').apply_to(m)

# Before solve, Boolean vars have no value
Reference(m.d[:].indicator_var).display()

# Solve the reformulated model
run_data = SolverFactory('glpk').solve(m)
Reference(m.d[:].indicator_var).display()

从中我们学到了几件事。

语法有点尴尬。但是，它们在链接中提供了更简洁的语法。
它们具有可用于使 GDP 可供各种求解器访问的转换。上面的示例显示了 Big-M 转换。这些不会引入额外的变量，但往往比 Hull 变换更宽松一些。他们还有一个实验性的混合 Big-M/Hull 变换和一个直接处理 GDP 的求解器。请参阅此处的转换/重新制定列表。
Pyomo 可以与多个求解器交互。这很棒，因为它允许您尝试找出适合您的问题的求解器。特别是，有许多开源求解器可以很好地解决小问题；但是，对于较大的问题，您可能需要使用商业求解器。Pyomo 使这成为可能。

如果出于某种原因，您需要手动进行 GDP 转换

IE Grossmann 和 JP Ruiz。广义析取编程：用于 MINLP 优化的公式和替代算法的框架。载于 J. Lee 和 S. Leyffer，编辑，混合整数非线性规划，第 93-115 页，纽约，纽约，2012 年。Springer 纽约。国际标准书号 978-1-4614-1927-3。

对 MINLP 变换有一个不错的解释，而对船体变换有一个不太容易理解的解释。

其它你可能感兴趣的问题

上一篇我们如何用有限差分法和 Newton-Raphson 法求解耦合 PDE？下一篇用于带状线性系统的 3 级 BLAS 加速求解器。