Publikation

Solving the Traveling Thief Problem using Orchestration in Optimization Networks

Outline:

J. Karder, A. Beham, S. Wagner, M. Affenzeller - Solving the Traveling Thief Problem using Orchestration in Optimization Networks - Lecture Notes in Computer Science 10671, Las Palmas de Gran Canaria, Spanien, 2017, pp. 307-315

Abstract:

Optimization problems can sometimes be divided into multiple subproblems. Working on these subproblems instead of the actual master problem can have some advantages, e.g. if they are standard problems, it is possible to use already existing algorithms, whereas specialized algorithms would have to be implemented for the master problem. In this paper we approach the NP-hard Traveling Thief Problem by implementing dierent cooperative approaches using optimization networks. Orchestration is used to guide the algorithms that solve the respective subproblems. We conduct experiments on some instances of a larger benchmark set to compare the dierent network approaches to best known results, as well as a sophisticated, monolithic approach. Using optimization networks, we are able to nd new best solutions for all of the selected problem instances.