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?



closed as too localized by Mohammad Al-Turkistany, Suresh Venkat Jun 1 '11 at 6:03

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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.