# Writing a constraint of an integer programming in a linear form

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

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

## 2 Answers

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

• Thank you. This is a great answer. However, here $n$ is a large number introducing another set of binary variables makes computation costly. Is there any way to reduce the number of binary variables? Commented Apr 3, 2023 at 4:25
• I updated my answer just now. You don’t need $t_j$ or $y_j$. Commented Apr 3, 2023 at 4:26

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