Please use this identifier to cite or link to this item:
https://hdl.handle.net/10316/44347
Title: | Dynamic programming for spanning tree problems: application to the multi-objective case | Authors: | Di Puglia Pugliese, Luigi Guerriero, Francesca Santos, José Luis |
Keywords: | Dynamic programming, Spanning tree problems, Multiple objective programming, Pareto front | Issue Date: | 2015 | Publisher: | Springer Berlin Heidelberg | Serial title, monograph or event: | Optimization Letters | Volume: | 9 | Issue: | 3 | Abstract: | The aim of this paper is to provide a dynamic programming formulation for the spanning tree problem (ST P), which allows several instances of the classical ST P to be addressed. The spanning tree structure is modelled with states and transition between states, defining a state-space. Several properties are shown and optimality conditions are given. Once the theoretical fundamentals of the proposed formulation are derived, the multi-objective spanning tree problem (MOST P) is addressed. This problem arises in the telecommunications and transportation sectors. In these contexts, handling different criteria simultaneously plays a crucial role. The scientific literature provides several works that focus on the bi-objective version of the considered problem, in which only two criteria are taken into account. To the best of our knowledge, no works provide optimal methods to address theMOST P with an arbitrary number l of objective functions. In this paper we extend the proposed dynamic programming formulation to model and solve the MOST P with l ≥ 3 criteria. | URI: | https://hdl.handle.net/10316/44347 | ISSN: | 1862-4472 (Print) 1862-4480 (Online) | DOI: | 10.1007/s11590-014-0759-1 10.1007/s11590-014-0759-1 |
Rights: | embargoedAccess |
Appears in Collections: | I&D CMUC - Artigos em Revistas Internacionais |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
MOSTP-DP_revisto.pdf | 396.58 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.