Evaluation and relaxation of constraints in a constraint satisfaction problem using linear programming - A case study of timetabling

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.