linear programming (is this doable?) [closed]

Question

I have the LP formulation at the link below for the following problem:

my lp formulation

Minimize:

• $\sum_{i=1}^{N_1} \sum_{j=1}^{N_2} x_{ij}$

Subject to:

• $\sum_{i=m}^{m+a-1} \sum_{j=n}^{n+b-1} x_{ij} \ge k$
• $x_{ij} \in \{0,1\}$

where

• $\forall m, 1 \le m \le N_1 - a + 1 \wedge$
• $\forall n, 1 \le n \le N_2 - b + 1$

We have a $N_1 \times N_2$ grid. Each cell of the grid can have the value either 0 or 1. Assume that we have $a \times b$ windows as the subset of the $N_1 \times N_2$ grid where $a < N_1$ and $b < N_2$, and we want to have at least $k$ of the cells in each window have the value 1. We want to minimize the number of cells having the value 1.

$x_{ij}$, in the formulation, represents the cell at $i$th column and $j$th row.

Actually, this problem is a reduction from the problem, Hitting Set.

Now, I want to add another set of constraints which guarantees that the pairs that will be formed out of the cells (having value 1, and location $(i,j)$) of the $N_1 \times N_2$ grid will have unique slope values. I've been thinking on this, but couldn't figure out if it is doable or not using LP.

Any ideas, suggestions?

Thanks,

Answer 1

BTW you have an IP. You'd have an LP if you relax the $x_{ij} \in \{0, 1\}$ constraint to $0\leq x_{ij} \leq 1$.

For your question: for two pairs of cells $\{(i, j), (i + u, j + v)\}$ and $\{(k, l), (k + u, l + v)\}$, you can add a constraint: $x_{ij} + x_{i + u, j + v} + x_{kl} + x_{k + u, l + v} \leq 3$. In the IP this should enforce your condition: it implies that for any two pairs of points "with the same slope", at least one point has value 0. There will be $O(N^3)$ such constraints, where $N = N_1 N_2$.