The University of Essex Skip to main content  School of Computer Science and Electronic Engineering
Prospective Students | Research | Department | Intranet | Search | Site Map | Home

 

Research Group

Constraint Satisfaction and Optimization + Computational Finance Group

Non-technical Description

Constraint satisfaction and optimization are behind many applications in airline operations; e.g. British Airways uses ECLiPSe (IC-Parc) for scheduling aircraft to serve their flights and ILOG Solver for aircraft stand allocation at airportsConstraint satisfaction and optimization are fundamental issues in computer science. Many real life problems, such as scheduling, logistics, timetabling and resource allocation, are constraint satisfaction and optimization problems. As its name suggests, constraint satisfaction involves satisfying constraints of various types. For example, in transportation, one may be asked to deliver goods to a large number of customers satisfying their time constraints and the capacity constraints of the vehicles available at different depots. Optimization has a much longer history in Operations Research. It involves finding the "best solution" among all possible solutions, where "best" is defined by some appropriate criteria. For example, in the transportation problem, this may mean minimizing the total travelling distance of all vehicles. Despite the rapid growth in computer processing power in the last couple of decades, many real life problems are computationally demanding by nature and are still beyond the capability of computers in present day technology. Researchers in constraint satisfaction and optimization aim to develop faster methods and solve more complex problems. 

Applications

Constraint programming is a multi-million pound business. Amongst the market leader are ILOG (an international company based in France) and ECLiPse (from IC-Parc, Imperial College, UK). Users of their services include Siemens, Bull, Renault (France), British Airways, Port of Singapore, Hong Kong Container Terminals, etc. Constraint satisfaction and optimization are also core technologies in transportation optimisation and supply chain management. For example, the method known as “Guided Local Search” (which was developed in our group) has been used in ILOG Dispatcher, a commercial product for solving vehicle routing problems.

Technical Overview

Finding the minimum value when there are two variables (as shown) is usually relatively simple. In many real life problems, there can be thousands of variables. Finding the minimum (say, cost) is, even today, sometimes beyond the fastest computers and the best methods, but the boundaries are constantly being pushed back.Formally, a constraint satisfaction problem involves a set of variables and a set of constraints of arbitrary type. Each variable may draw its value from a predefined (normally finite) domain. The problem is to assign a value to each variable satisfying the constraints. An optimization problem normally involves the assignment of values to variables, maximizing or minimizing a given function. Some of the techniques employed in constraint satisfaction are complete search methods (such as lookahead search, dependency directed backtracking and learning methods), local search methods (such as hill climbing and heuristic search) and evolutionary computation. Optimization problems normally employ a wide range of techniques from numerical analysis, often exploiting the nature of the individual problem. Each technique has its own merits and limitations. Employing the right techniques for the right problem requires good knowledge of these techniques as well as the ability to model the problem in hand.

Constraint Satisfaction and Optimization + Computational Finance Research Projects

Guided Local Search (GLS):  

Constraint satisfaction is one of the core technologies in transportation optimization. For example Guided Local Search was used in ILOG Solver’s vehicle routing package, Dispatcher. It was also used for tackling BT’s work force scheduling problemGLS is a meta-heuristic search method that enhances the effectiveness and efficiency of local search methods. GLS has been applied to a wide range of problems such as vehicle routing and industrial scheduling.

Computer-aided Constraint Programming:

The focus of this research is in developing tools to help users to model problems as constraint satisfaction problems and apply established methods to solve them.

Estimation of Distributed Algorithms (EDA):

EDA is a class of methods based on evolutionary computation. It uses statistical analysis of samples of the solution space to guide the search.

Numerical Methods:

We are interested in a range of optimization methods (including the quasi-Newton methods) for continuous problems.

Dynamic Scheduling:

In some scheduling applications, the problem changes dynamically. The challenge is to adapt one's strategy in response to the changes.

Distributed Scheduling: 

We are interested in scheduling problems that involve multiple agents, each with its own objectives. We are interested in the evolution of strategies.

EDDIE, a financial forecasting tool, uses a constraint-based optimization function to satisfy the user's risk preferenceComputational Finance:

Constraints are related to computational finance, another branch of research at the University (http://cswww.essex.ac.uk/CSP/finance).

Funding

Government Funding: EPSRC (UK)
Industrial Funding: British Telecom, HSBC (UK)

Group Members:

Edward Tsang

Professor Edward Tsang
(coordinator for 
Constraint Satisfaction)

Dr John Ford  
(coordinator for 
Numerical Computation)

Dr Qingfu Zhang 
(coordinator for 
EDA Project)

Dr Patrick Mills
Research Assistant

Mr Jianyung Sun
Research Assistant

Mr Mathias Kern 
PhD student 
(funded by EPSRC and BT)

Mr Tim Gosling
PhD student 
(funded by EPSRC and BT)

Ms Nanlin Jin
PhD Student

Mr Hassan Rashidi
PhD Student

 

Affiliate Members:

Dr Abdel Salhi (Mathematics Department)
Dr Sheri Markose (Economics Department)
Mr Serafin Martines-Jaramillo, PhD student (Institute For Studies In Finance)

For more information:

Professor Edward Tsang
Department of Computer Science, University of Essex, Colchester CO4 3SQ UK
Tel: +44 1206 872774
Fax: +44 1206 872788
Email: edward@essex.ac.uk
URLs: http://cswww.essex.ac.uk/CSP and http://cswww.essex.ac.uk/Research/NA

[top of page]

 

Prospective Students | Research | Department | Intranet | Search | Site Map | Home