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\}$
Best Answer
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.