constraints formulation

Question

This question is an extension of this.

Again, I have n total fruit plantations and s number of just apple plantations.

I want to place s and (n-s) plantations on an m by m grid of field. Each s apple plantation should be a minimum distance, d away from each other. So each grid point has two possibilities: multiple (n-s) plantations or 1 s plantation and multiple (n-s) plantations.

The objective function should be minimizing the area of the grid field where n fruits are to be planted.

Also, I need to control the number of total plantations/grid points. That means for the two possibilities mentioned above, I might place multiple plantations on the same grid point.

New additional constraints:

• All calculations in Manhattan distance i.e. |x1-x2|+|y1-y2|
• This time the area calculation is approximated simply as [y2-y1]+[x2-x1] as a proxy for actual area, where y2 = max(all n plantations' y) , y1 = min(all n plantations' y), same for x2 and x1.
• For the distance constraint for s plantations, I am thinking |ai1,j1 - ai2,j2| >=d. But I need to generalize this for all plantations.
• Lastly, with another variable, I need to be able to control the number of total plantations/grid points.

Please help.

Answer 1

The distance constraints are the same as in linear programming problem formulation (extended), with only the definition of distance changing: $$a_{i_1,j_1} + a_{i_2,j_2} \le 1 \quad \text{if $0<|i_1-i_2|+|j_1-j_2|<d$}.$$ To avoid duplication of each pair, you should consider only $i_1 < i_2$ or $i_1=i_2 \land j_1<j_2$.

For the area minimization, constraints $(1)$ through $(4)$ there still apply, but the new objective is to minimize $$\sum_{k=1}^m k \left(\ell_k + w_k\right).$$

Alternatively, you can introduce variables $x_1$, $x_2$, $y_1$, and $y_2$, objective function $(x_2-x_1)+(y_2-y_1)$, and "big-M" constraints \begin{align} x_1 - i &\le (m-i)(1-f_{i,j}) &&\text{for all $i,j$}\\ i - x_2 &\le (i-1)(1-f_{i,j}) &&\text{for all $i,j$}\\ y_1 - j &\le (m-j)(1-f_{i,j}) &&\text{for all $i,j$}\\ j - y_2 &\le (j-1)(1-f_{i,j}) &&\text{for all $i,j$} \end{align} These constraints enforce $f_{i,j} \implies (x_1 \le i \le x_2 \land y_1 \le j \le y_2)$. In words, if a plantation is placed at grid point $(i,j)$, then the minimum $x$ is at most $i$, the maximum $x$ is at least $i$, minimum $y$ is at most $j$, and the maximum $y$ is at least $j$.

To enforce an upper bound of $10$ plantations per grid point, impose linear constraint $$a_{i,j} + b_{i,j} \le 10 \quad \text{for all $i,j$}$$

You also still need constraints $(1)$ through $(4)$ from linear programming formulation, but because you can now place both apple and non-apple at the same grid point, omit constraint $(5)$.