# ---------------------------------------- # MULTI-COMMODITY FLOW USING # DANTZIG-WOLFE DECOMPOSITION # ---------------------------------------- ### SUBPROBLEM ### set ORIG; # origins set DEST; # destinations set PROD; # products param supply {ORIG,PROD} >= 0; # amounts available at origins param demand {DEST,PROD} >= 0; # amounts required at destinations check {p in PROD}: sum {i in ORIG} supply[i,p] = sum {j in DEST} demand[j,p]; param price_convex; # dual price on convexity constr param price {ORIG,DEST} <= 0.000001; # dual price on shipment limit param cost {ORIG,DEST,PROD} >= 0; # shipment costs per unit var Trans {ORIG,DEST,PROD} >= 0; # units to be shipped minimize Artif_Reduced_Cost: sum {i in ORIG, j in DEST, p in PROD} (- price[i,j]) * Trans[i,j,p] - price_convex; minimize Reduced_Cost: sum {i in ORIG, j in DEST, p in PROD} (cost[i,j,p] - price[i,j]) * Trans[i,j,p] - price_convex; subject to Supply {i in ORIG, p in PROD}: sum {j in DEST} Trans[i,j,p] = supply[i,p]; subject to Demand {j in DEST, p in PROD}: sum {i in ORIG} Trans[i,j,p] = demand[j,p]; ### MASTER PROBLEM ### param limit {ORIG,DEST} >= 0; # max shipped on each link param nPROP integer >= 0; param prop_ship {ORIG,DEST,1..nPROP} >= -0.000001; param prop_cost {1..nPROP} >= 0; # For each proposal from the subproblem: # amount it ships over each link, and its cost var Weight {1..nPROP} >= 0; var Excess >= 0; minimize Artificial: Excess; minimize Total_Cost: sum {k in 1..nPROP} prop_cost[k] * Weight[k]; subject to Multi {i in ORIG, j in DEST}: sum {k in 1..nPROP} prop_ship[i,j,k] * Weight[k] - Excess <= limit[i,j]; subject to Convex: sum {k in 1..nPROP} Weight[k] = 1; ### PHASE III PROBLEM ### param opt_ship {ORIG,DEST} >= -0.000001; minimize Opt_Cost: sum {i in ORIG, j in DEST, p in PROD} cost[i,j,p] * Trans[i,j,p]; subject to Opt_Multi {i in ORIG, j in DEST}: sum {p in PROD} Trans[i,j,p] = opt_ship[i,j];