variable-assignment - 分配优化/集合覆盖

Question

我有以下任务，但没有找到任何可行的解决方案。

我需要找到网络节点放置的最佳解决方案。目标是最小化连接电缆的挖掘成本。一些挖掘成本取决于彼此。例如，假设您连续有 2 个节点并将一根电缆挖到第一个节点，那么您不必将挖掘成本计入第一个节点以挖掘到第二个节点。但是，如果您只选择第二个节点，则必须添加挖掘到节点 1 和从节点 1 到节点 2 的成本。

对于每个节点，都有一定数量的用户可以由它提供。达到至少例如90％的用户的用户覆盖率是限制条件。

我尝试使用二次规划，但 cvx 不喜欢它：

cvx_begin
variable x(n,1) binary;
minimize( x'*Q*x )
subject to
   x'*A*x >= 0.9;
cvx_end

有没有人有更好的主意......使用例如二进制线性或二次编程？

谢谢和BR

score 1 · Accepted Answer

x'Ax是的总和a(i,j)*x(i)*x(j)。产品z(i,j)=x(i)*x(j)可以通过以下方式线性化：

z(i,j) <= x(i)
z(i,j) <= x(j)
z(i,j) >= x(i)+x(j)-1
z(i,j) in {0,1}

有了这个，你就有了一个线性 MIP 问题。

我们可以在这个公式中使用一些优化：

1 回答 1