1
$\begingroup$

I have a system with $k$ tasks, where each task is a state in a Markov chain. I am working on allocating agents to each task. I would like to achieve a specific distribution of the agents among these tasks in the steady state. How do I optimize the Transition Probability Matrix (TPM) using OR-Tools?

Some info of my system: The system exists as a simulation of the process. Hence, each agent is simulated to make an actual choice about which state to go to from its current state based on the TPM. In one iteration, every agent makes a transition. I run this for a very large number of iterations to simulate the steady state.

Variable: TPM

Constraints: Standard constraints of a TPM

Optimization: Minimize difference between desired distribution vector and actual distribution vector

Edit: While I appreciate the analytical means of arriving at the values of the TPM, I am interested in optimizing the TPM based on the results of simulation. I suppose this shifts the focus from the conceptual approach behind finding the values in the TPM, to how I may use my own function/method to determine the suitability of each intermediate solution generated by the solver (and how the solver uses the suitability determined by the custom function) specifically in OR-Tools.

$\endgroup$
7
  • $\begingroup$ Are the transitions deterministic? Also, could you model your problem as an integer program instead of a MDP? $\endgroup$
    – PeterD
    Oct 19, 2022 at 22:07
  • $\begingroup$ How many states? Is there a reason you can't determine the steady state distribution for a candidate transition matrix by analytical/numerical means, and hereby avoid simulation and allow an approach along the lines of @RobPratt? $\endgroup$ Oct 20, 2022 at 0:04
  • $\begingroup$ @PeterD I'm not quite sure what a deterministic transition means. But, the transition values don't change during a simulation (and are determined by the solver). Please follow my reply to Mark Stone's comment for the second question :) $\endgroup$ Oct 20, 2022 at 5:44
  • $\begingroup$ @MarkL.Stone finite (3-6 mostly) number of states. I am avoiding analytical methods as I wish to demonstrate creative intersections of operations research, stochastic processes and robotics. While pursuing this problem, I found this certain capability of optimising using simulation very interesting. That's all :) $\endgroup$ Oct 20, 2022 at 5:47
  • 1
    $\begingroup$ I thought you comment "I am avoiding analytical methods as I wish to demonstrate creative intersections of operations research, stochastic processes and robotics" was allowing for complications to the model, as yet unknown to me, which might render analytical methods impossible. It's actually nice, but not necessary, to start with a problem which can be simulated and evaluated analytically. And then introduce complications which can't be evaluated analytically.. But again, don't rely on me if this is for a school project you must complete, and do so by a deadline. $\endgroup$ Oct 20, 2022 at 15:36

1 Answer 1

3
$\begingroup$

Given target vector $\pi$, if there is such a transition probability matrix $P$ with $\pi$ as its limiting distribution, you can find one via linear programming (LP), as shown in my answer here.

Otherwise, you can minimize the absolute error via LP by minimizing $\sum_j (s_j + t_j)$ subject to \begin{align} \sum_i \mu_i P_{ij} &= \mu_j &&\text{for all $j$} \label1\tag1 \\ \sum_j P_{ij} &= 1 &&\text{for all $i$} \label2\tag2 \\ P_{ij} &\ge \epsilon && \text{for all $i$ and $j$} \label3\tag3 \\ \mu_j - s_j + t_j &= \pi_j &&\text{for all $j$} \\ s_j &\ge 0 && \text{for all $j$} \\ t_j &\ge 0 && \text{for all $j$} \end{align}

Alternatively, you can minimize the sum of squares error via quadratic programming by minimizing $\sum_j (\mu_j - \pi_j)^2$ subject to \eqref{1}-\eqref{3}.

$\endgroup$
1
  • $\begingroup$ Thank you for the thoughtful and spot on method of arriving at the TPM values. I have added an edit to my original question explaining how I would like an approach specific to OR-Tools that allows me to use my simulation runs as methods of evaluating the solver's intermediate solutions. Thank you :) $\endgroup$ Oct 20, 2022 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.