Rescom TP instructions
Instuctions for the Lab on Markov chain modeling and MDP analysis, at the RESCOM2019 summer school
Sommaire
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> .
