将数字 (x1, x2, x3, ...) 分配给列表 (a1, a2, a3, ...) 中的每个元素，以便 a1/x1 类似于 a2/x2 等等

Question

假设我有一个数字列表 = [3, 10, 20, 1, ...] 如何为列表中的每个元素分配一个数字 (x1, x2, x3, x4, ...)，以便 3/x1 ~= 10/x2 ~= 20/x3 ~= 1/x4 = . .. ?

编辑：数字有一些限制（x1、x2、x3...）。它们必须从可用数字列表中挑选（也可以是浮点数）。问题是元素的数量不一样。有更多的 X 元素。 X可以赋值多次。

目标是最小化 3/x1、10/x2、20/x3、1/x4 之间的差异

Answer 1

它通常有助于开发数学模型。例如

让

   a(i)>=0  i=1,..,m
   b(j)>0   j=1,..,n with n > m

是数据。

引入变量（由模型决定）

   c      =  common number for all expressions to be close to
   x(i,j) =  1 if a(i) is assigned to b(j)
             0 otherwise

那么我们可以这样写：

min sum((i,j), (x(i,j)*(a(i)/b(j) - c))^2 )
subject to
    sum(j, x(i,j)) = 1   for all i  (each a(i) is assigned to exactly one b(j))
    x(i,j) in {0,1}
    c free

这是一个 non-linear 模型。 MINLP（混合整数 Non-linear 编程）求解器很容易获得。也可以选择一个可以线性化的objective：

min sum((i,j), abs(x(i,j)*(a(i)/b(j) - y(i,j))) )
subject to
    y(i,j) = x(i,j)*c
    sum(j, x(i,j)) = 1   for all i
    x(i,j) in {0,1}
    c free

这可以重新表述为 MIP（混合整数规划）模型。有许多可用的 MIP 求解器。

解决方案可能如下所示：

矩阵内的值为a(i)/b(j)。每一行对应一个a(i)，并且恰好有一个匹配的b(j)。

更多详情here。

将数字 (x1, x2, x3, ...) 分配给列表 (a1, a2, a3, ...) 中的每个元素，以便 a1/x1 类似于 a2/x2 等等

Allocating numbers (x1, x2, x3, ...) to each element in a list (a1, a2, a3, ...) so that a1/x1 is similar to a2/x2 and so on

algorithm

minimization

constraint-programming