# Reduce integer linear program constraints

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

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

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: \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}