平成７年度第４回KSMAP

日時：  平成７年９月８日（金） 午後３〜５時

場所：  京都大学工学部８号館３階
        共同６講義室
        
プログラム：
◆３時より
  ［タイトル］
      アブダクション(仮説生成)の計算の複雑さについて
 
  ［発表者］
      トーマス・アイター教授
       (Institut for Information Systems, Database and 
        Expert Systems Group, Technical University of Vienna)

  ［概要］
      アブダクション(abduction)は, 1つの現象が生じたときその原因を見出す
      ことを目的とする非単調推論の重要な形態である. 例えば, 路面が濡れて
      いることが観測された場合,  雨が降ったという仮説は, (通常の状況下で
      は)1つの説明となるであろう. 適用対象が論理式で表現されている場合は, 
      これは論理ベースアブダクションと呼ばれる. 仮説的説明は, 通常, 集合
      の包含関係, 位数, 重みの極小性, または, 個々の仮説の優先順位の下で
      の極小性といった, 極小性の基準に基づいて多くの候補中から選ばれる. 

      ここでは, 命題論理におけるアブダクションの計算の複雑さについて紹介
      する. 具体的には, アブダクションの最も基本的な形態において, 対応す
      る決定問題は,  多項式時間階層の2番目のクラスにおいて完全であり, さ
      らに,  優先順位を取り入れることにより, 計算の複雑さは3番目のクラス
      に上がってしまう場合があることを示す. この結果は, アブダクションが
      演繹よりも難しいことを示唆している. 


◆４時より
  ［タイトル］
     「航空路のハブ・スポークモデルについて」

  ［発表者］
      佐々木 美裕 （奈良先端科学技術大学院大学 情報科学研究科）

  ［概要］
      航空路のハブ・スポークモデルでは, 中継点の役割を果たすハブ空港と
      よばれる施設を配置し, ハブ空港間はすべて直接接続される. 
      また, ハブ空港以外の空港はハブ空港を経由して他の空港と接続される. 
      与えられたn個のハブ空港候補の中から, 移動費用とハブ空港の建設費用の
      総和を最小にするp個のハブ空港を選択するp-hub配置問題について考える. 

      上記のようなハブ・スポークモデルに関する研究は, 1987年のO'Kellyの
      論文に始まる. 初期の研究で扱われたモデルは, 容量制約なし, 各空港は
      唯一のハブ空港に割り当てられるというシンプルなモデルであった. 
      最近では, 複数のハブへの割当を可能とするモデル, 複数のサービス・
      タイプ(直行便, 1-stop, 2-stop)を含むモデル, ハブに容量制約を付加した
      モデル等, さまざまな拡張モデルが提案されている. またこれらの問題に
      対して, ラグランジュ緩和問題を利用した下界値を用いた分枝限定法に
      よる厳密解法, ランダム・アルゴリズムやタブー・サーチなどを用いた
      近似解法が研究されている. 
       
      本発表では, 航空路のハブ・スポークモデルの概要について紹介したあと, 
      ハブ空港と航路の双方に容量制約があるモデルを考える.
      各ODペア(出発地と目的地のペア)で経由するハブの数は1または0(直行便)
      とし, ODペアごとの取りうる経路を1つに限定せずに, 経路選択に自由度を
      持たせる. このハブ・スポークモデルを混合0-1計画問題として定式化し, 
      Benders DecompositionおよびCross Decompositionの適用について考察する.