7

複雑な問題があり、巡回セールスマン問題のように、既存のよく理解されているソリューションモデルが存在するか適用されるかを知りたいです。

入力：

  • 開始時間と終了時間、および場所によって定義されるN回のイベントのカレンダー。
  • 各待ち合わせ場所の定員（同時に収容できる最大人数）
  • アテンダントがアテンダントと会うことを希望し、その招待を受け入れたこと(Ai,Aj)を示すペアのセット。AiAjAj

出力：

  • アシスタントごとAに、彼が参加するすべてのイベントのクロノグラム。主な基準は、各アテンダントが、スペースの制約を満たして、招待を受け入れたアテンダントのできるだけ多くを満たす必要があるということです。

これまで、バックトラッキングを使用して解く（可能なすべての解を試す）こと、および線形計画法を使用すること（つまり、モデルを定義してシンプレックスアルゴリズムを使用して解くこと）を考えてきました。

更新：Aiあるイベントですでに会った場合Aj、彼らはもう会う必要はありません（彼らはすでに会っています）。

4

3 に答える 3

3

あなたの問題は、区間グラフの最小最大マッチング問題と同じくらい難しいです、wlog部屋の容量は2、時間内に1つの会議しか処理できないことを意味すると仮定します。区間グラフを使用して問題をモデル化できます。各区間（各人）は1つのノードです。また、エッジは、A_iとA_jに共通の時間があり、お互いを見たい場合は、エッジの重みをお互いに見える時間に設定します。このグラフで最小の最大一致が見つかった場合は、制限されたケースの解決策を見つけることができます。ただし、このグラフはn分割であり、各部分も区間グラフであることに注意してください。

PS：人々がお互いにいるべき時間の長さが固定されている場合、これは加重されたものよりも簡単になることに注意してください。

于 2012-04-30T09:42:00.250 に答える
2

優れたMIPソルバー（acedamicイニシアチブを介したcplex / gurobiですが、coin ORとLP_solveはオープンソースであり、悪くはありません）にアクセスできる場合は、間違いなくシンプレックスを試してみます。私はあなたの問題を混合整数計画法として定式化することを検討しました、そしてそれはかなり強い緩和を持っていると私は感じています、それでブランチアンドカットと価格はあなたにとって大いに役立ちます。これらのソルバーは、今日、特に商用ソリューションで非常にスケーラブルなソリューションを提供します。利点は、上限も提供されるため、ヒューリスティックには当てはまらないソリューション品質のアイデアが得られることです。

処方：

z（i、j）（binary）を、iとjが{1,2、...、N}の少なくとも1つのイベントnに一緒にあることを示す変数として定義します。z（i、j、n）（バイナリ）を定義して、イベントnで一緒になっていることを示します。z（i、n）を定義して、iがnに参加していることを示します。Z（i、j）とz（i、j、m）は、iとjが出会うことになっている場合にのみ存在します。

各tについて、M^tは同時に開催されるタイムイベントのサブセットです。したがって、イベント1が9から11で、イベント2が10から12で、イベント3が11から13の場合、M ^ 1 = {イベント1、イベント2）およびM ^ 2 = {イベント2、イベント3} 。つまり、1と2、または2と3の両方に参加できる人はいませんが、1と3は問題ありません。

Max sum Z(i,j)                      

z(i,j)<= sum_m z(i,j,m)   
(every i,j)(i and j can meet if they are in the same location m at least once)

z(i,j,m)<= z(i,m)   (for every i,j,m) 
(if i and j attend m, then i attends m)

z(i,j,m)<= z(j,m)     (for every i,j,m) 
(if i and j attend m, then j attends m)

sum_i z(i,m) <= C(m)   (for every m) 
(only C(m) persons can visit event m)

sum_(m in M^t) z(i,m) <= 1  (for every t and i)  
(if m and m' are both overlapping time t, then no person can visit them both. )
于 2012-05-15T21:05:39.537 に答える
1

@SaeedAmiriが指摘しているように、これは複雑な問題のように見えます。

私の推測では、あなたが検討しているバックトラッキングと線形計画法のオプションは、アシスタントの数が少し増えるとすぐに爆発するでしょう（おそらく数十のアシスタントのオーダー）。

最適性が要件でない場合は、（メタ）ヒューリスティックアプローチを検討するか、初期モデルを構築してそれがどのようにスケーリングするかを確認するための制約プログラミングを検討する必要があります。

より正確な答えを出すために、なぜこの問題を解決する必要があるのですか？典型的な参加者数はいくつですか？室数？

于 2012-04-30T10:54:01.397 に答える