Rostering with constraint programming and heuristic

Abstract

Constraint Satisfaction Problem (CSP) is one of the active branches in Artificial Intelligence (AI) research. Many real world problems can be modeled as CSP naturally from business to engineering domains. Efficient techniques for solving CSPs have been widely studied in the last two decades, which is called Constraint Programming (CP). In general, CP can be divided into two main approaches, complete systematic search and incomplete local search. This thesis focuses on the first one, which is usually referred as systematic tree search incorporate with constraint consistency techniques. Search space can be efficiently reduced by repeatedly invoking constraint consistency check without affecting the original solution space. In addition, variable and value ordering heuristics are also important in tree search. A suitable heuristic can guide the search process direct to the first solution effectively. We first propose two enhancements in existing variable and value ordering heuristics, which are called MWO/FFP hybrid and Relaxed FFP. Former focuses on solving problems which large variance in degree of node, and latter focus on some evenly constrained problems. Classical problems – map coloring and N-Queen problem are used to test our approaches. Experiment results shown that our approach outperforms existing techniques. Many real world problems, such as rostering problem have been solved by CP. Nurse Rostering Problem (NRP) is one of the intensively studied applications in CSP. Unfortunately, most of these problems are NP-complete, conventional generic techniques are usually not able to solve this kind of problem within a reasonable time limit. Focusing on Nurse Rostering Problem (NRP), we developed three CSP techniques for this particular problem. They are Meta-level Reasoning (MR), Probability-based Ordering heuristic (PO) and integration of these two approaches – MRPO. Meta-Level Reasoning is a preprocessing procedure, which analyzes constraint relationship and generates more useful constraints. With constraint analysis, we may also able to discover insolvable problem before searching. The idea of Probability-based Ordering heuristic is similar to Relaxed FFP. This heuristic approximate the probability of a label occur in solution set and select the highest probability label to instantiate. The approximation is done by scoring functions, which related to properties of different constraints. Experiments show both MR and PO alone improves the search speed significantly. Furthermore, with minor changes, these two approaches can be integrate together perfectly to form a hybrid algorithm – MRPO. Experiment results show that MRPO gains advantages from both MR and PO.

Date of Award	4 Oct 2004
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Hon Wai CHUN (Supervisor)