\$title Cplex Benders for a Simple Facility Location Problem (CBENDERS,SEQ=415) \$onText A simple version of a facility location problem is used to show how the Benders decompostion works with Cplex 12.7. The model includes a small example and can be started with a double dash parameter --wmax to set an arbitrary number of warehouses. The remaining set and data items will be computed from this wmax. There are three ways of running Cplex' Benders driving by the BendersStrategy parameters. The lower the BendersStrategy number the more information needs to be provided by the user. Note that the problem can also be solved as an RMIP but since Benders does not provide dual information, the Cplex log will have a few lines that look like errors but can be safely ignored. A company is considering opening as many as four warehouses in order to serve nine different regions. The goal is to minimize the sum of fixed costs associated with opening warehouses as well as the various transportation costs incurred to ship goods from the warehouses to the regions. Whether or not to open a warehouse is represented by binary variable ow. Whether or not to ship goods from warehouse i to region j is represented by binary variable oa. Each region needs a specified amount of goods, and each warehouse can store only a limited quantity of goods. In addition, each region must be served by exactly one warehouse. Keywords: mixed integer linear programming, Benders decomposition, facility location problem \$offText \$ifThen not set wmax Set i 'warehouses' / w1*w4 / j 'regions' / r1*r9 / k 'goods' / k1*k3 /; Parameter f(i) 'fixed costs' / w1 130, w2 150, w3 170, w4 180 / c(i) 'capacity' / w1 90, w2 110, w3 130, w4 150 / d(j) 'demand' / r1 10, r2 10, r3 12, r4 15, r5 15 r6 15, r7 20, r8 20, r9 30 /; Table t(j,i) 'transport costs' w1 w2 w3 w4 r1 10 30 25 55 r2 10 25 25 45 r3 20 23 30 40 r4 25 10 26 40 r5 28 12 20 29 r6 36 19 16 22 r7 40 39 22 27 r8 75 65 55 35 r9 34 43 41 62; \$else * Generate large random examples \$ eval rmax %wmax%*5 \$ eval kmax round(%wmax%/3) Set i 'warehouses' / w1*w%wmax% / j 'regions' / r1*r%rmax% / k 'goods' / k1*k%kmax% /; Parameter f(i) 'fixed costs' c(i) 'capacity' d(j) 'demand' t(j,i) 'transport cost'; f(i) = uniformInt(100,200); c(i) = uniformInt(200,300); d(j) = uniformInt(20,60); t(j,i) = uniformInt(5,100); \$endIf Parameter ck(i,k), dk(j,k); ck(i,k) = round(c(i)*uniform(0.5,1.8)); dk(j,k) = round(d(j)*uniform(0.5,1.8)); Variable totcost 'total cost' fcost 'fixed cost' tcost(k) 'transportation cost' ow(i) 'indicator for open warehouse' oa(i,j) 'indicator for open shipment arc warehouse to region' x(i,j,k) 'shipment of good k for open shipment arc warehouse to region'; Binary Variable ow, oa; Positive Variable x; Equation deftotcost 'definition total cost' deffcost 'definition fixed cost' deftcost(k) 'definition transportation cost' defwcap(i,k) 'limit utilization of warehouse by its capacity' defwdem(j,k) 'demand satisfaction in region j for good k' twow(j) 'only two warehouses per region' defow(i,j) 'warehouse open if shipment from i to j' defx(i,j,k) 'shipment only if link open bteween i to j'; deftotcost.. totcost =e= fcost + sum(k, tcost(k)); deffcost.. fcost =e= sum(i, f(i)*ow(i)); deftcost(k).. tcost(k) =e= sum((i,j), t(j,i)*x(i,j,k)); defwcap(i,k).. sum(j, x(i,j,k)) =l= ck(i,k); defwdem(j,k).. sum(i, x(i,j,k)) =g= dk(j,k); twow(j).. sum(i, oa(i,j)) =l= 2; defow(i,j).. ow(i) =g= oa(i,j); defx(i,j,k).. ck(i,k)*oa(i,j) =g= x(i,j,k); Model loc / all /; File fopt / cplexd.opt /; put fopt 'BendersStrategy 1' / 'variables.BendersPartition 0'; loop(k, put / "x.BendersPartition(*,*,'" k.tl:0 "') " ord(k):0:0 / "tcost.BendersPartition('" k.tl:0 "') " ord(k):0:0; ); putClose fopt; \$onEcho > cplexd.op2 BendersStrategy 2 variables.BendersPartition 0 x.BendersPartition 1 tcost.BendersPartition 1 \$offEcho \$onEcho > cplexd.op3 BendersStrategy 3 \$offEcho \$onEcho > cplexd.op4 BendersPartitionInStage 1 BendersStrategy 1 \$offEcho totcost.stage = 0; fcost.stage = 1; tcost.stage(k) = ord(k) + 1; x.stage(i,j,k) = ord(k) + 1; option solver = cplexd, optCr = 0, limRow = 0, limCol = 0, solPrint = off, solveLink = %solveLink.loadLibrary%; Scalar cpxOptFile; for(cpxOptFile = 1 to 4, loc.optFile = cpxOptFile; solve loc minimizing totcost using mip; abort\$(loc.modelStat <> %modelStat.optimal%) 'expect model status optimal'; abort\$(abs(totcost.l - 11661) > 1e-6) 'expect objective to be 11661'; ); * solve again with SCIP, if not AIX or Solaris, while passing on decomposition info \$if %system.buildcode% == AIX \$exit \$if %system.buildcode% == SOX \$exit option solver = scip; loc.optfile = 0; * starting with the optimal solution is too easy x.l(i,j,k) = 0; solve loc minimizing totcost using mip; abort\$(loc.modelStat <> %modelStat.optimal%) 'expect model status optimal'; abort\$(abs(totcost.l - 11661) > 1e-6) 'expect objective to be 11661';