Experimental Design Problem with Goofy Constraints

Question

I am having trouble designing an experiment. I will give a hypothetical example that shares the main features of my actual problem.

Suppose there are:

1. $M$ meadows, indexed by $m={1,...,M}$, where $M \approx 1000$ if that simplifies things.
2. $F$ types of flowers, indexed by $f={1,...,F}$, where $F \approx 150$.
3. no meadow has all the species of flowers
4. every meadows has at least one type of flower growing on it
5. $B_{mf}>0$ is a known and stable, but varying, value for each type of flower in a particular meadow.

I want to select $V$ varieties (where $V \in [20,30]$) and $L$ meadows such that $\sum B_{mf}$ is maximized, subject to the following constraints:

1. all $V$ varieties must grow in every one of the $L$ selected meadows
2. I wind up with $V\cdot L = P\approx 5000$ flower-meadow pairs to randomize for an experiment
3. Randomization has to be at the meadow level

The $B_{mf}$ parameters are known beforehand. The treatment is bringing in bees to pollinate the flowers and $B_{mf}$s comes from a botanist who believes that particular sites and flowers would benefit a lot. The control group is denied pollination. The analysis will test the hypothesis that bees improve flower yield overall, and that this effect will be higher in meadows with higher $B_{mf}$. So it's a test of the pollination and also of the botanist. We want to bring the bees to the most promising meadows, and measure the effect there. The plan it to test less promising meadows later.

The $L$ meadows will be split into a treatment and control group and compared in terms of some outcome $Y$. In addition to the sampling problem, I am not sure if doing matched pairs makes sense here, or a more general randomized block design.

I would appreciate any advice, references, or solutions to the design and analysis. If anything is unclear, please let me know.

---

Addendum: I don't know if this simplifies the problem, but you can also assume that all meadows have every type of flower, but that for some meadows $B_{mf}=0$ for at least one species.

Answer 1

First, the problem of maximizing $\sum B_{mf}$ is a knapsack problem, there does exist at least one R package for such problems, adagio. If $B_{mf}$ is undefined for some combinations, just give it some negative value!

Then, assuming some pairs are chosen that way, the problem is the design. If the treatment effect really depends on $B_{½mf}$ (and to test that), it might be an advantage to restrict the randomization to some balancing of the $B_{mf}$. You asks about a paired design, which would entail selecting paits of meadows with close $B$'s. Maybe that will loose too many df's, so just define blocks with little variation in the $B$'s, and randomize within the blocks. Hope I have understood the problem correctly ...

More about the knapsack problem Introduce binary indicator variables $I_m$ for the chosen meadows and $J_f$ for the chosen flowers, then you want to maximize $\sum_m\sum_f I_m B_{mf} J_f$. Observe that this give a solution that satisfy your restriction

all V varieties must grow in every one of the L selected meadows

Which asks for selecting a (rectangular ) submatrix of $B$ that maximizes the sum of its elements. In matrix terms, this means maximizing the quadratic expression $$ I^T B J $$ where $I, J$ are the vectors with elements $I_m, J_f$, under the restriction $\sum I_m \leq L, \sum J_f \leq V$. When some $B_{mf}$ is undefined, assign those a sufficiently large negative value might be sufficient, but what to do in this case might depend on the pattern (and quantity) of undefinedness.

This problem is similar to the Quadratic knapsack problem but extends that too, and seems to be known as the maximum sum rectangular submatrix problem. But some formulations of that problem seems to seek for a contiguous submatrix, which is not what we want! I don't have time to study this more now, but have asked this question: https://or.stackexchange.com/questions/4730/a-variant-of-maximum-sum-subarray-problem so hopefully some of the people there with experience in combinatorial optimization can help.