Repositorio de producción científica de la Universidad de Sevilla

Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods


Advanced Search

Show simple item record

dc.creator Blanco Izquierdo, Víctor es
dc.creator Fernández Aréizaga, Elena es
dc.creator Puerto Albandoz, Justo es 2017-06-22T08:02:35Z 2017-06-22T08:02:35Z 2017-11-01
dc.identifier.citation Blanco Izquierdo, V., Fernández Areizaga, E. y Puerto Albandoz, J. (2017). Minimum Spanning Trees with neighborhoods: Mathematical programming formulations and solution methods. European Journal of Operational Research, 262 (3), 863-878.
dc.identifier.issn 0377-2217 es
dc.description.abstract This paper studies Minimum Spanning Trees under incomplete information for its vertices. We assume that no information is available on the precise placement of vertices so that it is only known that vertices belong to some neighborhoods that are second order cone representable and distances are measured with a ℓq-norm. Two mixed integer non linear mathematical programming formulations are presented, based on alternative representations of subtour elimination constraints. A solution scheme is also proposed, 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. es
dc.description.sponsorship Ministerio de Economía y Competitividad es
dc.format application/pdf es
dc.language.iso eng es
dc.publisher Elsevier es
dc.relation.ispartof European Journal of Operational Research, 262 (3), 863-878.
dc.rights Attribution-NonCommercial-NoDerivatives 4.0 Internacional *
dc.rights.uri *
dc.subject Minimum spanning trees es
dc.subject Neighborhoods es
dc.subject Mixed integer non linear programming es
dc.subject Second order cone programming es
dc.title Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods es
dc.type info:eu-repo/semantics/article es
dc.type.version info:eu-repo/semantics/submittedVersion es
dc.rights.accessrights info:eu-repo/semantics/openAccess es
dc.contributor.affiliation Universidad de Sevilla. Departamento de Estadística e Investigación Operativa es
dc.relation.projectID info:eu-repo/grantAgreement/MINECO/MTM2016-74983-C2-1-R es
dc.relation.projectID info:eu-repo/grantAgreement/MINECO/MTM2015-63779-R es
dc.relation.publisherversion es
dc.identifier.doi 10.1016/j.ejor.2017.04.023 es Universidad de Sevilla. FQM331: Métodos y Modelos de la Estadística y la Investigación Operativa es
idus.format.extent 26 p. es
dc.journaltitle European Journal of Operational Research es
dc.publication.volumen 262 es
dc.publication.issue 3 es
dc.publication.initialPage 863 es
dc.publication.endPage 878 es
dc.contributor.funder Ministerio de Economía y Competitividad (MINECO). España
Size: 307.4Kb
Format: PDF

This item appears in the following Collection(s)

Show simple item record