制約充足問題を線形計画法で解く場合の制約条件の緩和とその評価

DOI Web Site

書誌事項

タイトル別名
  • Evaluation and Relaxation of Constraints in a Constraint Satisfaction Problem using Linear Programming
  • 制約充足問題を線形計画法で解く場合の制約条件の緩和とその評価 : 時間割編成を例に
  • セイヤク ジュウソク モンダイ オ センケイ ケイカクホウ デ トク バアイ ノ セイヤク ジョウケン ノ カンワ ト ソノ ヒョウカ : ジカンワリ ヘンセイ オ レイ ニ
  • —時間割編成を例に
  • - A case study of timetabling

この論文をさがす

抄録

本稿では，時間割編成問題を制約充足問題として定式化し，単体法を用いて厳密解を求める．その結果から制約がどのように解に影響を与えるのか検証する．具体的には時間割編成において除外しても実行可能な解に影響のない制約条件を除き，計算時間や単体法の反復回数を基準として問題を難しくしている可能性のある制約を見つけ出す．得られた結果から2時限連続で行う科目や1日に同じ科目を行える回数を制限する制約といった科目の配置に影響を与える制約が問題を実行不可能にしていることがわかった．そこで，問題が実行不可能となるような制約を導入するために，制約の違反を許しその違反の量を目的関数により最小化する方法を提案する．

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ