Most efficient way to fill this specific 9x9 grid

Question

I've been thinking about this question for a while.

Say, you have a 9x9 grid. Each of these grids can have a state - nothing, supplier, and a generator. A supplier can supply 1 unit to each generator nearby it, including diagonals, to a maximum of 8 generators. A generator cannot work unless it is powered by a supplier.

What's the most efficient way to place these to get the greatest number of generators?

Answer 1

Let $g \ge 0$ be the number of generators and $s \ge 0$ the number of suppliers. You want to maximize $g$ subject to \begin{align} g+s &\le 81 \tag1\label1\\ g -8s &\le 0 \tag2\label2 \end{align} Now multiplying constraint \eqref{1} by $8/9$ and constraint \eqref{2} by $1/9$ and adding them up yields $g \le 72$, which is attainable by placing a supplier in the middle of each $3 \times 3$ "Sudoku" subgrid:

For a $10 \times 10$ grid, the same approach yields an upper bound of $\lfloor(8/9)10^2\rfloor = 88$, which is not attainable. Via integer linear programming, with two binary decision variables per cell, the maximum turns out to be $84$: