Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Solves the Multicommodity Flow Problem for Concurrent Flow with GNU MathProg.
# Multicommodity Flow Problem for Directed Networks,
## Optimized for Concurrent Flow
set V; # Vertex Set
set E, within V cross V; # Edge Set
set K; # Commodity Set
param s {K}, symbolic in V; # Source Vertex of Commodity
param t {K}, symbolic in V; # Sink Vertex of Commodity
param d {K}, >= 0; # Demand of Commodity
param c, >= 0; # Capacity of Edge
var f {K,E}, >= 0; # Flow of Commodity on Edge
var dstar {K}, >= 0; # Throughput of Commidty
# Conservation Constraint.
## This is basically Kirchhoff's Current
## Law in a nutshell. The exception is that
## the source nodes should generate throughput,
## while the sink nodes should receive the same
## throughput.
s.t. conserve_ct { k in K, v in V } :
( sum { w in V : (w,v) in E } f[k,w,v] ) -
( sum { w in V : (v,w) in E } f[k,v,w] ) =
if ( v!=s[k] and v!=t[k] ) then 0
else if ( v=s[k] ) then -dstar[k]
else if ( v=t[k] ) then dstar[k];
# Demand Constraint.
## This constraint ensures the demand is
## always either met or exceeded.
s.t. demand_ct { k in K } :
d[k] <= dstar[k];
# Flow Constraint.
## This constraint is necessary to prevent
## flow over an arc from exceeding the throughput.
s.t. flow_ct { k in K, (w,v) in E } :
f[k,w,v] <= dstar[k];
# Capacity Constraint.
## The total flow over an arc should
## be less than or equal to the arc's
## capacity.
s.t. capacity_ct { (v,w) in E } :
( sum { k in K } f[k,v,w] ) <= c;
# Optimization Objective.
## The objective is to maximize the smallest throughput
## to demand ration.
var z, >= 0;
s.t. conc_ct { k in K } :
dstar[k] / d[k] - z >= 0;
maximize obj : z;
data;
# As an example, let's define a ring
## network topology as a directed graph.
set V := A B C;
set E :=
A B
B C
C A;
# Capacity of each edge.
param c := 10;
# Finally, let's define
## the commodities.
param : K : s t d :=
k0 A C 0.5
k1 B A 0.5;
@esdrasa
Copy link

esdrasa commented Nov 14, 2018

Nice Work, man!

Loading

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment