4
$\begingroup$

I have a combinatorial problem regarding the optimal placement of sensors. I want to find the optimal placement of $N$ sensors, given $M$ possible locations, $N < M$. Right now I'm working with values of $N$ and $M$ around 15 and 30, respectively, but ideally, it could be scaled into the thousands. The cost that I want to minimize is the worst possible detection delay (i.e. max delay) of any malfunction in the system. In other words, it is a minimax problem.

Given one particular arrangement of $N$ sensors, the computation to find the max delay is a black box that takes about 3 seconds. This can not be shortened, nor can I access the code within the black box. The black box takes as input the arrangement of sensors and outputs a single value, which I want to minimize.

Many of the combinatorial optimization algorithms that I've found, such as branch-and-bound, assume that the cost is readily available and that the cost of subsets of the solution is also available. For example, given locations $\{1,2,3\}$, and $N=2$, the branch-and-bound algorithm would want to know the cost of $\{1\}$, $\{2\}$, $\{3\}$, $\{1,2\}$, $\{1,3\}$, and $\{2,3\}$ in the worst case. This makes it worse than exhaustive search since exhaustive search would only require the calculations for $\{1,2\}$, $\{1,3\}$, and $\{2,3\}$.

For larger values of $M$, branch-and-bound only gets worse.

My questions are:

  1. Is there a name for this type of problem?
  2. Are there resources regarding solutions?
$\endgroup$
1
$\begingroup$

It's true that the number of pairs scales as $N^2$ and the number of subsets as $2^N$, but only a small subset of the sets are ever considered because each check rules out many others, so the overall cost is smaller.

If you have black boxes for any $N$, why not wrap the box in a function that constructs appropriate boxes on the fly and caches them for reuse?

You still pay the cost of computation, but you now have a tool appropriate for the solvers you mention.

Alternatively, you need a form of optimization that minimises calls to the objective. Bayesian optimization (see the paper "Bayesian Optimization for a Better Dessert") is designed for such a situation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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