计算科学 - 使用线性表达式对二次约束建模 - 吾爱随笔录

计算科学优化线性规划二次规划

2021-12-16 18:22:11

在我尝试使用 MIP 程序建模的问题中，会出现以下情况：

我得到二进制变量 $x_1,\ldots,x_n$ 和 $y_1,\ldots,y_n$ 真的可以认为是 $n$ -向量。我需要计算的是它们不同的位数。特别是我只需要确保它们最多只有一位相等。

这可以通过添加以下二次约束来完成

\sum_{i = 1}^{n} x_{i} y_{i} \leq 1

$\sum_{i=1}^n x_i y_i \leq 1$

鉴于这种情况的特殊性质，我想知道

有没有更好的表达方式？

和

有没有把这个表达式转换成线性表达式的技巧？

2个回答

引入一个新变量 $z_i$ 代表 $x_iy_i$ （逻辑和）。你的约束是 $\sum_{i=1}^n z_i \leq 1$ , 产品由 $x_i + y_i -1 \leq z_i$ .

认为

z_{i} = x_{i} \times y_{i}

$z_{i} = x_{i} \times y_{i}$ 约束

\sum_{i = 1}^{n} x_{i} y_{i} \leq 1

$\sum_{i=1}^{n} x_{i}y_{i}\le 1$ 可以重新表述为线性约束：

\sum_{i = 1}^{n} z_{i} \leq 1

$\sum_{i=1}^{n} z_{i}\le 1$ 2)

z_{i} \leq x_{i}

$z_{i}\le x_{i}$ 3)

z_{i} \leq y_{i}

$z_{i}\le y_{i}$ 4)

z_{i} \geq x_{i} + y_{i} - 1

$z_{i}\ge x_{i} + y_{i} -1$

其它你可能感兴趣的问题