1
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ What is new about the first bullet? $\endgroup$ Commented Aug 28, 2020 at 0:20
  • $\begingroup$ Do equations (1) and (2) cover the first bullet? There is no separate constraint/equation for the first bullet so I wondered. $\endgroup$ Commented Aug 28, 2020 at 4:23

1 Answer 1

0
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ You are a genius. $\endgroup$ Commented Sep 1, 2020 at 2:13
  • 1
    $\begingroup$ @svetlana I added more details just now. $\endgroup$ Commented Sep 7, 2020 at 17:40
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Sep 7, 2020 at 18:17
  • 1
    $\begingroup$ $\{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). $\endgroup$ Commented Sep 7, 2020 at 22:14
  • 1
    $\begingroup$ Yes, the conflict constraints have nothing to do with the length and width constraints. $\endgroup$ Commented Sep 8, 2020 at 3:17

You must log in to answer this question.