计算科学 - 大型二进制编程问题 - 吾爱随笔录

大型二进制编程问题

计算科学优化算法线性求解器

2021-12-14 11:12:48

我有 10000 个变量（每个变量都是二进制的）、正系数向量和一个矩阵 $A$ ( $10000\times10000$ ），如果 $A_{ij}=1$ ，然后 $i$ 和 $j$ th 个变量可以同时取 1，如果取 0 则不可能。目标是最大化它们的加权和。我可以使用什么算法和软件来解决这个问题？

\begin{array}{l} max F (x_{1} . . x_{m}) = \sum_{i = 1}^{m} b_{i} x_{i} \end{array}

$\begin{array}{l} \max F\left( x_{1}..x_{m} \right)=\sum\limits_{i=1}^m {b_{i}x_{i}} \end{array}$

\begin{array}{l} x_{i} \in {0, 1}, i = 1.. m \\ x_{i} x_{j} \leq A_{i j}, i, j = 1.. m \\ A_{i j} \in {0, 1}, i, j = 1.. m \end{array}

$\begin{array}{l} x_{i}\in \left\{ 0,1 \right\},\, \, i=1..m \\ x_{i}x_{j}\le A_{ij}\,, i,j=1..m \\ A_{ij}\in \left\{ 0,1 \right\},\, \, i,j=1..m \\ \end{array}$

2个回答

编辑之前的以下答案将“不可能”一词解释为“不可能取 1”。如果我们将其读作“不可能都取 1”，那么这个答案不适用。

如果我正确阅读了这个问题，在我看来，这个问题比最大重量集团问题要容易得多。它似乎是。给定的系数都是正的，因此很明显，给定一组系数的最大加权和将是都为 1 的地方。所以我们希望它们为 1，除非它们不能为 1。初始化为 1，遍历元素，如果这些矩阵元素为 0，则将相应的和设置为 0。然后我们在向量 $O(m^2)$ $b_i$ $x_i$ $x_i$ $m^2$ $A_{ij}$ $x_i$ $x_j$ $x$ 矩阵允许我们拥有，并且加权和最大化。

最好的想法是使用针对您的特定优化问题结构量身定制的算法。

不使用任何专门针对这个问题量身定制的算法，你就有了一个 MINLP，并且没有解决一般大型 MINLP 的真正好方法；在撰写本文时，“大”可能是数百或数千。

格洛弗在将这些问题重新表述为 MILP 方面做了一些工作；基本思想是注意对于，一些有效的不等式成立，比如 $x_{i}, x_{j} \in \{0, 1\}$

\begin{aligned} x_{i} x_{j} & \geq x_{i} + x_{j} - 1 \\ x_{i} & \geq x_{i} x_{j} \\ x_{j} & \geq x_{i} x_{j} \end{aligned}

$\begin{align} x_{i}x_{j} &\geq x_{i} + x_{j} - 1 \\ x_{i} &\geq x_{i}x_{j} \\ x_{j} &\geq x_{i}x_{j} \end{align}$

您添加这些不等式并将替换为变量。但是，这样的重新表述大大增加了问题中二元变量的数量，所以我怀疑这是一个可行的选择。这个想法的其他版本在重新表述的大小上有所不同，但每个重新表述的大小数量级或多或少是相同的。 $x_{i}x_{j}$ $z_{ij} \in \{0, 1\}$

其它你可能感兴趣的问题

上一篇如何强制执行边界条件下一篇用于高效/轻松实现二维泊松方程的有限体积法的数据结构