> How can I solve a Minimum Spanning Tree problem with GAMS?
It is possible to implement an algorithm in GAMS (Prim, Kruskal, see model library model mst.gms). It is also possible to formulate a MIP. There are several formulations (see Magnanti, Wolsey, “Optimal Trees”, in Network Models, volume 7, Handbooks of Operations Research, 1995). If the graph is planar, there is a formulation described in Justin C. Williams, “A linear-size zero - one programming model for the minimum spanning tree problem in planar graphs”, Networks, 39(1), 2002.
Here is one of the flow formulations mst.gms.
As the MIP is automatically integer (total unimodularity) we can solve as an RMIP. This is a big LP however: for a 42 city problem with all edges i → j allowed, I get:
BLOCKS OF EQUATIONS 3 SINGLE EQUATIONS 72,325
BLOCKS OF VARIABLES 3 SINGLE VARIABLES 72,325
NON ZERO ELEMENTS 284,131 DISCRETE VARIABLES 72,324
PS: I believe the model mst.gms from the model library is incorrect. The assignment mst(a,u,ip)$(dmin eq darc(a,u)) = ord(s); should be changed so that if multiple arcs (a,u) have length dmin, only one is chosen. A corrected version for the above instance is mst2.gms. The fix was needed for this data set: without it a suboptimal tree was returned: obj=662 instead of obj=591 (as demonstrated by msterr.gms). This is another good reason to implement this as an LP: to debug algorithms.