平成12年度1月 最適化とアルゴリズム研究部会
- 日時:1月20日(土) 14:00 〜 17:30
- 場所:上智大学7号館12階第1215号室
- 発表1:汪 寿陽 氏 (中国科学院, 筑波大学社会工学系)
- 『Bilevel Programming: Theory, Algorithms and Issues to Be Studied』
-
In this talk, the basic theory and some numerical methods of bilevel programming are introduced, including various models and the corresponding solution concepts, optimality conditions, duality theorems, properties of optimal solutions and algorithms. Some successful applications will be also surveyed, but will not be discussed in details.
A few issues and problems will be given concerning development of bilevel programming. Some of them might be attracting topics for further investigations.
- 発表2:永持 仁氏 (豊橋科学技術大学 情報工学系)
- 『無向グラフの辺連結度に対するラミナ構造とその応用』
-
1990年にフローアルゴリズムを用いない無向グラフの最小カット
を求める方法が永持・茨木により提案されて以来、その最小カットアルゴリズムで
使われる最大隣接順序(MAO)の他の問題への応用が研究されている。
MAOにより効率よく解ける問題として辺連結度増大問題が知られている。
この問題は、グラフに最小本数の枝を付加して辺連結度を目標値kに
増加させる問題である。この問題をMAOで解決する過程で、
カット値がkに満たない点集合の族でラミナとなるものが計算されるが、
本講演では、このラミナ構造の計算法とその応用について紹介する。
最近、要求量kの供給点配置問題がMAOを使って効率よく解くことが
できることが分かり、この事実は、先のラミナ構造の存在から容易に理解できる。
ただし、要求量kの供給点配置問題とはグラフから最小の節点集合Sを選び、
残りの点からSへの辺連結度をk以上にする問題である。
また、MAOがグラフの辺集合に対して作る森への分解を用いれば、
すべての目標値kに対する辺連結度増大問題の
最適解を得られること知られているが、このアルゴリズム
からすべての目標値に対するラミナ構造が生成出来ることを示す。
これにより、これまでと同じ計算量ですべての要求量kに対する供給点配置問題
を解くことができる。
SOA Home Page へ.