I am stuck in a constraint formulation of a discrete optimization problem. Consider a board of Cartesian grids (M rows by N columns). We are going to color some grids among them. There is a geometric constraint that the colored grids must form a rectangle (and its interior, no holes).
My question is: How to algebraically formulate this geometric constraint (so that it can be handled by computer)?
The decision variables can be written as $x_i, i\in \{1,2,\ldots,M\cdot N\}$. $x_i=1$ if the $i$th grid is colored; $x_i=0$ if the $i$th grid is not colored. (Or since the board is 2D, for convenience, you can use a two-digit index to denote a decision variable, for example, $x_{ij}=1$ if the grid located at $i$th row and $j$th column is colored, now $i\in \{1,2,\ldots,M\}$ and $j\in \{1,2,\ldots,N\}$)
A sketch to help you understand the question: sketch
You want to enforce $$(x_i \land x_j) \implies x_k,$$ where $1\le i<j \le M\cdot N$ and $k$ is within the rectangle determined by $i$ and $j$. Rewriting in conjunctive normal form yields $$ (x_i \land x_j) \implies x_k \\ \lnot (x_i \land x_j) \lor x_k \\ \lnot x_i \lor \lnot x_j \lor x_k, $$ from which we obtain linear constraint $$(1-x_i) + (1-x_j) + x_k \ge 1,$$ equivalently, $$x_i + x_j - x_k \le 1.$$
Update to match your two-indexed variables: $$x_{i_1,j_1} + x_{i_2,j_2} - x_{i_3,j_3} \le 1,$$ for all $(i_1,j_1)$, $(i_2,j_2)$, and $(i_3,j_3)$ such that $(i_3,j_3)$ is in the rectangle determined by $(i_1,j_1)$ and $(i_2,j_2)$. That is, $$\min(i_1,i_2) \le i_3 \le \max(i_1,i_2) \text{ and } \min(j_1,j_2) \le j_3 \le \max(j_1,j_2).$$ Alternatively, you can avoid duplicate constraints by imposing lexicographic ordering of $(i_1,j_1)$ and $(i_2,j_2)$ as follows: $$(i_1 < i_2 \lor (i_1 = i_2 \land j_1 < j_2)) \land (i_1 \le i_3 \le i_2) \land (\min(j_1,j_2) \le j_3 \le \max(j_1,j_2)).$$