2

線形制約のある単純な LP があります。多くの決定変数があり、約 2,400 万です。私は R で lpSolve を使用して小さなサンプルで遊んでいますが、このソルバーはうまくスケーリングしません。LP の近似解を得る方法はありますか?

編集：

問題はスケジュールの問題です。24 時間のうちの 1 時間に予定を組む必要がある人は 100 万人いるため、2,400 万の決定変数があります。人 $i$ を時間 $j$ にスケジュールすると、$R_{ij}$ の報酬があります。制約は、各人が数時間にスケジュールされる必要があることですが、各時間には限られた数の予約スロットしかありません $c$

4

2 に答える 2

3

膨大な数の変数と制約を持つ LP/IP にアプローチする 1 つの良い方法は、論理的な方法で決定変数をグループ化する方法を探すことです。問題の概要を示しただけなので、解決策のアイデアを次に示します。

アプローチ 1 : 人々を小さなバッチにグループ化する

100 万人ではなく、1 万人単位の 100 ユニットと考えてください。したがって、2400 (24 x 100) の変数しかありません。これは、そこへの道のりの一部になります。これは最適な解決策ではなく、適切な近似であることに注意してください。もちろん、1000 人のバッチを 1000 作成して、よりきめ細かいソリューションを得ることができます。あなたはアイデアを得る。

アプローチ 2: コストに基づくコホートへのグループ化

R_ij を見てください。おそらく、百万の異なるコストはありません。通常、一意のコスト値はわずかしかありません。アイデアは、同じコスト構造を持つ多くの人々を 1 つの「コホート」にグループ化することです。これで、どのコホートがどの時間に入るかという、はるかに小さな問題を解決できます。

繰り返しになりますが、いったんアイデアが得られれば、非常に扱いやすいものにすることができます。

OPのコメントに基づく更新：その性質上、これらのグループを作成することは近似手法です。最適解が得られる保証はありません。ただし、（同一または非常に類似したコスト構造を持つコホートを調べることによる）慎重なグループ化の全体的な考え方は、はるかに少ない計算労力で、可能な限り最適に近いソリューションを取得することです。

  • また、スケーリングする場合 (グループ化は問題のサイズを縮小する 1 つの方法にすぎません)、他の定数もスケーリングする必要があることも追加する必要がありました。つまり、c_j も同じ単位 (10K) である必要があります。
  • 人 A、B、C がタイム スロット j に収まらない場合、モデルは、コストが最も低いタイム スロットにできるだけ多くの人を絞り込み、残りをコストがわずかに高い他のスロットに移動します。対応可能です。

正しい方向に進むのに役立つことを願っています。

于 2013-04-24T16:24:50.793 に答える
2

重複する人がたくさんいると仮定すると、あまりにも多くの変数を使用していることになります。

1000 種類の人しかいないと仮定して、2000 回発生する人もいれば、500 回発生する人もいるとします。

次に、各時間に割り当てる人数の割合を最適化する必要があります。(定数として 2000 または 500 を追加して、目的関数と制約を少し調整する必要があることに注意してください)

良いニュースは、これにより「少数の」変数で最適なソリューションが得られるはずですが、問題によっては、結果として全員を取得するために結果を丸める必要がある場合があります。

于 2013-04-24T16:36:04.697 に答える