Minimum-Spaning-Tree-Gurobi

Minimum Spaning Tree Solutiın with/without constraints using Gurobi Library

Prerequisites:

• C++ complier
• C++ Gurobi Solver

In this repository you will find two different formulation of Minimum Spaning Tree solver. These two formulation are widely used by researchers and business people to solve MST problems.

Miller, Tucker and Zemlin Formulation

Filename: MSTP - Miller, Tucker Zemlin.cpp

For an example model file check out: MSTP - Miller, Tucker Zemlin.lp

Simply MTZ formulation first apear in 1960 and still a popular formulation to solve Travelling Salesman Problem (TSP) or Minimum Spanning Trees (MST). It uses an Integer Programming approach to solve models. For more information you may check out the paper they published (https://dl.acm.org/citation.cfm?id=321046) and also search for new papers with 'Miller-Tucker-Zemlin Formulation' keyword.

Gavish and Graves Formulation

Filename: MSTP - Gavish, Graves.cpp

For an example model file check out: MSTP - Gavish, Graves.lp

Gavish and Graves first published their paper on Integer Programming solution for TSP solution on 1978 you may check out the paper via (http://hdl.handle.net/1721.1/5363), with their different approach the formulation is still a hot topic for researchers.

In my coding files, you may find a vector based approach to read Integer Programming (IP) Models from multiple *.txt files and contruct Gurobi models and run Gurobi IP Solver, then get the results for each run.
One addition to formulation I use conflicting edges as constraints but not include all the constraints at once (because time complexity goes sky high).
My approach is:

• Step 1: Solve model without constraint
• Step 2: Check current solution has any conflicting edges
• Step 3.1: Add constraints for conflicting pairs into model
• Step 3.2: Run again and Go to Step 2
• Step 4: Print out the results