An efficient mixed integer linear programming model for the minimum spanning tree problem
Summary: Finding a minimum spanning tree in a given network is a famous combinatorial optimization problem that appears in different engineering applications. Even though this problem is solvable in polynomial time, having efficient mathematical programming models is important as they can provide insights for formulating larger models that integrate other decisions in more complex applications. In the literature, there are ten different integer and mixed integer linear programming (MILP) models for this problem. They are variants of set packing, cuts, network flow and node level formulations. In addition, this paper introduces an efficient node level MILP model. Comparisons for the eleven models are provided. First, the models are compared in terms of the number of decision variables and the number of constraints. Then, computational comparisons using a commercial MILP solver on sets of randomly generated instances of different sizes are conducted. Results provide evidence that the proposed MILP model is competitive in terms of the computational time needed for proving optimality of generated solutions for instances with up to 50 nodes. Meanwhile, the LP relaxation of a multi-commodity flow MILP model which has integer polyhedron provides stable computational times despite its larger size.
- A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs
- A new relaxation method for the generalized minimum spanning tree problem
- A mixed integer linear formulation for the minimum label spanning tree problem
- New models of the generalized minimum spanning tree problem
- Solving the minimum label spanning tree problem by mathematical programming techniques
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- scientific article; zbMATH DE number 2132174 (Why is no real title available?)
- scientific article; zbMATH DE number 1312984 (Why is no real title available?)
- scientific article; zbMATH DE number 718142 (Why is no real title available?)
- scientific article; zbMATH DE number 795222 (Why is no real title available?)
- Integer Programming Formulation of Traveling Salesman Problems
- On the shortest spanning subtree of a graph and the traveling salesman problem
- The Traveling-Salesman Problem and Minimum Spanning Trees
- Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods
- Compact mixed integer linear programming models to the minimum weighted tree reconstruction problem
- Improved approaches to solve the one-to-one skewgram problem
- A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs
- Integer programming formulations for minimum spanning forests and connected components in sparse graphs
- scientific article; zbMATH DE number 4173002 (Why is no real title available?)
- A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”
- Collective combinatorial optimisation as judgment aggregation
- Solving the minimum label spanning tree problem by mathematical programming techniques
- Constraint programming approaches for finding conserved metabolic and genomic patterns
- Designing compact, connected and gap-free reserves with systematic reserve site selection models
This page was built for publication: An efficient mixed integer linear programming model for the minimum spanning tree problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6162004)
