×

Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods. (English) Zbl 1375.90295

Summary: This paper studies minimum spanning trees under incomplete information assuming that it is only known that vertices belong to some neighborhoods that are second order cone representable and distances are measured with a \(\ell_q\)-norm. Two mixed integer non linear mathematical programming formulations are presented based on alternative representations of subtour elimination constraints. Also proposed is a solution scheme resulting from a reformulation suitable for a Benders-like decomposition, which is embedded within an exact branch-and-cut framework. Furthermore, a mathheuristic is developed, which alternates in solving convex subproblems in different solution spaces and is able to solve larger instances. The results of extensive computational experiments are reported and analyzed.

MSC:

90C35 Programming involving graphs or networks
90C11 Mixed integer programming
90C20 Quadratic programming

Software:

Gurobi
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Arkin, E. M.; Hassin, R., Approximation algorithms for the geometric covering salesman problem, Discrete Applied Mathematics, 55, 197-218 (1994) · Zbl 0819.90115
[2] Arkin, E. M.; Hassin, R., Minimum diameter covering problems, Networks, 36, 147-155 (2000) · Zbl 0973.05075
[3] Benders, J. F., Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik, 4, 3, 238-252 (1962) · Zbl 0109.38302
[4] Bertsimas, D.; Howell, L. H., Further results on the probabilistic traveling salesman problem, European Journal of Operational Research, 65, 1, 68-95 (1993) · Zbl 0776.90082
[5] Blanco, V.; Puerto, J.; El-Haj Ben-Ali, S., Revisiting several problems and algorithms in continuous location with \(l_τ\) norms, Computational Optimization and Applications, 58, 3, 563-595 (2014) · Zbl 1297.90073
[6] Brimberg, J.; Wesolowsky, G. O., Locating facilities by minimax relative to closest points of demand areas, Computers & Operations Research, 29, 6, 625-636 (2002) · Zbl 1001.90042
[7] Cooper, J., Bounds on the weber problem solution under conditions of uncertainty, Journal of Regional Science, 18, 1, 87-92 (1978)
[8] Disser, Y.; Mihalák, M.; Montanari, S.; Widmayer, P., Rectilinear shortest path and rectilinear minimum spanning tree with neighborhoods, Proceedings of the third international symposium on combinatorial optimization (ISCO), 208-220 (2014) · Zbl 1445.68158
[9] Dorrigiv, R.; Fraser, R.; He, M.; Kamali, S.; Kawamura, A.; López-Ortiz, A.; Seco, D., On minimum-and maximum-weight minimum spanning trees with neighborhoods, Proceedings of the tenth international workshop on approximation and online algorithms (WAOA), 93-106 (2013) · Zbl 1394.68415
[10] Dror, M.; Efrat, A.; Lubiw, A.; Mitchell, J. S.B., Touring a sequence of polygons, Proceedings of the thirty-fifth symposium on theory of computing, 473-482 (2003), ACM Press · Zbl 1192.68354
[11] Dufour, S. W., Intersections of random convex regions (1973), Department of Statistics, Standford University
[12] Edmonds, J., Submodular functions, matroids, and certain polyhedra, Proceedings of the calgary international conference on combinatorial structures and their applications, 69-87 (1970) · Zbl 0268.05019
[13] Fernández, E.; Pozo, M. A.; Puerto, J.; Scozzari, A., Ordered weighted average optimization in multiobjective spanning tree problems, European Journal of Operational Research, 17, 1, 886-903 (2016) · Zbl 1403.90637
[14] Fischetti, M.; Ljubic, I.; Sinnl, M., Benders decomposition without separability: A computational study for capacitated facility location problems, European Journal of Operational Research, 253, 557-569 (2016) · Zbl 1346.90490
[15] Fischetti, M.; Ljubic, I.; Sinnl, M., Redesigning benders decomposition for large scale facility location, Management Science (2016)
[16] Frank, H., Shortest paths in probabilistic graphs, Operations Research, 17, 4, 583-599 (1969) · Zbl 0176.48301
[17] Gentilini, I.; Margot, F.; Shimada, K., The travelling salesman problem with neighborhoods: MINLP solution, Optimization Methods and Software, 28, 2, 364-378 (2013) · Zbl 1270.90055
[18] Geoffrion, A. M., Generalized benders decomposition, Journal of Optimization Theory and Applications, 10, 4, 237-260 (1972) · Zbl 0229.90024
[19] Gorski, J.; Pfeuffer, F.; Klamroth, K., Biconvex sets and optimization with biconvex functions: A survey and extensions, Mathematical Methods of Operations Research, 66, 3, 373-407 (2007) · Zbl 1146.90495
[21] Juel, H., Bounds in the generalized weber problem under locational uncertainty, Operations Research, 29, 6, 1219-1227 (1981) · Zbl 0474.90035
[22] Landete, M.; Marín, A., Looking for edge-equitable spanning trees, Computers & Operations Research, 41, 44-52 (2014) · Zbl 1348.90600
[23] Lobo, M.; Vandenberghe, L.; Boyd, S.; Lebret, H., Applications of second-order cone programming, Linear Algebra and its Applications, 284, 193-228 (1998) · Zbl 0946.90050
[24] Löffler, M.; van Kreveld, M., Largest and smallest convex hulls for imprecise points, Algorithmica, 56, 235-269 (2010) · Zbl 1185.65036
[25] Martin, R., Using separation algorithms to generate mixed integer model reformulations, Operations Research Letters, 10, 3, 119-128 (1991) · Zbl 0747.90071
[26] McCormick, G. P., Computability of global solutions to factorable nonconvex programs: Part I. Convex underestimating problems, Mathematical Programming, 10, 147-175 (1976) · Zbl 0349.90100
[27] Miller, C. E.; Tucker, A. W.; Zemlin, R. A., Integer programming formulation of traveling salesman problems, Journal of the ACM, 7, 4, 326-329 (1960) · Zbl 0100.15101
[28] Nickel, S.; Puerto, J.; Rodríguez-Chía, A. M., An approach to location models involving sets as existing facilities, Mathematics of Operations Research, 28, 4, 693-715 (2003) · Zbl 1082.90059
[29] Shioura, A.; Tamura, A.; Uno, T., An optimal algorithm for scanning all spanning trees of undirected graphs, SIAM Journal on Computing, 26, 678-692 (1997) · Zbl 0870.05066
[31] Sörensen, K.; Janssens, G. K., An algorithm to generate all spanning trees of a graph in order of increasing cost, Pesquisa Operacional, 25, 2, 219-229 (2005)
[32] Wendell, R. E.; Hurter, A. P., Minimization of a non-separable objective function subject to disjoint constraints, Operations Research, 24, 4, 643-657 (1976) · Zbl 0347.90044
[33] Yang, Y.; Lin, M.; Xu, J.; Xie, Y., Minimum spanning tree with neighborhoods, Proceedings of the third international conference on algorithmic aspects in information and management (AAIM 2007), 306-316 (2007) · Zbl 1137.68615
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.