Mathematics and Statistics Vol. 8(6), pp. 728 - 739
DOI: 10.13189/ms.2020.080614
Reprint (PDF) (682Kb)

Algorithmic Verification of Constraint Satisfaction Method on Timetable Problem

Viliam Ďuriš ^*
Department of Mathematics, Constantine the Philosopher University in Nitra, Tr. A. Hlinku 1, 94974 Nitra, Slovakia

ABSTRACT

Various problems in the real world can be viewed as the Constraint Satisfaction Problem (CSP) based on several mathematical principles. This paper is a guideline for complete automation of the Timetable Problem (TTP) formulated as CSP, which we are able to solve algorithmically, and so the advantage is the possibility to solve the problem on a computer. The theory presents fundamental concepts and characteristics of CSP along with an overview of basic algorithms used in terms of its solution and forms the TTP as CSP and delineates the basic properties and requirements to be met in the timetable. The theory in our paper is mostly based on the Jeavons, Cohen, Gyssens, Cooper, and Koubarakis work, on the basis of which we've constructed a computer programme, which verifies the validity and functionality of the Constraint satisfaction method for solving the Timetable Problem. The solution of the TTP, which is characterized by its basic characteristics and requirements, was implemented by a tree-based search algorithm to a program and our main contribution is an algorithmic verification of constraints abilities and reliability when solving a TTP by means of constraints. The created program was also used to verify the time complexity of the algorithmic solution.

KEYWORDS
NP-complete Problem, Timetable Problem, Computational Complexity, Decision Problem, Constraint Satisfaction, Constraint Satisfaction Problem, Algorithms for CSP, School Timetabling, Optimization, Backtracking, Relational Algebra

Cite This Paper in IEEE or APA Citation Styles
(a). IEEE Format:
[1] Viliam Ďuriš , "Algorithmic Verification of Constraint Satisfaction Method on Timetable Problem," Mathematics and Statistics, Vol. 8, No. 6, pp. 728 - 739, 2020. DOI: 10.13189/ms.2020.080614.

(b). APA Format:
Viliam Ďuriš (2020). Algorithmic Verification of Constraint Satisfaction Method on Timetable Problem. Mathematics and Statistics, 8(6), 728 - 739. DOI: 10.13189/ms.2020.080614.