| EPSRC Reference: |
GR/M90641/01 |
| Title: |
PROBLEM REFORMULATION AND SEARCH |
| Principal Investigator: |
Prosser, Dr P |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| 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: |
|
| EPSRC Industrial Sector Classifications: |
|
| 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 |