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

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'

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)

forall(n in NODES) do
end-do

forall(a in ARCS)
if(getsol(flow(a))>0) then