Travelling Salesperson Optimization Version

Problem description

This problem modifies its corresponding decision problem by minimizing the sum of weights of edges in a Hamiltonian cycle. For a given undirected graph G = (V,E), the objective function to minimize is as follows:

sum { w_{i,j} * cycle(i,j) : {i,j} in E }

Except for the objective function to minimize, the problem description is the same as the one of the corresponding decision problem.

Input format

See corresponding decision problem

Output format

See corresponding decision problem

Author: Lengning Liu, Miroslaw Truszczynski, and Martin Gebser
Affiliation: University of Kentucky and University of Potsdam