Solving the Simple Offset Assignment Problem as a Traveling Salesman

J√ľnger, Michael and Mallach, Sven (2013) Solving the Simple Offset Assignment Problem as a Traveling Salesman.
Published In: M-SCOPES '13: Proceedings of the 16th International Workshop on Software and Compilers for Embedded Systems ACM 2013, pp. 31-39.


In this paper, we present an exact approach to the Simple Offset Assignment problem arising in the domain of address code generation for digital signal processors. It is based on transformations to weighted Hamiltonian cycle problems and integer linear programming. To the best of our knowledge, it is the first approach capable to solve all instances of the established OffsetStone benchmark set to optimality within reasonable time. Therefore, it enables to evaluate the quality of several heuristics relative to the optimum solutions for the first time. Further, using the same transformations, we present a simple and effective improvement heuristic. In addition, we include an existing heuristic into our experiments that has so far not been evaluated with OffsetStone.

Download: [img] PDF
Download (204kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
Depositing User: Sven Mallach
Date Deposited: 29 May 2013 07:33
Last Modified: 02 Sep 2013 11:07