FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

Minimum cost flow

Description
A company needs to transport 180 tonnes of chemical products stored in four depots to three recycling centers. The depots contain 190 tonnes in total. Each depot only delivers to certain centers, by road and/or by rail, at a given cost per tonne. Transports by rail need to have at least 10 tonnes and at most 50 tonnes for any single delivery. How should the company transport the 180 tonnes of chemicals to minimize the total cost of transport?

Further explanation of this example: 'Applications of optimization with Xpress-MP', Section 10.2 'Choosing the mode of transport'. Similar problems: Section 6.4 'Cane sugar production', Section 6.5 'Opencast mining'

mincostflowgr.zip[download all files]

Source Files

Data Files





mincostflow_graph.mos

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

   file mincostflow.mos
   ````````````````````
   TYPE:         Minimum cost flow problem
   DIFFICULTY:   2
   FEATURES:     MIP problem, formulation with extra nodes for modes of
                 transport; encoding of arcs, `finalize', union of sets, 
                 nodes labeled with strings, graphical solution representation
   DESCRIPTION:  A company needs to transport 180 tonnes of chemical products 
                 stored in four depots to three recycling centers. The depots 
                 contain 190 tonnes in total. Each depot only delivers to 
                 certain centers, by road and/or by rail, at a given cost 
                 per tonne. Transports by rail need to have at least 10 tonnes 
                 and at most 50 tonnes for any single delivery. 
                 How should the company transport the 180 tonnes of chemicals 
                 to minimize the total cost of transport?     
   FURTHER INFO: `Applications of optimization with Xpress-MP', 
                 Section 10.2 `Choosing the mode of transport'.
                 Similar problems:
                 Section 6.4 `Cane sugar production',
                 Section 6.5 `Opencast mining'
   
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, 2002, rev. Sep. 2017
*******************************************************!)

model "Minimum cost flow"
 uses "mmxprs", "mmsvg"

 declarations
  NODES: set of string                  ! Set of nodes
  MINQ : integer                        ! Total quantity to transport
  A: array(ARCS:range,1..2) of string   ! Arcs
  COST: array(ARCS) of integer          ! Transport cost on arcs
  MINCAP,MAXCAP: array(ARCS) of integer ! Minimum and maximum arc capacities
 end-declarations

 initializations from 'mincostflow.dat'
  A MINQ MINCAP MAXCAP COST
 end-initializations

 finalize(ARCS)

! Calculate the set of nodes
 NODES:=union(a in ARCS) {A(a,1),A(a,2)}

 declarations
  flow: array(ARCS) of mpvar            ! Flow on arcs
 end-declarations

! Objective: total transport cost
 Cost:= sum(a in ARCS) COST(a)*flow(a)

! Flow balance: inflow equals outflow
 forall(n in NODES | n<>"SOURCE" and n<>"SINK")
  Balance(n):=
   sum(a in ARCS | A(a,2)=n) flow(a) = sum(a in ARCS | A(a,1)=n) flow(a)
   
! Min and max flow capacities
 forall(a in ARCS | MAXCAP(a) > 0) do
  flow(a) >= MINCAP(a)
  flow(a) <= MAXCAP(a)
 end-do
  
! Minimum total quantity to transport
 MinQuant:= sum(a in ARCS | A(a,1)="SOURCE" ) flow(a) >= MINQ

! Solve the problem
 minimize(Cost)
 
! Solution printing
 writeln("Total cost: ", getobjval)
 forall(a in ARCS)
  write( if(getsol(flow(a))>0, 
         A(a,1) + " -> "+ A(a,2) + ": "+ getsol(flow(a))+"\n", ""))

! Solution drawing
 declarations
  X,Y: array(NODES) of integer        ! x-y-coordinates of nodes
 end-declarations
 
 initializations from 'mincostflow.dat'
  [X,Y] as 'POS'
 end-initializations

 svgsetgraphviewbox(0,10,max(n in NODES)X(n)+15, max(n in NODES)Y(n)+15)
 svgsetgraphscale(2)

 svgaddgroup("Arcs", "Network")
 forall(n in NODES) do
  svgaddpoint(X(n), Y(n))
  svgaddtext(X(n), if(Y(n)>60, Y(n)+2, Y(n)-5), n)
 end-do

 svgaddgroup("Flow", "Used routes")
 forall(a in ARCS)
  if(getsol(flow(a))>0) then
   svgaddarrow(X(A(a,1)), Y(A(a,1)), X(A(a,2)), Y(A(a,2)))
   svgaddtext((X(A(a,1))+X(A(a,2)))/2, (Y(A(a,1))+Y(A(a,2)))/2-3, 
                text(getsol(flow(a))))
  else
   svgaddline("Arcs", X(A(a,1)), Y(A(a,1)), X(A(a,2)), Y(A(a,2)))
  end-if

 svgsave("mincostflow.svg")
 svgrefresh
 svgwaitclose("Close browser window to terminate model execution.", 1)
end-model

Back to examples browserPrevious exampleNext example