DocumentCode :
1867599
Title :
Quadratic TSP: A lower bounding procedure and a column generation approach
Author :
Rostami, Borzou ; Malucelli, Francesco ; Belotti, Pietro ; Gualandi, Stefano
Author_Institution :
Dipt. di Elettron., Inf. e Bioingegneria, Politec. di Milano, Milan, Italy
fYear :
2013
fDate :
8-11 Sept. 2013
Firstpage :
377
Lastpage :
384
Abstract :
In this paper we present a Column Generation approach to the Quadratic Traveling Salesman Problem. Given a graph and a function that maps every pair of edges to a cost, the problem consists in finding a cycle that visits every vertex exactly once and such that the sum of the costs over all pairs of consecutive edges of the cycle is minimum. We propose a Linear Programming formulation that has a variable for each cycle in the graph. Since the number of cycles is exponential in the graph size, we solve our formulation via column generation. Computational results on some set of instances used in the literature show that our approach is promising. As it obtains a lower bound close to the optimal solutions for all instances.
Keywords :
graph theory; linear programming; quadratic programming; travelling salesman problems; column generation approach; graph edge; graph size; graph vertex; linear programming formulation; lower bounding procedure; optimal solution; quadratic TSP; quadratic traveling salesman problem; Color; Cost function; Linear programming; Mathematical model; Pricing; Silicon; Traveling salesman problems;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Science and Information Systems (FedCSIS), 2013 Federated Conference on
Conference_Location :
Krako??w
Type :
conf
Filename :
6644028
Link To Document :
بازگشت