Minimum Spanning Trees with neighborhoods: Mathematical programming formulations and solution methods

摘要

Highlights ? Minimum Spanning Trees with second order cone-representable neighborhoods and lengths are studied. ? Two Mixed Integer Nonlinear models are presented. ? A decomposition approach is proposed which is embedded within an branch-and-cut scheme. ? An alternate convex search heuristic is developed, by using a biconvex representation. ? The results of our computational experiments are reported.