Rescom TP instructions

Instuctions for the Lab on Markov chain modeling and MDP analysis, at the RESCOM2019 summer school

Objective

The goals of the Lab session is

• program the model of a discrete-time queue with impatience, batch size and finite capacity, using the marmoteCore library;
• program the same model with a control of admission in service, with the marmoteMDP library;
• compute the optimal service policy in this queue.

Steps

Preparation

The first step is to have the library installed on your computer. Two possibilities:

• using a virtual machine with virtualbox
  • download VM + instructions from this page
  • copy it from USB drive, available at the conference.
• using the compiled library (linux only)
  • tarball + instructions from marmoteCore's site

The instructions with virtualbox are then:

• install the virtualbox software from its web site
• launch virtualbox
• click on "Machine > Add"
• enter the location of the virtual machine that has been downloaded
• select the VM (Rescom2019_TP) in the right-hand pane and click on "Start"
• log in with username/password pierre/Rescom2019*
• you should see a desktop with two folders: TP_Marmote and TP_MDP

Instructions for building Markov Chains

Testing the example provided

• Click on the TP_Marmote folder
• click on the file "example1.cpp" (or right-click then select "geany")
• a command-line terminal should appear at the bottom. Type

./example1

Example 1: construction of a discrete-time Markov chain on a 3-state space.

• the program takes as arguments:
  • n, a number of steps
  • p1 p2 p3, three probabilities summing up to 1, representing the initial distribution
• it outputs
  • the probability transition matrix
  • a trajectory x[0], x[1], ... x[n]

• run the example with values, e.g.

./example1 4 0.2 0.3 0.5

• use the editor to modify the code example1.cpp, in order to make state 2 absorbing
• compile by clicking "Construire > Make"
• execute again
• modify further the code to make it compute the value of the distribution after n steps:

 Distribution* trDis = c1->TransientDistributionDT( 0, n );
 trDis->Write( stdout, STANDARD_PRINT_MODE );

• compile and execute

Developing a new model

• download/copy the skeleton of the program from here.
• copy/rename it as main.cpp (overwite the present one)

The file contains:

• the "include" instructions necessary
• a "combinations" and "binomial" useful for computing some probabilities
• the template of a "MakeGenerator" function returning a matrix (type SparseMatrix)
• a main() function.

• modify the code of MakeGenerator( batchDistrib, batchSize, bufferSize ) to have it create the transition matrix of the queue with
  • arrivals in batches distributed according to batchDistrib
  • one server serving batches of size batchSize
  • buffer + server capacity = bufferSize

The object DiscreteDistribution:

• represents a discrete distribution on some finite set of values
• is created as

new DiscreteDistribution( n, values, probas );

where n is the number of values, and the two other parameters are arrays of double.

• has member functions
  • nb_vals() for getting the number of values
  • batchDistrib->values() for getting the array of values
  • batchDistrib->probas() for getting the array of probabilities
  • Mean() for computing its average
  • Write( stdout, STANDARD_PRINT_MODE ) for displaying it on the terminal.

• in the main(), create a DiscreteDistribution object for the distribution:
  • with values 0, 1, 2, 3, 4,
  • with probabilities 1/2, 1/4, 1/8, 1/16, 1/16
• adapt the code from example1.cpp to create a SparseMatrix object with MakeGenerator, then a Markov chain
• simulate the chain for some time
• compute its stationary distribution with the MarkovChain method:

Distribution* StationaryDistributionDT();

• then write it to the terminal.

Instructions for building a MDP model

• download/copy the skeleton of the program from here.
• adapt the code of the file MDP_jouet.cpp in order to:
  • create in the object P1 the transition matrix of a queue with batch service (reuse the code of the previous exercise)
  • create in the object P2 the transition matrix of the same queue, but without any service
  • create in the object R1 the matrix of rewards/costs for each pair (state,action)
• create the discountedMDP object from these elements
• solve the MDP problem with the discountedMDP method

solutionMDP* valueIteration( epsilon, maxIter )

where epsilon is some precision parameter and maxIter the maximum number of iterations

• write the result to the terminal with the writeSolution() method
• do the same with the discountedMDP method policyIterationModified( epsilon, maxIter, value, period )
  where value = 0.01 and period = 100
• compile and execute

Formulas

<math xmlns="http://www.w3.org/1998/Math/MathML"> <mtable class="m-displaymath" displaystyle="true" style="display: block; margin-top: 1.0em; margin-bottom: 2.0em"> <mtr> <mtd> <mspace width="6.0em" /> </mtd> <mtd columnalign="left"> <mi>c</mi> <mrow> <mo form="prefix">(</mo> <mi>x</mi> <mo>,</mo> <mi>q</mi> <mo form="postfix">)</mo> </mrow> <mi> </mi> <mo>=</mo> <mi> </mi> <mi>q</mi> <mspace width="0.167em" /> <msub> <mi>c</mi> <mi>B</mi> </msub> <mspace width="0.167em" /> <mo>+</mo> <mspace width="0.167em" /> <mrow> <mo form="prefix">(</mo> <msub> <mi>c</mi> <mi>L</mi> </msub> <mspace width="0.167em" /> <mi>α</mi> <mo>+</mo> <msub> <mi>c</mi> <mi>H</mi> </msub> <mo form="postfix">)</mo> </mrow> <mspace width="0.167em" /> <msup> <mrow> <mo form="prefix">(</mo> <mi>x</mi> <mo>-</mo> <mi>q</mi> <mi>B</mi> <mo form="postfix">)</mo> </mrow> <mo>+</mo> </msup> <mi> </mi> <mo>=</mo> <mi> </mi> <mi>q</mi> <mspace width="0.167em" /> <msub> <mi>c</mi> <mi>B</mi> </msub> <mspace width="0.167em" /> <mo>+</mo> <msub> <mi>c</mi> <mi>Q</mi> </msub> <mspace width="0.167em" /> <msup> <mrow> <mo form="prefix">(</mo> <mi>x</mi> <mo>-</mo> <mi>q</mi> <mi>B</mi> <mo form="postfix">)</mo> </mrow> <mo>+</mo> </msup> <mi> </mi> <mo>,</mo> </mtd> </mtr> </mtable> </math> with <math xmlns="http://www.w3.org/1998/Math/MathML"> <mrow> <msub> <mi>c</mi> <mi>Q</mi> </msub> <mo>=</mo> <msub> <mi>c</mi> <mi>L</mi> </msub> <mspace width="0.167em" /> <mi>α</mi> <mo>+</mo> <msub> <mi>c</mi> <mi>H</mi> </msub> </mrow> </math> .