A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem

• DOI: 10.1287/opre.43.1.130
• Publication Date: 2008-11-08T13:45:52Z
• Authors: Luis Gouveia
• Keywords: Cutting-plane method; Lagrangian relaxation; Linear programming relaxation; Tree (set theory); Branch and cut

In this paper we present a new formulation for the Capacitated Minimal Spanning Tree (CMST) problem. One advantage of is that it more compact (in number constraints) than well-known formulation. Additionally, show linear programming relaxation both formulations produces optimal solutions with same cost. We brief discussion concerning valid inequalities which are directly derived from some not dominated by sets facet-inducing (CMST). derive Lagrangian relaxation-based methods and computational evidence showing reasonable improvements on original bounds can be obtained if these strengthened use cutting planes. The reported results indicate one presented in dominates, most cases, previous best literature. significant instances root corner.