Writing a constraint of an integer programming in a linear form

Question

I modeled an optimization problem in an integer programming format. The main constraint I came up with is now nonconvex. I would like to see if there is another equivalent formulation in which the constraints are convex or simple enough to be solved.

\begin{equation} \begin{aligned} \min_{x,t} \quad & \sum_{i=1}^{n}{c_i x_i}\\ \textrm{s.t.} \quad & \sum_{j=1}^{n}{t_j \big( \text{dist} (v_i , v_j) - T x_j \big)} \leq 0 ,~ i=1,\dots,n \\ & t_1 + t_2 +\dots + t_n = 1\\ & t_i , x_i \in \{ 0 , 1 \} \\ \end{aligned} \end{equation}

Note that $\text{dist} (v_i , v_j) $ and $T$ are positive constants. $x_i = 1$ if the node $v_i$ is selected, $x_i = 0$ otherwise. $t_i$s are auxiliary variables. The constraints have been written in a way that for each node $v_i$, there exists a selected node $v_j$ such that $\text{dist} (v_i , v_j) \leq T.$

Answer 1

Introduce a binary decision variable $y_j$ to represent the product $t_j x_j$. The usual linearization would use three linear constraints to enforce this relationship. But here, because $T\ge 0$, we need only enforce $y_j \le t_j x_j$, so two constraints suffice: $y_j \le t_j$ and $y_j \le x_j$. Finally, replace your first constraint with $$\sum_{j=1}^n \left(t_j \text{dist}(v_i,v_j)−T y_j\right)\le0$$

---

A simpler way to enforce your desired restriction is to let $$J_i=\{j\in\{1,\dots,n\}: \text{dist}(v_i,v_j)\le T\}$$ and impose set covering constraints $$\sum_{j\in J_i} x_j \ge 1 \quad \text{for all $i$}$$

Answer 2

You can implement - for each node $v_i$, there exists a node $v_j$ such that $\text{dist} (v_i , v_j) \leq T.$ like below
$x_i \le \sum_{j \neq i} x_j \le x_i + M(1-x_i)$
$\sum_{j \neq i}x_j dist(v_i,v_j) \le T +M(1-x_i)$
Or
$\sum_{j \neq i}x_j dist(v_i,v_j) \le T(2-x_i)$: simply replaced $M$ with $T$