0
$\begingroup$

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

$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ Thank you for your answer. But I don't think it is that simple. 1) my question is two-dimensional, thus your constraint doesn't apply to it; 2) i, j, k should be free index (not dummy), then how to identify the ranges of i, j, k, does it hold for any two i \in 1...M, j \in 1...N? $\endgroup$ Commented Mar 10, 2022 at 0:54
  • $\begingroup$ I initially used one-indexed variables $x_i$ to match your question. Now that you have used two-indexed variables $x_{i,j}$, I updated my answer. The logic is the same, no matter what indexing you use: if two grids are colored, every grid in the corresponding rectangle must also be colored. $\endgroup$ Commented Mar 10, 2022 at 1:50
  • $\begingroup$ Thanks.......... The indexes i, j are free variables, right? This means, e.g., i ranges from 1 through M to obtain all the constraints?.................. Also, could you please clarify how to convert the logical expression to the algebraic expression, just like what you did in your old-version answer. $\endgroup$ Commented Mar 10, 2022 at 1:56
  • $\begingroup$ Yes, $\{(i_1,j_1),(i_2,j_2),(i_3,j_3)\}\subset\{1,\dots,M\}\times\{1,\dots,N\}$. $\endgroup$ Commented Mar 10, 2022 at 1:58
  • 1
    $\begingroup$ Thanks! Now I totally know what you mean. It's not the logical expression of the constraints, but the range of free indexes. $\endgroup$ Commented Mar 10, 2022 at 23:05

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.