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
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
```

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.

Keywords: mixed integer linear programming, mixed integer nonlinear programming,
p-median problem, facility location problem
\$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%"
\$ifE errorLevel<>0 \$abort problems with awk call

\$offListing
\$include "%fn%"
\$onListing

Alias (n,i,j);

Scalar wMax;
wMax = smax((i,j), w(i,j));

Variable
x(n)       'location selection'
costs(n,n) 'costs between location i and j'
cost(n)    'cost to serve i'
obj        'objective';

Binary Variable 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 using mip   min obj;
\$else
solve pmedian using minlp min obj;
\$endIf
``````
GAMS Development Corp.
GAMS Software GmbH

General Information and Sales
U.S. (+1) 202 342-0180
Europe: (+49) 221 949-9170