1

私は、分岐限定アルゴリズムで解決しなければならない問題に取り組んでいます。出発点からの距離の値が異なる n 個のガソリンスタンドがあるとします。ステーションにはさまざまな利益があります。利益を最大化したいのですが、各ステーションは少なくとも K の長さ離れている必要があります。動的アルゴリズムでこの問題を解決しましたが、分岐限定アルゴリズムの解決策を見つけることができませんでした。実際、境界を決定するには適切な目的関数が必要です。多くの機能を試しましたが、すべて失敗しました。ありがとう。

例：n=5 k=10

距離値 l1= 5、l2=15、l3=23、l4=30、l5=38

利益: p1=7、p2=3、p3=10、p4=12、p5=6

4

1 に答える 1

0

これはかなり典型的なパッキングの問題です。このように整数プログラムとして定式化できます。駅を開いた場合とそうでx_iない場合があります。それから目的は、1i0

          n
maximize sum profit_i x_i.
         i=1

制約は、距離内に 2 つの駅を開設しないことですk。ステーション上で長さのウィンドウをスライドさkせて、最大サブセットごとに制約を発行できます。距離値l_1 = 5, l_2 = 15, l_3 = 23, l_4 = 30, l_5 = 38とk = 16については、制約があります。

x_1 + x_2       <= 1    (y_1)    { 5, 15}
x_2 + x_3 + x_4 <= 1    (y_2)    {15, 23, 30}
x_3 + x_4 + x_5 <= 1    (y_3)    {23, 30, 38}.

最後に、各駅が開いているかどうかです。

for all i, x_i in {0, 1}

二元性

私たちがこのようなトラブルに巻き込まれる理由は次のとおりです。まず、 に置き換えることで制約を緩和できx_i in {0, 1}ますx_i >= 0。これで線形計画ができました。私達はことを知っています

value of linear program >= value of integer program,

整数計画法のすべての解は、線形計画法の有効な解だからです。線形プログラムの素晴らしい点は、特定の技術的制約の下で、LP 双対性によって、次の条件を満たす双対プログラムがあることです。

value of dual program = value of linear program >= value of integer program.

ここでの双対計画は最小化であるため、これは重要です。そのため、古い解決策は元の整数計画 (つまり、実際に関心のある問題) に制限を与えます。

デュアルプログラム

これは、線形プログラムから機械的に導出されます。以下、直感的に説明します。一般版:

          m
minimize sum y_j
         j=1
for all i, sum over windows j containing station i of y_j >= profit_i
for all j, y_j >= 0.

具体的なバージョン (上記の具体的な LP のデュアル):

minimize y_1 + y_2 + y_3
y_1       >= profit_1    (x_1)
y_1 + y_2 >= profit_2    (x_2)
y_2 + y_3 >= profit_3    (x_3)
y_2 + y_3 >= profit_4    (x_4)
y_3       >= profit_5    (x_5).
y_1, y_2, y_3 >= 0.

直観的に、どの駅を建設しても損益分岐点になるように、各ウィンドウにどれだけの負担をかけるかを計算しています。私たちが徴収しなければならない税金が少なければ少ないほど、ステーションの価値は低くなります。

主双対近似

二重計画法は LP で解くことができます (実際には、整数最適化の可能性があります。これは変装した最短経路問題です)。これは、実装がより簡単な近似アルゴリズムです。

満たされていない二重制約の左側にある場合、それぞれy_iがアクティブです。一部y_iがアクティブである間、すべてy_iのアクティブ を同じ割合で継続的に増やします。実際には、最初にどの制約が満たされているかを判断し、次にその時点まで時間を直接進めます。

制約が以前と同じであると仮定しましょう。

y_1       >= profit_1 = 1
y_1 + y_2 >= profit_2 = 2
y_2 + y_3 >= profit_3 = 4
y_2 + y_3 >= profit_4 = 5
y_3       >= profit_5 = 3.

最初は、すべての変数が0アクティブです。それらが にヒット1すると、profit_1およびprofit_2制約が満たされます。したがってy_1、他の制約に関与しないため、非アクティブ化されます。とまで増加y_2し続け、制約が満たされます。両方の変数が制約に参加するため、アクティブなままになります。に増加すると、制約が満たされ、アクティブではなくなります。値のとの最終的な解をに増やしていきます。最適値は (例) and andで、値は です。y_32profit_3profit_42.5profit_4y_2y_33y_1 = 1y_2 = 2.5y_3 = 36.5y_1 = 1y_2 = 2y_3 = 36

于 2015-05-04T01:38:20.727 に答える