## Optimal square foot gardening with companion planting and mixed-integer programming

If you are planning next year’s vegetable or herb garden, one way to do that is to use the square grid layout in what is called square foot gardening. The principle is simple: divide your plot in a square grid, and assign to each square a specific plant. For example: square 1 will have beets, square two carrots, and so on.

There is also something called companion planting: the growing of plants in close proximity to both their benefit. A well known example is squash, maize and beans being grown together for thousands of years in Mesoamerica.

Let’s combine these two concepts into *optimal square foot gardening*: planning the vegetable garden in such a way that plants grown next to each other, stimulate each other, and those that negatively effect each other are spaced apart.

I’ll formulate this into a mixed binary-linear programming problem, allowing us to give up requirements on the number and type of vegetables we want in the garden, and letting a solver figure out where to best put them.

## The optimization problem

The garden is assumed to be rectangular with a grid of size , and that we have to pick from vegetables. Let’s introduce the decision variables to indicate whether vegetable is grown in square .

To ensure the garden is full, we have the constraint

Because we need keep track of which vegetables grow next to each other, we use a variable , where

We can code this using

if is next to (and for simplicity we’re only counting top, bottom, left and right, no diagonals), and 0 if they are not.

Any constraints on the minimum number of vegetables of a specific type, , can be encoded using

Now, for the objective. Assume we have some symmetric matrix where is positive if plants and stimulate each other and negative if they do not. The actual values can maybe be estimated from data, but for simplicity purposes I’m using simple rules with according to a table I found:

The objective is to sum up the bonusses (or negative scores) for each pair of squares:

This problem is a mixed Binary-Linear programming non-convex optimization problem, that we can try to solve with for example Julia, JuMP and the Cbc solver.

## Example

Let’s say we try to plant a vegetable garden that is 4 by 6 squares, and plant it with at least 3 of each of the following vegetables:

- Beans
- Corn
- Peas
- Peppers
- Squash
- Tomatoes

and we have the following scoring matrix:

Running the optimization with a timeout of 90 seconds, we get back the following plan:

I indicated the different vegetables by color, and the score is indicated by a colored circle. I’d say this is a pretty good solution! Only two edges are not giving a positive boost, and none have negative effects.

## Conclusion

I described a way to optimize the layout of a vegetable garden.

The optimization technique will need further research. The optimization problem as stated here gets really large really quickly with increasing size of grids and possible vegetables. Perhaps the convex relaxation technique I’ve used in other posts can handle these, because this large scale MBLP will turn into a series of large LPs. Even though this not necessarily gives the optimal solution, maybe we will obtain a very good one anyway. Another possible technique avoids having so many variables is a Genetic Algorithm, so maybe that’s the path forward.

Maybe the future of this technique is not so much in small vegetable gardens, but in larger farms that want to grow multiple crops in a way that minimizes large contiguous fields of monocrops. Before we’re there though, I assume research is necessary to make actually farming such a diverse field economically viable and technically possible. Different crops need different attention.