# ---------------------------------------- # LOCATION-TRANSPORTATION PROBLEM # USING BENDERS DECOMPOSITION # (using dual formulation of subproblem) # ---------------------------------------- ### SUBPROBLEM FOR EXTREME POINT ### 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 param BIG := 1.0e+9; # objective > BIG ==> unbounded var Supply_Price {ORIG} <= 0; var Demand_Price {DEST}; maximize Dual_Ship_Cost: sum {i in ORIG} Supply_Price[i] * supply[i] * build[i] + sum {j in DEST} Demand_Price[j] * demand[j]; subj to Unbounded_Check: sum {i in ORIG} Supply_Price[i] * supply[i] * build[i] + sum {j in DEST} Demand_Price[j] * demand[j] <= BIG; subj to Dual_Ship {i in ORIG, j in DEST}: Supply_Price[i] + Demand_Price[j] <= var_cost[i,j]; ### SUBPROBLEM FOR EXTREME RAY ### maximize Dummy: 0; subj to Unbounded_Direction: sum {i in ORIG} Supply_Price[i] * supply[i] * build[i] + sum {j in DEST} Demand_Price[j] * demand[j] = 1; subj to Feasible_Direction {i in ORIG, j in DEST}: Supply_Price[i] + Demand_Price[j] <= 0; ### 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; 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];