Mostrar el registro sencillo del ítem
Artículo
Two-phase strategies for the bi-objective minimum spanning tree problem
dc.creator | Amorosi, Lavinia | es |
dc.creator | Puerto Albandoz, Justo | es |
dc.date.accessioned | 2022-07-04T08:38:25Z | |
dc.date.available | 2022-07-04T08:38:25Z | |
dc.date.issued | 2022-01-12 | |
dc.identifier.citation | Amorosi, L. y Puerto Albandoz, J. (2022). Two-phase strategies for the bi-objective minimum spanning tree problem. International transactions in operational research, 29 (6), 3435-3463. | |
dc.identifier.issn | 0969-6016 | es |
dc.identifier.issn | 1475-3995 | es |
dc.identifier.uri | https://hdl.handle.net/11441/134943 | |
dc.description.abstract | This paper presents a new two-phase algorithm for the bi-objective minimum spanning tree (BMST) prob-lem. In the first phase, it computes the extreme supported efficient solutions resorting to both mathematicalprogramming and algorithmic approaches, while the second phase is devoted to obtaining the remaining ef-ficient solutions (non-extreme supported and non-supported). This latter phase is based on a new recursiveprocedure capable of generating all the spanning trees of a connected graph through edge interchanges basedon increasing evaluation of non-zero reduced costs of associated weighted linear programs. Such a procedureexploits a common property of a wider class of problems to which the minimum spanning tree (MST) prob-lem belongs, that is the spanning tree structure of its basic feasible solutions. Computational experimentsare conducted on different families of graphs and with different types of cost. These results show that thisnew two-phase algorithm is correct, very easy to implement and it allows one to extract conclusions on thedifficulty of finding the entire set of Pareto solutions of the BMST problem depending on the graph topologyand the possible correlation of the edge costs | es |
dc.format | application/pdf | es |
dc.format.extent | 29 p. | es |
dc.language.iso | eng | es |
dc.publisher | Wiley | es |
dc.relation.ispartof | International transactions in operational research, 29 (6), 3435-3463. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | multiple objective programming | es |
dc.subject | combinatorial optimisation | es |
dc.subject | minimum spanning tree | es |
dc.subject | two-phase methods | es |
dc.title | Two-phase strategies for the bi-objective minimum spanning tree problem | es |
dc.type | info:eu-repo/semantics/article | es |
dc.type.version | info:eu-repo/semantics/publishedVersion | 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.publisherversion | doi.org/10.1111/itor.13120 | es |
dc.identifier.doi | 10.1111/itor.13120 | es |
dc.contributor.group | Universidad de Sevilla. FQM331: Metodos y Modelos de la Estadistica y la Investigacion Operativa | es |
dc.journaltitle | International transactions in operational research | es |
dc.publication.volumen | 29 | es |
dc.publication.issue | 6 | es |
dc.publication.initialPage | 3435 | es |
dc.publication.endPage | 3463 | es |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Two‐phase strategies for the ... | 2.371Mb | [PDF] | Ver/ | |