! Facility interdiction model in LINGO.
Given:
Player 2 has
a set of demand points i,
a set of supply points j, and
d(i,j) = distance or cost of supplying
demand point i from supply facility j.
Player 2 uses the rule: each demand point is
assigned to the closest supply facility that is operating.
Player 1 would like to interdict/destroy the r facilities
that will increase the supply costs of Player 2 the most.
Which r facilities should be interdicted by Player 1?
! Reference:
Church, R., M. Scaparra, and R. Middleton(2004),
"Identifying Critical Infrastructure:
The Median and Covering Facility Interdiction Problems",
Annals of Association of American Geographers, vol. 93, no. 3, pp. 491-502;
! Keywords: Interdiction, Game theory, Assignment, Target selection;
SETS:
DP: a; ! Set of demand points;
FP: s; ! Set of facility points;
DXF( DP, FP): d, x;
ENDSETS ! Parameters:
a(i) = demand at demand point i,
d(i,j) = distance between demand point i and
facility point j,
r = number of facilities to be interdicted
or eliminated;
DATA:
DP = 1..6; ! The demand points;
FP = 1..4; ! The current facility points;
a = 9 4 8 5 2 3; ! Demand at each demand point;
d = 4 3 8 2 ! The demand x facility ;
1 3 8 5 ! distance matrix;
5 3 4 8
9 2 3 4
3 9 1 1
6 2 5 3;
ENDDATA
SUBMODEL INTERDICT:
! Variables:
s(j) = 1 if facility at location j is interdicted,
x(i,j) = 1 if demand i was assigned to facility j
after interdiction.
Maximize the cost of the assignment, the objective
of the player doing the interdicting.;
MAX = Z;
Z = @SUM(DXF(i,j): a(i)*d(i,j)*x(i,j));
! Number of interdicted facilities = r;
@SUM(FP(j): s(j)) = r;
! Each demand point i is assigned to some facility point j;
@FOR( DP(i):
@SUM( DXF(i,j): x(i,j)) = 1;
);
! The objective of the player 2.
Each demand point i, cannot be assigned
to a facility k more distant than j
except if j has been interdicted;
@FOR( DP(i):
@FOR( FP(j):
@SUM( DXF(i,k) | k #NE# j #AND# d(i,k) #GT# d(i,j): x(i,k)) <= s(j);
);
);
! Apply the 0/1 restrictions;
@FOR( FP(j): @BIN(s(j)));
@FOR( DXF(i,j): @BIN(x(i,j)));
ENDSUBMODEL
CALC:
! Turn off default output;
@SET('TERSEO', 2);
! Try all possible number of facilities to interdict;
@WRITE(' Interdiction of a Supply System.',@NEWLINE(1));
@FOR( FP(r1):
r = r1-1;
@SOLVE( INTERDICT);
@WRITE(' If Player 1 can interdict ', r,' facilities,',@NEWLINE(1),
' Cost to player 2 is: ',Z, @NEWLINE(1),
' Facilities to interdict are:');
@FOR( FP(j) | s(j) #GT# 0.5:
@WRITE(' ',FP(j));
);
@IFC( r #EQ# 0: @WRITE(' None'));
@WRITE( @NEWLINE(1),' Player 2 assignments are:',@NEWLINE(1));
@WRITE(' Demand point Supply facility',@NEWLINE(1));
@FOR( DXF(i,j) | X(i,j) #GT# 0.5:
@WRITE(' ', i, ' ', j, @NEWLINE(1));
);
@WRITE(@NEWLINE(1));
);
ENDCALC
|