平成１０年度３月　ＲＡＭＰの案内

• 日時：3月6日（土） 14:00 〜 17:00
• 場所：上智大学10号館3階322号室

• 発表１：堀田敬介氏 (筑波大学経営工学専攻）

  『単調線形相補性問題に対するCHK関数を用いたSmoothing法について』
  

  相補性問題を解く算法として, 近年盛んに研究されているものの 一つに Smoothing法というものがあります. 相補性問題とは, 等式条件・非負条件・相補性条件を満たす点の 組を見つける問題であり, ここで扱う Smoothing法は, 非負条件と 相補性条件を CHK(Chen-Harker-Kanzow)関数の等式条件に置き換え て表現し, 先の等式条件と合わせてニュートン・ラプソン法で解く というものです. その理論的考察と数値実験結果について報告します.

• 発表２：梶谷洋司氏（東京工業大学電気・電子工学科）

  『配置の数理：多数の長方形を最小面積に埋め込む』
  

  ２次元パッキング問題，すなわち，多数の長方形を平面上に，相互の重なりがなく， それら全部を囲む矩形面積ができるだけ小さくなるように配置する問題について，新 解法とその実用性について説明する． 規模が爆発するVLSIチップ設計では，パッキングは基本問題であり，どうしても解か ねばならない．長い努力にもかかわらず未だ実質的には手作業であり，納得の行く自 動解法は提案されていなかった． ここでは，解法を思いつくことが困難である理由の解析から始め，新しい方法の必然 性を抽象し，それに応える二通りの方法を提案し，それによって最小面積配置を数え 挙げることができることを述べる．両方法は，それぞれBSGおよびSequence-Pairと呼 ぶデータ構造によって実現される． シミュレーテッドアニーリングによる実装実験によれば数万個でも十分な品質で配置 でき実用上限界は無くなった．一般矩形，配線面積考慮，ソフト図形の配置，あるい は既配置図形，変形パッケージの扱い，更には３次元配置への発展，などの研究状況 を紹介する。この方式の本質は，四方位が一意である仮想平面の構築の成功とそこに は最適解が含まれる，という幸運にある．