FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home

Minimum weight spanning tree

Description
Six terminals located in different buildings need to be connected. The cost of connecting two terminals is proportional to the distance between them. Determine the connections to install to minimize the total cost.

Further explanation of this example: 'Applications of optimization with Xpress-MP', Section 12.4 'Construction of a cabled network' (g4cable.mos)

Source Files
By clicking on a file name, a preview is opened at the bottom of this page.

Data Files

spanningtree_graph.mos

(!******************************************************
Mosel Example Problems
======================

file spanningtree.mos

TYPE:         Minimum weight spanning tree problem
DIFFICULTY:   3
FEATURES:     MIP problem, formulation of constraints to exclude subcycles,
graphical representation of results
DESCRIPTION:  Six terminals located in different buildings need to be
connected. The cost of connecting two terminals is
proportional to the distance between them. Determine the
connections to install to minimize the total cost.
FURTHER INFO: Applications of optimization with Xpress-MP',
Section 12.4 Construction of a cabled network'

(c) 2008 Fair Isaac Corporation
author: S. Heipcke, 2002, rev. Sep. 2017
*******************************************************!)

model "Cabled network"
uses "mmxprs", "mmsvg","mmsystem"

declarations
NTERM = 6
TERMINALS = 1..NTERM                  ! Set of terminals to cnct

DIST: array(TERMINALS,TERMINALS) of integer  ! Distance between terminals

cnct: array(TERMINALS,TERMINALS) of mpvar ! 1 if direct connection
! between terminals, 0 otherwise
level: array(TERMINALS) of mpvar      ! level value of nodes
end-declarations

initializations from 'spanningtree.dat'
DIST
end-initializations

! Objective: length of cable used
Length:= sum(s,t in TERMINALS | s<>t) DIST(s,t)*cnct(s,t)

! Number of cnctions
NumConnect:= sum(s,t in TERMINALS | s<>t) cnct(s,t) = NTERM - 1

! Avoid subcycle
forall(s,t in TERMINALS | s<>t)
Cycle(s,t):= level(t) >= level(s) + 1 - NTERM + NTERM*cnct(s,t)

! Direct all cnctions towards the root (node 1)
forall(s in 2..NTERM) Direct(s):= sum(t in TERMINALS | s<>t) cnct(s,t) = 1

forall(s,t in TERMINALS | s<>t) cnct(s,t) is_binary

! Solve the problem
minimize(Length)

! Solution printing
writeln("Cable length: ", getobjval)

write("Connections:")
forall(s,t in TERMINALS | s<>t)
write(if(getsol(cnct(s,t))>0, " " + s + "-" + t, ""))
writeln

! Solution drawing
declarations
X,Y: array(TERMINALS) of integer       ! x-y-coordinates of terminals
end-declarations

initializations from 'spanningtree.dat'
[X,Y] as 'POS'
end-initializations

minx:=min(t in TERMINALS)X(t)-5; miny:=min(t in TERMINALS)Y(t)-5
svgsetgraphviewbox(minx, miny,
max(t in TERMINALS)X(t)+5-minx,max(t in TERMINALS)Y(t)+5-miny)

forall(t in TERMINALS) do
end-do

forall(s,t in TERMINALS | s<>t)
if(getsol(cnct(s,t))>0) then
`