| |||||||||

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) 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 | |||||||||

Copyright 2017 Fair Isaac Corporation. |