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

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

 dc.creator Blanco Izquierdo, Víctor es dc.creator Fernández Aréizaga, Elena es dc.creator Puerto Albandoz, Justo es dc.date.accessioned 2017-06-22T08:02:35Z dc.date.available 2017-06-22T08:02:35Z dc.date.issued 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.identifier.uri http://hdl.handle.net/11441/61450 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 http://creativecommons.org/licenses/by-nc-nd/4.0/ * 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 http://ac.els-cdn.com/S0377221717303569/1-s2.0-S0377221717303569-main.pdf?_tid=39e19780-571e-11e7-a8dc-00000aacb360&acdnat=1498117479_857be2b947ca88f8fc7938de9b973341 es dc.identifier.doi 10.1016/j.ejor.2017.04.023 es dc.contributor.group 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