Binary combinatorial optimization with hard to compute costs

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?

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?