I am trying to formulate a constraint for an MILP optimization problem.
There are $N*N$ weighted points distributed on a 2D plane, each point denoted by its coordinate index $(i,j)$.
The decision variables are:
- $N*N$ binary variables $z_{ij} \in \{0,1\}, i \in \{1,\ldots,N\}, j \in \{1,\ldots,N\} $;
- 12 continuous variables $a_k, b_k, c_k \in \mathbb{R}, k \in \{1,2,3,4\}$. Denote the region bounded by four lines $ a_kx+b_ky+c_k = 0, k \in \{1,2,3,4\} $ as $S$.
The optimization problem is to select a region $S$ (determined by four lines) to cover points as few as possible while ensuring the weight sum of the covered points is greater than a threshold.
The constraint to formulate is: $z_{ij} = 1$ iff point $(i,j) \in S$ (i.e., point $(i,j)$ is covered by $S$) ; otherwise $z_{ij} = 0$. This constraint describes the relation between the binary decision variables $z_{ij}$ and continuous decision variables $a_k, b_k, c_k$. How do I formulate this constraint in terms of decision variables $z_{ij}$ and $a_k, b_k, c_k$ only, how do I formulate "iff"?
A sketch is attached to illustrate this:
You want to enforce $$z_{ij}=1\implies \bigwedge_{k=1}^4 (a_k i+b_k j+c_k\le 0) \quad \text{for all $i,j$},$$ and you can do so via linear big-M constraint $$a_k i+b_k j+c_k\le M_{ij1}(1-z_{ij})\quad\text{for all $i,j,k$}. \tag1\label1$$ Similarly, you can enforce $$z_{ij}=0\implies \bigvee_{k=1}^4 (a_k i+b_k j+c_k\ge 0) \quad \text{for all $i,j$}$$ via linear constraints \begin{align} -a_k i-b_k j-c_k &\le M_{ij2} z_{ijk} &&\text{for all $i,j,k$} \tag2\label2 \\ 1 - z_{ij} &\le \sum_k (1 - z_{ijk}) &&\text{for all $i,j$} \tag3\label3 \end{align} If you want to avoid ambiguity of $z$ on the lines, introduce a small positive tolerance $\epsilon$ and add it to the left-hand side of \eqref{2}, as follows: $$-a_k i-b_k j-c_k + \epsilon\le M_{ij2} z_{ijk}.$$