# linear programming (is this doable?) [closed]

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,

• is this a homework question? Also, the site supports LaTeX, why not just LaTeX the formulation instead of linking us? – Artem Kaznatcheev Jun 1 '11 at 1:38
• I am not sure I see what does this question has to with theoretical computer science ? – M. Alaggan Jun 1 '11 at 2:46
• this is out of scope for being too localized. – Suresh Venkat Jun 1 '11 at 6:03

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$.
• corrected the mistake, the number of new constraints is $O(N_1^3 N_2^3)$ as you have one constraint for each set of integers $i, j, k, l, u, v$. – Sasho Nikolov Jun 2 '11 at 0:16