# ---------------------------------------- # LOCATION-TRANSPORTATION PROBLEM # USING BENDERS DECOMPOSITION # (using primal formulation of subproblem) # ---------------------------------------- ### SUBPROBLEM ### set ORIG; # shipment origins (warehouses) set DEST; # shipment destinations (stores) param supply {ORIG} > 0; param demand {DEST} > 0; param fix_cost {ORIG} > 0; param var_cost {ORIG,DEST} > 0; param build {ORIG} binary; # = 1 iff warehouse built at i var Ship {ORIG,DEST} >= 0; # amounts shipped minimize Ship_Cost: sum {i in ORIG, j in DEST} var_cost[i,j] * Ship[i,j]; subj to Supply {i in ORIG}: sum {j in DEST} Ship[i,j] <= supply[i] * build[i]; subj to Demand {j in DEST}: sum {i in ORIG} Ship[i,j] = demand[j]; ### MASTER PROBLEM ### param nCUT >= 0 integer; param cut_type {1..nCUT} symbolic within {"point","ray"}; param supply_price {ORIG,1..nCUT} <= 0.000001; param demand_price {DEST,1..nCUT}; var Build {ORIG} binary; # = 1 iff warehouse built at i var Max_Ship_Cost >= 0; minimize Total_Cost: sum {i in ORIG} fix_cost[i] * Build[i] + Max_Ship_Cost; subj to Cut_Defn {k in 1..nCUT}: if cut_type[k] = "point" then Max_Ship_Cost >= sum {i in ORIG} supply_price[i,k] * supply[i] * Build[i] + sum {j in DEST} demand_price[j,k] * demand[j];