Binary combinatorial optimization with hard to compute costs

An answer to this question on the Scientific Computing Stack Exchange.

Question

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?

Answer

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.