ITC-2007 Track2: An Approach using General CSP Solver
光紀 熱田, Koji Nonobe, Toshihide Ibaraki · 2007
Description of the method Our approach is to formulate the given timetabling instances as instances of constraint satisfaction problem (CSP), and then apply a general purpose CSP solver to find their solutions. To validate this approach, however, (1) a powerful CSP solver must be available, and (2) compact CSP formulations that can utilize all the power of such solver must be devised. As the general purpose CSP solver, we use the one proposed by [1]. This solver adopts hyblid algorithm of tabu search and iterated local search, and handles weighted constraints. By specifying initial weights, it can distinguish soft and hard constraints, but their weights are dynamically controlled during computation to improve performance. The solver used in this experiment is an improved version of [1] in the sense of added capability of handling quadratic 0-1 constraints. The CSP formulation of Track 2 instances was basically done by using linear 0-1 inequalities, quadratic 0-1 inequalities, and all-different constraints. In