- Title
- The Unexpected Virtue of Problem Reductions or How to Solve Problems Being Lazy but Wise
- Creator
- Mathieson, Luke; Moscato, Pablo
- Relation
- 2020 IEEE Symposium Series on Computational Intelligence (IEEE SSCI 2020). Proceedings of the 2020 IEEE Symposium Series on Computational Intelligence (IEEE SSCI 2020) (Canberra, Australia 1-4 December, 2020) p. 2381-2390
- Relation
- ARC.DP200102364 http://purl.org/au-research/grants/arc/DP200102364
- Publisher Link
- http://dx.doi.org/10.1109/SSCI47803.2020.9308295
- Publisher
- Institute of Electrical and Electronics Engineers (IEEE)
- Resource Type
- conference paper
- Date
- 2020
- Description
- The generalization of one problem to another is a useful technique in theoretical computer science; reductions among problems are a well established mathematical approach to demonstrate the structural relationships between problems. However, most of the reductions used to obtain theoretical results are relatively coarse-grained and chosen for their amenability in supporting mathematical proof, and represent a selection amongst many possible reduction schemas. We propose reexamining reductions as a practical tool, since choosing one reduction scheme over another may be decisive in solving a given instance in practical settings. In this work, we examine the impact of several new reduction schema. A total of 100 experiments were conducted using challenging Hamiltonian Cycle Problem instances using Concorde, a well known and effective TSP solver, and example of a complete memetic algorithm (MA). Benefits of using MA are that it uses multi-parent recombination, local search and also provides an optimality guarantee through its implicit enumeration complete search. We show that the choice of reduction scheme can result in dramatic speed-ups in practice, suggesting that when using general solvers, it pays “to be wise” and to explore alternative representations of instances.
- Subject
- reductions; complete memetic algorithm; Hamiltonian Cycle; Concorde
- Identifier
- http://hdl.handle.net/1959.13/1439410
- Identifier
- uon:40915
- Identifier
- ISBN:9781728125473
- Language
- eng
- Reviewed
- Hits: 712
- Visitors: 710
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|