An exact dynamic programming based method to solve optimisation problems using GPUs

O'Connell, Jonathan F. and Mumford, Christine Lesley ORCID: https://orcid.org/0000-0002-4514-0272 2014. An exact dynamic programming based method to solve optimisation problems using GPUs. Presented at: 2014 Second International Symposium on Computing and Networking (CANDAR), Shizuoka, Japan, 10-12 Dec 2014. Computing and Networking (CANDAR), 2014 Second International Symposium on. IEEE, pp. 347-353. 10.1109/CANDAR.2014.27

Preview

PDF - Accepted Post-Print Version Download (155kB) | Preview

Abstract

In this paper we present a dynamic programming based technique that is suitable for providing exact solutions to a subset of optimisation problems, using general purpose GPU computing. The primary feature of this model is to efficiently use the computational and memory resources of the GPU, whilst still remaining abstract enough to allow implementation on a variety of problems. Secondly, as exact dynamic programming methods are often limited by memory complexity, great consideration has been given to reducing this constraint, allowing large scale problems to be solved. To demonstrate the effectiveness of the proposed model we test it against three problems, the 0-1 knapsack problem, the longest common subsequence problem, and the travelling salesman problem.

Item Type:	Conference or Workshop Item (Paper)
Date Type:	Publication
Status:	Published
Schools:	Computer Science & Informatics
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Publisher:	IEEE
Date of First Compliant Deposit:	30 March 2016
Last Modified:	28 Oct 2022 08:39
URI:	https://orca.cardiff.ac.uk/id/eprint/71639

Citation Data

Cited 3 times in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item