Constraint Satisfaction and Optimization + Computational Finance Group
Non-technical DescriptionConstraint 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.
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.
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
GLS 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.
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.
EDA is a class of methods based on evolutionary computation. It uses statistical analysis of samples of the solution space to guide the search.
We are interested in a range of optimization methods (including the quasi-Newton methods) for continuous problems.
In some scheduling applications, the problem changes dynamically. The challenge is to adapt one's strategy in response to the changes.
We are interested in scheduling problems that involve multiple agents, each with its own objectives. We are interested in the evolution of strategies.
Constraints are related to computational finance, another branch of research at the University (http://cswww.essex.ac.uk/CSP/finance).
For more information:
Professor Edward Tsang
|Monday, 25 October 2004|