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

my lp formulation


  • $\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\}$


  • $\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?


  • 4
    $\begingroup$ is this a homework question? Also, the site supports LaTeX, why not just LaTeX the formulation instead of linking us? $\endgroup$ – Artem Kaznatcheev Jun 1 '11 at 1:38
  • 1
    $\begingroup$ I am not sure I see what does this question has to with theoretical computer science ? $\endgroup$ – M. Alaggan Jun 1 '11 at 2:46
  • 1
    $\begingroup$ this is out of scope for being too localized. $\endgroup$ – 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$.

  • $\begingroup$ This is what I was looking for. Thank you so much. $\endgroup$ – Baris Jun 1 '11 at 17:08
  • $\begingroup$ 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$. $\endgroup$ – Sasho Nikolov Jun 2 '11 at 0:16

Not the answer you're looking for? Browse other questions tagged or ask your own question.