pmedian.gms : P-Median problem

**Description**

The pmedian problem is defined as follows: given a set I={1...n} of locations and a transportation cost W between each pair of locations. Select a subset S of p location minimizing the sum of the distances between each location and the closest one in S. There are currently 40 data files from the OR-LIB <a href="http://people.brunel.ac.uk/~mastjjb/jeb/orlib/pmedinfo.html">http://people.brunel.ac.uk/~mastjjb/jeb/orlib/pmedinfo.html</a> These data files are the 40 test problems from Table 2 of J.E.Beasley "A note on solving large p-median problems" European Journal of Operational Research 21 (1985) 270-273. pmed15 1729 1734

**Reference**

- Beasley, J E, A note on solving large p-median problems . European Journal of Operational Research 21, 2 (1985), 270-273.

**Large Model of Type :** MINLP

**Category :** GAMS Model library

**Main file :** pmedian.gms **includes :** pmed15.inc

$Title P-Median problem (pmedian,SEQ=408) $ontext The pmedian problem is defined as follows: given a set I={1...n} of locations and a transportation cost W between each pair of locations. Select a subset S of p location minimizing the sum of the distances between each location and the closest one in S. There are currently 40 data files from the OR-LIB http://people.brunel.ac.uk/~mastjjb/jeb/orlib/pmedinfo.html These data files are the 40 test problems from Table 2 of J.E.Beasley "A note on solving large p-median problems" European Journal of Operational Research 21 (1985) 270-273. pmed15 1729 1734 J.E.Beasley "A note on solving large p-median problems" European Journal of Operational Research 21 (1985) 270-273. $offtext $if not set instance $set instance pmed15.inc $if not exist "%instance%" $abort File of instance does not exist $onechoV > pm.awk BEGIN { nr=0 } !/^#/ { if (nr==0) { n = $1; printf("set n /0*%d/; Scalar p /%d/;\n", n-1,$3); printf("Table w(n,n) distances\n$ondelim\nn"); for (i=0; i<n; i++) printf(",%d",i); } if (nr>0) printf("\n%d %s",nr-1,$0); nr++; } END { printf("\n$offdelim\n;") } $offecho $set fn %gams.scrdir%tlinst.%gams.scrext% $call awk -f pm.awk %instance% > "%fn%" $if errorlevel 1 $abort problems with awk call $offlisting $include "%fn%" $onlisting alias (n,i,j); Scalar wMax; wMax = smax((i,j), w(i,j)); Variables x(n) location selection costs(n,n) costs between location i and j cost(n) cost to serve i obj objective; Binary variables x; Equation defp select p locations defcosts(i,j) 'costs between location i and j is w(i,j) or inf (=2*wMax))' defcost(i) cost to serve i is the smallest cost between i and other locations defobj objective ; $ifthen set MIP Positive Variable diff(i,j) Binary Variable bdiff(i,j) Equation defcosts2(i,j), defdiffZero(i,j); defcosts(i,j).. costs(i,j) =g= 2*wMax - 2*wMax*x(j); defcosts2(i,j).. cost(i) =e= costs(i,j) - diff(i,j); defdiffZero(i,j).. diff(i,j) =l= 2*wMax - 2*wMax*bdiff(i,j); defcost(i).. sum(j, bdiff(i,j)) =g= 1; $else defcosts(i,j).. costs(i,j) =e= ifthen (x(j)>=0.5, w(i,j), 2*wMax); defcost(i).. cost(i) =e= smin(j, costs(i,j)); $endif defp.. sum(n, x(n)) =e= p; defobj.. obj =e= sum(n, cost(n)); model pmedian /all/; costs.lo(i,j) = w(i,j); $ifthen set MIP solve pmedian us mip min obj; $else solve pmedian us minlp min obj; $endif