2

问题：n 个变量 (x) 加起来是一个常数。x1+x2+..+xn = const，其中每个 x 只能取 p（比如 5）个正整数值。我们希望找到 x 之间的差异最小化的解决方案，即它们分布最均匀。这是一个整数规划问题吗？

dlm

4

4 回答 4

4

是的，这是一个整数规划问题。你可以把它写成：

   minimize  |x1 - x2| + |x2 - x3| + ... + |xn-1 - xn|

   subject to  x1 + x2 + x3 + ... + xn == c,

               xi == Ai1*yi1 + Ai2*yi2 + ... + Aip*yip, i=1,...,n,

               yi1 + yi2 + ... + yip == 1, i=1,...,n,

               yij binary for i=1,...,n  j=1,...,p,

               xi integer for i=1,...,n,

这里 Aij 是已知的输入数据，描述了 xi 的特定值可能采用的整数。下面是一个具有 3 个变量 (n=3) 的具体示例，其中每个 xi 可以取两个整数值之一 (p=2)。即 x1 可以是 1 或 3，x2 可以是 3 或 4，x3 可以是 2 或 3。

    minimize  |x1 - x2| + |x2 - x3| 

    subject to  x1 + x2 + x3 == 8, 

                x1 == 1*y11 + 3*y12, 
                x2 == 3*y21 + 4*y22,
                x3 == 2*y31 + 3*y32,

                y11 + y12 == 1, 
                y21 + y22 == 1,
                y31 + y32 == 1,

                yij binary i=1,2,3 j=1,2
                xi integer i=1,2,3

您可以通过创建一组新的变量 u 来表示目标函数，将上述问题重新表述为 MIP（混合整数程序）。

    minimize   u1 + u2 + ... + un 

   subject to  ui >= xi - xi+1, i=1,...,n-1,

               ui >= xi+1 - xi, i=1,...,n-1,

               x1 + x2 + x3 + ... + xn == c,

               xi == Ai1*yi1 + Ai2*yi2 + ... + Aip*yip, i=1,...,n,

               yi1 + yi2 + ... + yip == 1, i=1,...,n,

               yij binary for i=1,...,n  j=1,...,p,

               xi integer for i=1,...,n,
               ui real    for i=1,...,n-1,

您可以使用任何标准MIP 求解器来解决上述问题。

于 2011-09-21T16:43:03.057 回答
0

这似乎是 np-complete 问题，实际上您需要搜索整个解决方案空间以获得正确的分布。也许试试这个

一、贪心算法

foreach x in xses
   if current_sum < desired_sum:
       take maximal p for x
   else take_minimal p for x

如您所见，这不会为您带来正确的解决方案，可能您的 SUM 会大于 DESIRED_SUM

但在此之后你可以开始优化你的分布：现在我们有一组贪婪的选择 xses

foreach x:
   if current_sum > desired_sum
       change taken P to minimal P for x
   else
     break

这将使您接近解决方案

二、进化算法

对问题的严格定义会将您带到遗传算法。人口将是 X=[x1,x2,x3,x4...xn] 适应度函数的向量，这很明显（所需总和与 X 计算总和之间的差异）

只需对向量进行适当的进化操作，它应该会在短时间内为您带来优化的解决方案

于 2011-04-28T09:04:12.577 回答
0

至于目标函数，当你想最小化集合之间的差异时，这是一个技巧。简单的形式可以是 Sum(ABS(Xi-Xj))，其中 i>j。可以线性化。但是，如果您想使用示例变体，那将成为 QIP 并且需要更多时间来解决。

于 2012-08-02T07:27:42.767 回答
0

您对整数有任何限制（或额外信息）吗？如果它们不是太大，则可以执行一种算法来遍历所有可能的总和（不进行所有组合）：

function adds_up_to(xs, N):
    sums := {0}
    for i from 1 to n:
        new_sums := {}
        for sum in sums:
            for value in values:
               new_sums := new_sums U {sum + value}
        sums := new_sums
    return (N in sums)

（这只是寻找一个令人满意的解决方案。需要加强算法以处理差异最小化，无论这意味着什么）

于 2011-04-29T02:38:31.533 回答