1

This question is a modified version of this. I want to know the decision variables, objective function, constraints, and non-negativity constraints for the following problem.

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.

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.

New additional constraints:

  • Each plant is to be planted only once. e.g. the same plant can't be on two different grid points.
  • This time the area is the actual area of the created grid, not the number of grid points like before.
  • Lastly, I have to ascertain that the s plantations are a certain distance, d away from each other.

Please help.

1 Answers1

0

I think the first bullet is already captured by the fact that the variables are binary or integer.

For the second bullet, you want to minimize the product of length and width, equivalently minimize the sum of logs, which you can linearize as follows. For $k\in\{1,\dots,m\}$, let binary decision variables $\ell_k$ and $w_k$ indicate whether the length or width, respectively, of the grid is $k$. The constraints are: \begin{align} \sum_k \ell_k &= 1 \tag1 \\ \sum_k w_k &= 1 \tag2 \\ f_{i_1,j_1} + f_{i_2,j_2} - 1 &\le \sum_{k \ge i_2-i_1} \ell_k &&\text{for $i_1<i_2$ and $(j_1,j_2)\in \{1,\dots,m\}^2$} \tag3 \\ f_{i_1,j_1} + f_{i_2,j_2} - 1 &\le \sum_{k \ge j_2-j_1} w_k &&\text{for $j_1<j_2$ and $(i_1,i_2)\in \{1,\dots,m\}^2$} \tag4 \end{align} Constraints $(1)$ and $(2)$ enforce one length and one width, respectively. Constraint $(3)$ enforces $$(f_{i_1,j_1} \land f_{i_2,j_2}) \implies \bigvee_{k \ge i_2-i_1} \ell_k.$$ Here, $\land$ is the logical AND operator (true if and only if all arguments are true), and $\bigvee$ is the logical OR operator (true if and only if at least one argument is true). In words, if plantations are placed at $(i_1,j_1)$ and $(i_2,j_2)$, then the length is at least $i_2-i_1$. Constraint $(4)$ is similar for the width.

The nonlinear objective is to minimize the area $$\left(\sum_{k=1}^m k\ \ell_k\right)\left(\sum_{k=1}^m k\ w_k\right).$$ Because $\log$ is an increasing function, you can equivalently minimize $$\log\left[\left(\sum_{k=1}^m k\ \ell_k\right)\left(\sum_{k=1}^m k\ w_k\right)\right]=\log\left(\sum_{k=1}^m k\ \ell_k\right)+\log\left(\sum_{k=1}^m k\ w_k\right).$$ Because of constraints $(1)$ and $(2)$, this nonlinear function is equal to the linear function $$\sum_{k=1}^m \log(k)\ell_k+\sum_{k=1}^m \log(k)w_k=\sum_{k=1}^m \log(k) \left(\ell_k + w_k\right).$$

For the third bullet, you can introduce conflict constraints $a_{i_1,j_1} + a_{i_2,j_2} \le 1$ if the distance between $(i_1,j_1)$ and $(i_2,j_2)$ is less than $d$.

RobPratt
  • 45,619
  • You are a genius. –  Sep 01 '20 at 02:13
  • Please look at this if you have some time : https://math.stackexchange.com/questions/3814154/mixed-linear-constraints-formulation-extended –  Sep 04 '20 at 14:09
  • I am so dumb. Can I ask for some elaboration on the derivation of constraint 3 (and what it enforces and its notations please)? Also some explanation on the objective - why is the log term and (l_k + w_k) term multiplied? –  Sep 07 '20 at 07:29
  • 1
    @svetlana I added more details just now. – RobPratt Sep 07 '20 at 17:40
  • Thanks again. For constraint 3, fi_1j_1 +fi2_j2 -1 why is the -1 necessary? Also this reason, if plantations are placed at (i1,j1) and (i2,j2), then the length is at least i2−i1-- why is this rule important here? If we didn't add this rule what would happen please? –  Sep 07 '20 at 18:06
  • 1
    Without the $-1$, the left hand side would be $2$ if $f_{i_1,j_1}=f_{i_2,j_2}=1$, and this would violate constraint $(1)$. Without constraint $(3)$, the length variable $\ell_k$ would not accurately reflect the true length between assigned plantations. – RobPratt Sep 07 '20 at 18:17
  • 1
    ${1,\dots,m}^2={1,\dots,m} \times {1,\dots,m}$. The conflict constraint means that $(i_1,j_1)$ and $(i_2,j_2)$ do not both contain an apple (but one of them can). – RobPratt Sep 07 '20 at 22:14
  • THanks again. If I have this last conflict constraint ai1,j1+ai2,j2≤1 do I still need constraints 3 and 4? –  Sep 08 '20 at 02:09
  • 1
    Yes, the conflict constraints have nothing to do with the length and width constraints. – RobPratt Sep 08 '20 at 03:17