! LP formulation of a Markov Decision Problem;
!  Road repair example, average cost criterion;
! Key words: Maintenance, Markov decision process, MDP, Repair, Road repair, Steady state ;
SETS: 
 STATE: SSPROB;
 DECISION:;
 SXD( STATE, DECISION): C, Y;
 SXSXD( STATE, STATE, DECISION): P;
ENDSETS
DATA:
! Give names to the states and decisions;
 STATE = S0 S1 S2 S3;
 DECISION = D1 D2 D3;
! Definitions of states & decisions:
   S0 : road surface is excellent,
   S1 : uneven surface, cracks forming,
   S2 : some potholes,
   S3 : a real tire buster,
    D1 : do nothing,
    D2 : add thin top layer, fill potholes,
    D2 : major resurfacing;
! Only a few decisions are typically valid in each state,
  so we use sparse form and list only the valid
  combinations of
  state, decision, cost;
      SXD,     C  = 
     S0  D1    0
     S1  D1  1000
     S1  D3  6000
     S2  D1  3000
     S2  D2  4000
     S2  D3  6000
     S3  D3  6000;
! Only a few transitions are typically
  possible from each state, so list only the ones
  with positive probability.  Note: P(i, j, k) = 
  Prob{next state=j|current state=i and our decision=k};
    SXSXD,   P=
   S0 S1 D1 .875
   S0 S2 D1 .0625
   S0 S3 D1 .0625
   S1 S1 D1 .75
   S1 S2 D1 .125
   S1 S3 D1 .125
   S1 S0 D3 1
   S2 S0 D3 1
   S2 S2 D1 .5
   S2 S3 D1 .5
   S2 S1 D2 1
   S3 S0 D3 1;     
ENDDATA

SUBMODEL MDPMOD:
! Definition of variables:
   Y(I,K) = probability of being in state I
            and making decision K.
     Typically, for each I there will be only one K
    such that Y(I,K) > 0.  That is, Y(I,K) > 0 means
    if the state is I, then you should take decision K;

! Minimize average cost per period;
  MIN = AVGCOST;
    AVGCOST = @SUM( SXD( J, K): C( J, K) * Y( J, K));

! Probabilities must sum to 1;
  @SUM( SXD( J, K): Y( J, K)) = 1;

! Prob{ being in state J}= sum of probabilities of
   getting there from other states ( I, K);
  @FOR( STATE( J):
    SSPROB( J) = @SUM( SXD( J, K): Y( J, K));
    SSPROB( J) =
    @SUM( SXSXD( I, J, K): Y( I, K) * P( I, J, K));
      );
ENDSUBMODEL


CALC:
 @SOLVE( MDPMOD); ! Solve it;
! Display a little report;
  @WRITE('  State    SS_PROB', @NEWLINE( 1));
  @FOR( STATE( J):
    @WRITE('   ', STATE( J), '      ', @FORMAT( SSPROB( J), '6.5f'), @NEWLINE( 1));
      );

 @WRITE(' Average cost/period= ', AVGCOST, @NEWLINE(1));

ENDCALC