Welcome to our community

Be a part of something great, join today!

How to optimise the following probability / algorithm / combinatorics problem?


New member
Oct 14, 2019
I am trying to solve the following problem. Let us take a bounded domain $S$ in which an explosive device is located. A team is deployed to locate and disable the device before a certain time T (when the device explodes). There are several criteria to be satisfied:

1. The domain $S$ is partitioned into $i \in 1,...,n$ subdomains.
2. Each subdomain is searched one after another, with each search lasting for the same length of time $T/t$ for some positive integer t. These subdomain can be searched and re-searched in any order.
3. Conditioning on the device being in subdomain $i$, the probability of finding the device is $\phi_{i}\in [0, 1]$. These probabilities vary from one subdomain to another.
4. Apriori, the assigned probability of device being located in subdomain $i$ is $\pi_{i}$ (so that $\sum_{i}^{n} \pi_{i} = 1$ ).

The aim is to optimise the sequence of subdomain searches so that the probability of finding the device by time $T$ is maximised.

Now, I think this is akin to the so-called "Knapsack problem", and I have a general outline as to how one could set it up, but I am really not sure if I am on the right track or not.

Any help / advice would be appreciated. Thank you.
Last edited: