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

Question

我有一个目标函数如

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

我希望尽量减少使用intlinprog有以下限制此功能：

和

与所有的X二进制文件。这些款项导致这些不平等现象4：

很明显的是，constaints矩阵是

这种运作良好，如果我手动创建此矩阵。现在假设我的目标函数和约束（相同模式）中有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列向量的

• 块对角矩阵s各自的大小为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。