<p>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$.</p>

<p>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$.</p>

CC BY-SA 3.0
2011-06-01T17:08:46.897Z
This is what I was looking for. Thank you so much.
Baris
CC BY-SA 3.0
2011-06-02T00:16:32.527Z
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
CC BY-SA 3.0
2011-06-01T01:43:50.967Z
2011-06-02T00:13:35.723Z
2011-06-02T00:13:35.723Z
Sasho Nikolov
<p>I have the LP formulation at the link below for the following problem:</p>

<p><a href="http://www.cs.utsa.edu/~btas/lpformulation.png" rel="nofollow">my lp formulation</a></p>

<p>Minimize:</p>

<ul>
<li>$\sum_{i=1}^{N_1} \sum_{j=1}^{N_2} x_{ij}$</li>
</ul>

<p>Subject to:</p>

<ul>
<li>$\sum_{i=m}^{m+a-1} \sum_{j=n}^{n+b-1} x_{ij} \ge k$</li>
<li>$x_{ij} \in \{0,1\}$</li>
</ul>

<p>where</p>

<ul>
<li>$\forall m, 1 \le m \le N_1 - a + 1 \wedge$</li>
<li>$\forall n, 1 \le n \le N_2 - b + 1$</li>
</ul>

<p>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 &lt; N_1$ and $b &lt; 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.</p>

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

<p>Actually, this problem is a reduction from the problem, 
Hitting Set.</p>

<p>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.</p>

<p>Any ideas, suggestions?</p>

<p>Thanks, </p>

CC BY-SA 3.0
2011-06-01T01:38:16.740Z
is this a homework question? Also, the site supports LaTeX, why not just LaTeX the formulation instead of linking us?
Artem Kaznatcheev
CC BY-SA 3.0
2011-06-01T02:46:30.813Z
I am not sure I see what does this question has to with theoretical computer science ?
Mohammad Alaggan
CC BY-SA 3.0
2011-06-01T06:03:11.087Z
this is out of scope for being too localized.
Suresh Venkat
<ds.algorithms><linear-programming>
linear programming (is this doable?)
Baris
# linear programming (is this doable?)

(Asked by: username_0 on 2011-05-31)

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

[my lp formulation](http://www.cs.utsa.edu/~btas/lpformulation.png)

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,

**Tags:** ds.algorithms, linear-programming
> **Comments:**
> **username_1**: is this a homework question? Also, the site supports LaTeX, why not just LaTeX the formulation instead of linking us?  
> **username_2**: I am not sure I see what does this question has to with theoretical computer science ?  
> **username_3**: this is out of scope for being too localized.  

---

## 1 answers

### Answer by username_4 on 2011-06-01. Score: 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$.

> **Comments:**
> **username_0**: This is what I was looking for. Thank you so much.  
> **username_4**: 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$.  

---

