在python3中使用CVXPY进行整数线性规划

Question

我正在尝试使用 CVXPY 解决整数线性规划问题，但我在一些语法上苦苦挣扎，并且无法找出一种方法来强制执行我有兴趣解决的约束取值为 0 或1. 我认为将它设置为布尔值是 Variable 对象中的解决方案，但由于某种原因我没有得到我想要的

我安装了 cvxpy 库并尝试使用一个小示例运行它来解决它。我的问题的输入是一个大小为 (I, J) 的二进制矩阵 M，它的值只有 (0 或 1)，而且我想求解的变量是一个布尔值（或再次二进制向量）向量 P尺寸 J，

目标函数是最小化我的大小为 J 的变量向量的值的总和（即最小化该向量内 1 的数量）

使得我的矩阵的每一行的总和 M 乘以我的变量向量 P 大于或等于 1。即，对于所有 i，Mij*Pj >= 1 的总和（超过 j）。

以最小化向量 P 的总和为目标。

我编写了以下代码来做到这一点，但是我正在努力寻找我做错了什么。

import numpy as np
import cvxpy as cp

M = np.array([[1,0,0,0], [1,0,0,0], [0,1,1,0], [1,0,0,0], [0,0,1,1], [0,0,1,0]])

variable= cp.Variable(M.shape[1], value = 1, boolean=True)

one_vec = np.ones(M.shape[1])

obj = cp.Minimize(sum(np.dot(variable, one_vec)))

constraints = []

for i in range(len(M)):
    constraints.append(np.sum(np.dot(M[i], variable)) >= 1)

problem = cp.Problem(obj, constraints=constraints)

problem.solve()

因此，作为对我的代码中矩阵 M 给出的这个简单示例的答案，答案应该是变量向量的值应该是 [1, 0, 1, 0]，因为乘以向量 [1, 0, 1, 0 ] 与矩阵

[[1, 0, 0, 0]

[1, 0, 0, 0]

[0, 1, 1, 0]

[1, 0, 0, 0]

[0, 0, 1, 1]

[0, 0, 1, 0] ]

将为每一行提供至少 1 的值。

但是如果我运行我编写的这段代码，我会得到一个浮点值作为我的答案，因此我做错了一些我无法弄清楚的事情。我猜我不知道如何以编程方式表达这个问题，以便求解器可以解决它。任何帮助将不胜感激。谢谢。

Answer 1

更新！我想我明白了

我将代码修改为：

import numpy as np
import cvxpy as cp

M = np.array([[1,0,0,1], [1,0,0,1], [0,1,1,1], [1,0,0,1], [0,0,1,1], [0,0,1,1]])

selection = cp.Variable(M.shape[1], boolean = True)
ones_vec = np.ones(M.shape[1])

constraints = []
for i in range(len(M)):
    constraints.append(M[i] * selection >= 1)

total_genomes = ones_vec * selection

problem = cp.Problem(cp.Minimize(total_genomes), constraints)

problem.solve()

现在它正在发挥作用。我使用 * 运算符而不是 numpy 点积，cvxpy 已重载该运算符，我认为可以执行向量乘法。