Optimization Online


Lagrangian and Branch-and-Cut Approaches for Upgrading Spanning Tree Problems

Eduardo Alvarez-Miranda(ealvarez***at***utalca.cl)
Markus Sinnl(markus.sinnl***at***univie.ac.at)

Abstract: Problems aiming at finding budget constrained optimal upgrading schemes to improve network performance have received attention over the last two decades. In their general setting, these problems consist of designing a network and, simultaneously, allocating (limited) upgrading resources in order to enhance the performance of the designed network. In this paper we address two particular optimal upgrading network design problems; in both cases, the sought layout corresponds to a spanning tree of the input network and upgrading decisions can be taken on nodes. We design Mixed Integer Programming-based algorithmic schemes to solve the considered problems: Lagrangian relaxation approaches and branch-and-cut algorithms. Along with the designed algorithms, different enhancements, including valid inequalities, primal heuristic and variable fixing procedures, are proposed. Using two set of instances, we experimentally compare the designed algorithms and explore the benefits of the devised enhancements. The results show that the proposed approaches are effective for solving to optimality most of the instances in the testbed, or manage to obtain solutions and bounds giving very small optimality gaps. Besides, the proposed enhancements turn out to be beneficial for improving the performance of the algorithms.

Keywords: Spanning Tree Problems; Integer Programming; Lagrangian Relaxation; Telecommunications

Category 1: Network Optimization

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Applications -- OR and Management Sciences (Telecommunications )

Citation: Department of Industrial Engineering, Universidad de Talca, Curico, Chile Department of Statistics and Operations Research, Faculty of Business, Economics and Statistics, University of Vienna, Vienna, Austria

Download: [PDF]

Entry Submitted: 04/02/2016
Entry Accepted: 05/01/2016
Entry Last Modified: 04/02/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society