组合向量加法最小化问题

Question

我正在研究一个问题，感觉它可能类似于数学编程中存在的问题，但我找不到任何这样的问题。

问题是这样的：我们有n组d维向量，这样每组都包含正好d + 1个向量。在每个集合中，所有向量具有相同的长度（此外，集合中任何两个向量之间的角度对于任何集合都是相同的，但我不确定这是否相关）。然后，我们需要从每个集合中精确选择一个向量，并计算这些向量的总和。我们的目标是做出我们的选择，以便最小化向量的总和。

感觉问题与最短向量问题或作业调度的变体有关，其中在机器上调度作业会影响所有机器或分区问题。

这个问题响了吗？具体来说，我正在寻找解决这个问题的研究，因为目前我最好的选择是使用ILP，但我觉得必须有更聪明的事情可以做到。

Answer 1

我认为这是一个MIQP（混合整数二次规划）或MISOCP（混合整数二阶锥）问题：

让

 v(i,j) be i vectors in group j (data)
 x(i,j) in {0,1}: binary decision variables
 w: sum of selected vectors (decision variable)

然后问题可以表述为：

 min ||w||
 sum(i, x(i,j)) = 1   for all j
 w = sum((i,j), x(i,j)*v(i,j))

如果你想要你可以替换w。实际上我没有使用你的角度限制（这是对数据的限制，而不是对模型的决策变量的限制）。选择x变量，使得我们从每个组中精确选择一个向量。

最小化2范数可以通过最小化元素的平方和（即最小化范数的平方）来代替。

假设2范数，这是一个MISOCP问题或凸MIQP问题，可用的解决方案很多。对于1范数和无穷小范数，我们可以形成线性MIP问题。 MIP求解器广泛可用。