The Unexpected Virtue of Problem Reductions or How to Solve Problems Being Lazy but Wise
- Publisher:
- IEEE
- Publication Type:
- Conference Proceeding
- Citation:
- 2020 IEEE Symposium Series on Computational Intelligence (SSCI), 2021, 00, pp. 2381-2390
- Issue Date:
- 2021-01-05
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
| The_Unexpected_Virtue_of_Problem_Reductions_or_How_to_Solve_Problems_Being_Lazy_but_Wise.pdf | Published version | 244.33 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
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.
Please use this identifier to cite or link to this item: