# Linearization of constraints in a ILP

I have been working on a Graph Theory problem for my thesis and got stuck about the linearization of some constraints. I am hiding everything, constraints, variables and so on, of my problem not needed for this StackExchange question.

Suppose we have in input a set of nodes $$V=\{1,\dots,n\}$$ for $$n\in \mathbb N,n\ge 4$$, a subset $$\widetilde V\subset V$$, a symmetrical matrix of costs $$s\in\mathcal M_n(\mathbb R)$$ and a boolean vector $$\hat{y}\in\{0,1\}^n$$.

My (partial) problem is:

$$\text{Min} \displaystyle \sum_{i\in V}\sum_{j\in V\setminus\{i\}}s_{ij}y_{ij}$$

$$s.t. \displaystyle\sum_{\substack{j \in V \backslash\widetilde{V}\\ i\neq j}} 2 y_{ij} + \displaystyle\sum_{\substack{j \in \widetilde{V}\\ i\neq j}} y_{ij} = 2(1 - \hat{y}_{i}) \quad \forall i \in V$$

$$\quad y_{ij}\le \hat y_{j}\quad \forall (i,j)\in V^2, i\neq j$$

$$y_{ij}\in \{0,1\},\quad \forall (i,j)\in V^2,i\neq j,\quad(*)$$

Currently the constraints are Integer and Linear. And the following example shows that using

$$y_{ij}\in [0,1],\quad \forall (i,j)\in V^2,i\neq j,\quad (**)$$

is not enough to make it linear. Indeed, suppose that $$V = \{1,2,3,4\}$$:

• $$s_{41} = 12$$
• $$s_{42} = 1$$
• $$s_{43} = 10$$
• $$\hat{y}=[1,1,1,0]$$
• $$1\notin \widetilde V$$ and $$2\in \widetilde V$$ as well as $$3\in \widetilde V$$

Using $$(*)\;\,$$ and focusing on node $$4$$ will give an optimal (partial) solution of $$y_{42} = y_{43} = 1 = 1 - y_{41}$$ of cost $$11$$.

Using $$(**)$$ and focusing on node $$4$$ will give an optimal (partial) solution of $$y_{41} = y_{42} = 0.5$$ and $$y_{43} = 0$$ of cost $$6.5$$ which is better than with $$(*)$$ and feasible for all constraints except integer constraints $$(*)$$.

I don't know how I should linearize such constraints? Thank you for your kind help :D

EDIT: thanks to @Kuifje's comments, I want the same problem but with linear decision variables instead of $$y_{ij}\in \{0,1\}$$. Using $$y_{ij}\in[0,1]$$ is not enough as shown in the 4 nodes example. I believe the linearization is possible because I have a polynomial algorithm solving the problem.

EDIT 2: I don't know if it is going to help:

The ILP you have above models a graph theory problem where, given a set of nodes $$V$$ and a subset $$\widetilde V$$. Suppose that $$\hat{y}_i$$ will be $$1$$ if and only if $$i$$ is selected. We will try to minimize, for all non selected hubs $$i$$, the minimum between

• the distance between $$i$$ and the closest selected hub in $$V\setminus{\widetilde V}$$
• and the sum the two distances between $$i$$ and the two closest selected hubs in $$\widetilde V$$
• I am not sure I follow : you want to get rid of the integer variables ? What makes you think this is possible ? If the problem is NP-hard, you will not be able to formulate it as a pure linear problem (or else you will become very famous). Oct 12 '21 at 14:29
• @Kuifje, yes, I would like to know how I could get rid of the integer constraints and have linear instead. I believe it is possible because I have a polynomial algorithm solving the problem. If it is not possible, there should be a mistake in my polynomial algorithm (I am not going to prove anything on P=NP haha) but I don't think it is the case
– JKHA
Oct 12 '21 at 14:32
• Ok, I understand. In this case, I think you will get better answers if you show your full problem in detail. There may be a linear formulation (assuming your polynomial algorithm is correct), but it may be quite different than yours. Oct 12 '21 at 14:34
• @Kuifje, I think what I have shown in the post is enough, I have spent time to be sure it is the case, so that it is clearer for you helping me. This is because my entire problem is Minimize A + B s.t. (1) and (2) Where B and (2) are in the post and A and (1) are hidden but can be optimized independently of B and (2) :)
– JKHA
Oct 12 '21 at 14:36
• @Kuifje, oh, you meant, the graph theory problem?
– JKHA
Oct 12 '21 at 14:42

Try adding valid constraints $$y_{i,j} \le \sum_{(i,k): k \in \tilde{V} \setminus \{j\}} y_{i,k} \quad\text{for (i,j) such that \hat{y}_i = 0 and j \in \tilde{V}\setminus\{i\}}$$ that enforce the logical implications $$(y_{i,j} \land \lnot\hat{y}_i \land [j \in \tilde{V} \setminus\{i\}]) \implies \bigvee_{(i,k): k \in \tilde{V} \setminus \{j\}} y_{i,k}$$