Constraint Satisfaction and Optimization Research Projects

The GENET Project
GENET is a connectionist approach to constraint satisfaction. It is a stochastic search method. It has been shown to be both efficient and effective in binary constraint satisfaction problems, graph colouring and car sequencing (which is a non-binary problem).

The Guided Local Search (GLS) Project
Guided Local Search (GLS) is an extension of GENET which takes optimization into consideration. It has been shown efficient and effective in a number of problems, including traditional optimization problems such as the Travelling Salesman Problem and pseudo real-life problems such as the Radio Length Frequency Assignment Problem and British Telecom's Workforce Scheduling Problem.

The Guided Genetic Algorithm (GGA) Project
Guided Genetic Algorithm (GLS) is an extension of GLS. It is a hybrid between GLS and GA. The aim is to improve the robustness of GLS and to extend its domain of application. It has been shown efficient and effective in a number of problems, including the Royal Road Function, the Processors configuration problem, the frequency assignment problem and the general assignment problem.

The Constraints Modelling Project
A system for modelling was developed in the CACP Project.
A model of a constraint satisfaction problem is defined by the variables, domains and contraints selected. Given a model specificaiton, the choice of model is crucial to the solving of a constraint satisfaction problem. This project looks at heuristics to evaluate models and modify it in order to help solving constraint satisfaction problem.

The Adaptive Constraint Satisfaction (ACS) Project
This project is built upon the philosophy of finding appropriate algorithms for a given constraint satisfaction (as opposed to applying a "champion algorithm" to all problems). Mechanisms are being developed to monitor the performance of algorithms and adaptive strategies are being developed to dynamically switches algorithms when the current algorithm is concluded failing.

The Computer-Aided Constraint-Programming (CACP) Project
This is a completed project which aims to bring constraint technology to non-expert users. The software engineering and human-computer interaction aspects of constraint satisfaction and constraint optimization will be investigated. Practical aspects of the constraint technology will be advanced. A computer-aided constraint-programming system will be designed and implemented.

The Autoport Project
This research concerns itself with the scheduling of Autonomous Guided Vehicles (AGVs) in a port. Port components that are relevant to our problem include berths, quay cranes, container storage areas, and a road network. Given a number of AGVs and their availability, the task is to schedule the AGVs to meet the transportation requirements. We have extended classical Network Simplex Method for (a) efficiency, and (b) dynamic problems. We have also developed a heuristic search algorithm for this problem.

The EDA Project
Population-based algorithms using estimation of distribution, often called estimation of distribution algorithms (EDAs), have been recognized as a major paradigm in evolutionary computation. This project will work towards establishing a sound theory for characterizing and explaining EDA-like algorithms. We shall use continuous optimization problems and quadratic assignment problems as our test problems.

The Flexible Workforce Management Project
This project is in collaboration with BT. Although it is motivated by BT's workforce scheduling problem, the ideas developed in this project are general. It involved scheduling engineers to jobs, satisfying a wide range of constraints. This is a multi-objective optimization problem. Some of the objectives are to minimize travelling distance and to maximize service quality as defined by the company. Staff empowerment is also a major theme in this project.

Constraint Satisfaction Home Logo Constraint Satisfaction Home Page

Bracil Home Image Map Bracil Home Page CIDER Theory Bracil CSP Home Page Bracil Finance Home Page Edward Tsang Home Page