A bilevel programming approach to the travelling salesman problem

A bilevel programming approach to the travelling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor20043363
Country: Netherlands
Volume: 32
Issue: 3
Start Page Number: 240
End Page Number: 248
Publication Date: May 2004
Journal: Operations Research Letters
Authors: , ,
Abstract:

We show that the travelling salesman problem is polynomially reducible to a bilevel toll optimization program. Based on natural bilevel programming techniques, we recover the lifted Miller–Tucker–Zemlin constraints. Next, we derive an O(n2) multi-commodity extension whose LP relaxation is comparable to the exponential formulation of Dantzig, Fulkerson and Johnson.

Reviews

Required fields are marked *. Your email address will not be published.