这是整数规划吗？

Question

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

dlm

Answer 1

是的，这是一个整数规划问题。您可以将其写为：

   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

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

    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 求解器来解决上述问题。

Answer 2

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

I。贪婪算法

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

这将使您结束解决方案

II。进化算法

对问题的严格定义使您可以使用遗传算法。
总体将是 X=[x1,x2,x3,x4...xn] 的向量
适应度函数很明显（期望总和与 X 计算总和之间的差异）

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

Answer 3

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

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)

这只是搜索令人满意的解决方案。需要加强该算法以处理差异-最小化，无论这意味着什么）

Answer 4

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