algorithm - 组合向量加法最小化问题

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 求解器应用广泛。