0
$\begingroup$

I currently have defined a pure integer linear program that works well, but the number of constraints for a given input runs out of time and/or memory. Let me introduce the problem.

I have an adjacent matrix $C$ of size $N \times N$, where each component $c_{ij} = 1$ if locations $i$ and $j$ can be connected and $0$ otherwise, and where $0 \leq i,j \leq N$. So let's suppose that I have a matrix with $N = 3$ like:

\begin{bmatrix} 1&1&1\\1&1&0\\1&0&1 \end{bmatrix}

This means that:

Location 1 can be connected with location 1 (itself), 2 and 3. Location 2 can be connected with location 1 and 2 (itself), but not 3. Location 3 can be connected with location 1 and 3 (itself), but not 2.

Each of my ILP variables are denoted by $x_{ij}$. So $x_{ij} = 1$ if locations $i,j$ are connected and 0 otherwise. My objective is to have up to K locations connected, respecting the adjacent matrix.

$x_{ii} = 1$ denotes that location $i$ is a root. My linear program looks like this:

f: min $\sum_{i\in N} x_{ii}$

such that:

1) $\sum_{i}x_{ii} \leq K$ (up to K roots)

2) $\forall i \sum_{j} x_{ij} = 1$ (a location can only belongs to a root).

3) $\forall i, x_{ii} + \sum_{j} c_{ij}x_{ij}x_{jj} = 1$. it denotes whether a location is a root or a leaf.

4) $\forall i,j,w (1 - x_{iw}) + (1 - x_{jw}) + c_{ij} \geq 1$. This is the problematic constraints. It means to denote transitivity. If $c_{ij} = 1$, then we have to check if $i$ and $j$ belongs to the same root $w$. It checks if locations $i,w$ and $jw$ can be connected if $i,j$ can be connected as well.

This means that I cannot have a connection {1,2,3} because {2,3} or {3,2} cannot be connected. So, although 1 can be connected with 2 and 3, since 2 and 3 are not compatibles, I cannot connect those locations.

A possible solution for K = 2 is {1,2}, {3} or {1,3}, {2}. For K = 1 there is not feasible solution.

The problem is that if I have a matrix C of for example size N = 100, then constraint 4) is 100*100*100 = 1000000 constraints. For matrices of 300/400, then it is intractable.

All variables must take values between 0 and 1.

Any idea about how can I check transitivity without having this huge amount of constraints? The problem is $\forall i,j,w$.

Thank you very much. Any idea will be really appreciated.

EDIT: Linear version of the quadratic program:

1) $\forall{i} \in S, x_{ii} + \sum_{j\in S-\{i\}}c_{ij}y_{ij} = 1 $

2) $\forall{i,j,k} \in S, (1-x_{ik}) + (1-x_{jk}) + c_{ij} \geq 1 $

3) $ \forall{i }\in S, \sum_{j \in S} x_{ij} = 1 $

4) $ \forall{i \in S}, \sum_{i\in S} x_{ii} \leq k $

5) $ \forall{i,j \in S}, y_{ij} \geq x_{ij} + x_{jj} - 1 $

6) $ \forall{i,j \in S}, y_{ij} \leq x_{ij}$

7) $ \forall{i,j \in S}, y_{ij} \leq x_{jj}$

8) $ \forall{i,j \in S}, x_{ij} \in \{0,1\}$

9) $ \forall{i,j \in S}, y_{ij} \in \{0,1\}$

$\endgroup$
  • $\begingroup$ In other words, you want to partition the nodes of a graph into a minimum number of cliques? $\endgroup$ – Rob Pratt Nov 7 '19 at 13:26
0
$\begingroup$

Constraint 3 is only an expression with no equality or inequality. It sounds like your graph is undirected, in which case you need to define variables $x_{i,j}$ only for $i \le j$ with $c_{i,j}=1$ instead of all $(i,j)\in N \times N$. There are then 3 transitivity constraints for each triple $i<j<k$: \begin{align} x_{i,j} + x_{i,k} -1&\le x_{j,k} \\ x_{i,j} + x_{j,k} -1&\le x_{i,k} \\ x_{i,k} + x_{j,k} -1&\le x_{i,j} \end{align}

Another approach is to recognize that this problem is minimum node clique cover, which is equivalent to chromatic number of the graph complement, as discussed in this previous post.

$\endgroup$
  • $\begingroup$ Thank you for your answer. I am sorry. Constraint 3 is an equality constraint. I already have edited it. $\endgroup$ – user3018940 Nov 7 '19 at 23:34
  • $\begingroup$ OK, but the edited constraint 3 is not linear. $\endgroup$ – Rob Pratt Nov 8 '19 at 0:03
  • $\begingroup$ That's true. I already linearised the constraint. But still the problem is constraint 4), the transitivity constraint. (Constraint 2) in the ILP version) $\endgroup$ – user3018940 Nov 8 '19 at 0:06
  • $\begingroup$ So, if I have N = 500. Then I have 500^3 transitivity constraints (125000000 constraints). Which is intractable $\endgroup$ – user3018940 Nov 8 '19 at 0:13
  • $\begingroup$ Can you please clarify whether you are trying to partition the nodes into a minimum number of cliques? $\endgroup$ – Rob Pratt Nov 8 '19 at 0:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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