{{ message }}

Instantly share code, notes, and snippets.

# andrewandrepowell/gmpl_mcfp_cl.mod

Last active Nov 14, 2018
Solves the Multicommodity Flow Problem for Concurrent Flow with GNU MathProg.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 # 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;

Nice Work, man!