2

問題: n 個の変数 (x) が合計されて const になります。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は2つの整数値（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

オブジェクティブ機能は、セット間の違いを最小限に抑えたい場合のコツです。単純な形式は、i> jであるSum（ABS（Xi-Xj））である可能性があります。これは線形化できます。ただし、サンプルバリアントを使用する場合は、QIPになり、解決に少し時間がかかります。

于 2012-08-02T07:27:42.767 に答える
0

それはnp-completeの問題のようです.実際には、適切な配布を得るためにソリューションの全空間を検索する必要があります. 多分これを試してみてください

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

これにより、解決に近づくことができます

Ⅱ．進化的アルゴリズム

問題を厳密に定義すると、遺伝的アルゴリズムにたどり着きます。母集団は X=[x1,x2,x3,x4...xn] のベクトルになります。それは明らかです (希望する合計と X から計算された合計の差)

ベクトルに対して適切な進化操作を行うだけで、短時間で最適化されたソリューションに到達するはずです

于 2011-04-28T09:04:12.577 に答える
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 に答える