EPSRC logo

Details of Grant 

EPSRC Reference: GR/M90641/01
Title: PROBLEM REFORMULATION AND SEARCH
Principal Investigator: Prosser, Dr P
Other Investigators:
Gent, Professor IP Smith, Dr B
Researcher Co-Investigators:
Project Partners:
Ilog SA (Bracknell)
Department: School of Computing Science
Organisation: University of Glasgow
Scheme: Standard Research (Pre-FEC)
Starts: 31 August 2000 Ends: 29 September 2003 Value (£): 159,097
EPSRC Research Topic Classifications:
Artificial Intelligence
EPSRC Industrial Sector Classifications:
Information Technologies
Related Grants:
Panel History:  
Summary on Grant Application Form
When we change the representation of a problem, this can influence the behaviour of an algorithm and its heuristic. In particular, in constraint programming a good formulation will give strong propagation resulting in significant reductions in search effort. Similarly, a formulation that allows us to express features of the domain may allow us to better exploit heuristics.Given a problem, when we go from one formulation to another we might find that this suggests a change of algorithm and heuristic. These reformulation may be subtle (eg an interchange between variables and values), austere (eg formulation as propositional satisfiability), or across domains (eg viewing a single resource scheduling problem with setups as travelling salesman problem).We will investigate problem reformulation, and how this influences search, for three real-world problem: Car Sequencing (CSP), Vehicle Routing (VRP) and Job Shop Scheduling (JSSP). We will derive theory based heuristics for the CSP and investigate empirically search behaviour as we reformulate as VRP, and then solved with VRP technology. We will investigate reformulation between these two domains.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Summary
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.gla.ac.uk