Evaluation and Relaxation of Constraints in a Constraint Satisfaction Problem using Linear Programming

DOI Web Site
  • Kakimoto Yohei
    Department of Information and Management Systems Engineering, Nagaoka University of Technology
  • Takahashi Hirotaka
    Department of Information and Management Systems Engineering, Nagaoka University of Technology
  • Shimakawa Yoichi
    Department of Computer Science and Technology, Salesian Polytechnic

Bibliographic Information

Other Title
  • 制約充足問題を線形計画法で解く場合の制約条件の緩和とその評価
  • 制約充足問題を線形計画法で解く場合の制約条件の緩和とその評価 : 時間割編成を例に
  • セイヤク ジュウソク モンダイ オ センケイ ケイカクホウ デ トク バアイ ノ セイヤク ジョウケン ノ カンワ ト ソノ ヒョウカ : ジカンワリ ヘンセイ オ レイ ニ
  • —時間割編成を例に
  • - A case study of timetabling

Search this article

Abstract

In this paper, the effect of constraints is shown in the case of solving a constraint satisfaction problem (CSP) using linear programming (LP). A timetabling problem (TP) is formulated as example CSP. Then, the authors try to solve the problem using a simplex method in order to get the exact solution by selectively varying the constraints. Using the results obtained, how constraints affect the solutions obtained are examined. The computation time and simplex pivot count are observed, excepting the constraints that do not affect the feasible TP solutions. Certain kinds of constraints are shown to make the problem difficult. As the result, it is found that constraints, such as giving two successive classes and limiting the number of times giving the same classes in a day, is a major factor for making the problem complicated. In addition, a method for importing ambiguous constraints is proposed.

Journal

Keywords

Details 詳細情報について

Report a problem

Back to top