# Experimental Design Problem with Goofy Constraints

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.

• I'm not sure I understand: All the $B_{mf}$ are known constants before the experiment? What will be measured in the experiment? I think your description is too brief! Commented Aug 16, 2020 at 2:35
• @kjetilbhalvorsen I added the explanation to the end of the question. Please let me know if it did not clear things up. Commented Aug 16, 2020 at 2:56
• So the problem is to choose the $m, f$ indices with the $B_{mf}$ known, which looks like a pure optimization problem, and then the randomization&experimentation follows? Commented Aug 16, 2020 at 3:31
• It certainly that optimization subject to the constraints, but also what type of randomization and analysis makes sense here (matches pairs of meadows or something else). Commented Aug 16, 2020 at 3:37
• Unless there are some special structure on the meadows, I cannot see how matched pairs can help? Commented Aug 16, 2020 at 4:32

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.

• A list of Qs with answers about knapsack problems Commented Aug 16, 2020 at 22:29
• This is already quite helpful. I am having some trouble mapping my meadows-flowers problem to one of the generalized KPs, or else expressing it as a set of constraint. Is there a connection that is obvious to you here? Commented Aug 17, 2020 at 6:38
• Aren't the restrictions like $20 \leq \sum J_f \leq30$. The knapsack problem with $\sum J_f \leq 30$ might give you a selection with less than 20 types of flowers but higher sum because higher $B_{mf}$ Commented Aug 19, 2020 at 6:35
• @Sextus Empiricus: This is true, I will edit. Also I guess the pattern of undefinedness may play games ... Commented Aug 19, 2020 at 23:58