Solving the Traveling Thief Problem using Orchestration in Optimization Networks
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, Spain, 2017, pp. 307-315
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.