Linearization of constraints in a ILP

Question

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$

Answer 1

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