An Efficient Mixed Integer Linear Programming Model for the Minimum Spanning Tree Problem

Tamer F. Abdelmaguid
Additional contact information
Tamer F. Abdelmaguid: Department of Mechanical Engineering, School of Sciences and Engineering, American University in Cairo, AUC Avenue, P.O. Box 74, New Cairo 11835, Egypt

Mathematics, 2018, vol. 6, issue 10, 1-17

Abstract: 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.

Keywords: minimum spanning tree; combinatorial optimization; mathematical programming (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/6/10/183/pdf (application/pdf)
https://www.mdpi.com/2227-7390/6/10/183/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:6:y:2018:i:10:p:183-:d:172755

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().