Friday, 11:00 - 11:25 h, Room: MA 041

 

Francois Margot
The traveling salesman problem with neighborhoods: MINLP solution

Coauthors: Iacopo Gentilini, Kenji Shimada

 

Abstract:
The traveling salesman problem with neighborhoods extends the traveling salesman problem to the case where each vertex of the tour is allowed to move in a given region. This NP-hard optimization problem
has recently received increasing attention in several technical fields such as robotics, unmanned aerial vehicles, or utility management. We formulate the problem as a nonconvex Mixed-Integer
NonLinear Program (MINLP) having the property that fixing all the integer variables to any integer values yields a convex nonlinear program. This property is used to modify the global MINLP optimizer Couenne, improving by orders of magnitude its performance and allowing the exact solution of instances large enough to be useful in applications. Computational results are presented where neighborhoods are either polyhedra or ellipsoids in R2 or R3 and with the Euclidean norm as distance metric.

 

Talk 2 of the invited session Fri.1.MA 041
"Applications of MINLP I" [...]
Cluster 14
"Mixed-integer nonlinear programming" [...]

 

  The system of instant Virginia Loans Online allows any adult U.S. citizen. Of course, the choice is not that easy, as there exist great number of different preparations. Notwithstanding, Buy Cialis Online is the one that definitely differs from all other products.