0

I want to formulate equations for this problem. I have previously looked at many examples and I am new to this.

Suppose 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.

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 (n-s) plantations/grid points. That means for all the plantations except the apple plantations, I might place multiple plantations on the same grid point.

Please help.

1 Answers1

1

You need three sets of decision variables. Let binary variable $a_{i,j}$ indicate whether an apple plantation is placed at grid point $(i,j)$. Let nonnegative integer variable $b_{i,j}$ be the number of non-apple fruit plantations placed at $(i,j)$. Let binary variable $f_{i,j}$ indicate whether at least one fruit plantation is placed at $(i,j)$. The problem is to minimize $\sum_{i,j} f_{i,j}$ subject to linear constraints: \begin{align} \sum_{i,j} a_{i,j} &= s \tag1\\ \sum_{i,j} b_{i,j} &= n-s \tag2\\ a_{i,j} &\le f_{i,j} &&\text{for all $i,j$} \tag3\\ b_{i,j} &\le (n-s) f_{i,j} &&\text{for all $i,j$} \tag4\\ b_{i,j} &\le (n-s) (1 - a_{i,j}) &&\text{for all $i,j$} \tag5 \end{align} Constraint $(1)$ places all $s$ apple plantations. Constraint $(2)$ places all $n-s$ non-apple plantations. Constraint $(3)$ enforces $a_{i,j}=1 \implies f_{i,j}=1$. Constraint $(4)$ enforces $b_{i,j}>0 \implies f_{i,j}=1$. Constraint $(5)$ enforces $a_{i,j}=1 \implies b_{i,j}=0$.

RobPratt
  • 45,619
  • I need to minimize f_i,j for the minimizing area constraint. I have some rough ideas for the rest. It would be good for my personal development to read a descriptive solution to this problem from an experienced person like you. –  Aug 26 '20 at 02:11
  • 1
    I added the details now. Can you predict the optimal objective value? – RobPratt Aug 26 '20 at 02:44
  • Thank you very much. I could not predict (5) at all. I am not being successful to predict optimal objective value either. –  Aug 26 '20 at 03:18
  • 1
    Each apple plantation needs its own point, and all the rest of the plantations can be placed together in one additional point. – RobPratt Aug 26 '20 at 03:43
  • For the rest of the plantations can it be controlled? Like, say 5 plantations for the rest of the plantations/grid point? –  Aug 26 '20 at 20:04
  • 1
    If you want to limit the non-apples to 5 plantations per grid point, change the $(n-s)$ in constraint $(4)$ to 5. – RobPratt Aug 26 '20 at 22:22
  • Could you please elaborate on equations (3), (4), (5)..I thought I understood why enforcing those constraints is necessary but I don't ...Thanks a lot.. –  Aug 29 '20 at 17:58
  • Without (3), you could have $a_{i,j}=1$ and $f_{i,j}=0$, which would mean that you place an apple plantation at $(i,j)$ without paying for it in the objective. Constraint (4) is similar for non-apple plantations. Without (5), you could place both apple and non-apple plantations at the same grid point. – RobPratt Aug 29 '20 at 19:53