混合整数线性规划：如何生成约束？

Question

我有一个objective函数，例如

（为简单起见，我省略了系数）。

我想使用 intlinprog 来最小化此函数，但有以下限制：

和

所有 x 二进制文件。这些总和导致这 4 个不等式：

显然contains矩阵是

如果我手动创建此矩阵，则效果很好。现在假设我的 objective 函数和约束（相同模式）中有 6 个或 8 个或 10 个变量而不是 4 个。我怎样才能使用 Matlab 为这些更大的问题生成这个约束矩阵？

Answer 1

我建议写下其他一些案例。因此，您似乎想要约束所有行总和和所有列总和：

对于 N=3，有 9 个变量（我在这里假设是正方形；您没有提供完整信息）：

x00 x01 x02
x10 x11 x12
x20 x21 x22

现在约束矩阵如下所示：

x00 x01 x02 | x10 x11 x12 | x20 x21 x22
---------------------------------------
1   1   1
              1   1   1
                            1   1   1
1             1             1
    1             1             1
        1             1             1

这很正常。现在还不是检查 matlab 的矩阵创建函数的时候。遗憾的是我不是一个 matlab 用户，但是：

行的下半部分包括：

每个大小为 N 的 N 个单位矩阵的水平堆叠

行的上半部分包括:

N 个 1 行向量的块对角矩阵，每个大小为 N

最终矩阵是两个分量的垂直堆叠

一个完整的稀疏矩阵 python-示例（抱歉，这里没有 matlab；但应该有一个 1:1 映射），更清楚的是：

import numpy as np
import scipy.sparse as sp

N = 3
component_a = sp.hstack([sp.eye(N) for i in range(N)])
row_full_1 = sp.csr_matrix(np.ones(N))
component_b = sp.block_diag([row_full_1 for i in range(N)])  # matlab: blkdiag?
matrix = sp.vstack((component_b, component_a))

print(matrix.todense())

输出：

[[ 1.  1.  1.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  1.  1.  1.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  1.  1.  1.]
 [ 1.  0.  0.  1.  0.  0.  1.  0.  0.]
 [ 0.  1.  0.  0.  1.  0.  0.  1.  0.]
 [ 0.  0.  1.  0.  0.  1.  0.  0.  1.]]

备注： 取决于N，你需要考虑使用密集矩阵还是稀疏矩阵。给定 N，矩阵中非零元素的比例将为 1/N.

混合整数线性规划：如何生成约束？

Mixed-integer linear programming: How to generate constraints?

optimization

matlab

constraints

matrix

mathematical-optimization