Lindo Systems

! 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