3
$\begingroup$

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

$\endgroup$
1

2 Answers 2

7
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Red shoes
    Apr 3 at 4:25
  • 1
    $\begingroup$ I updated my answer just now. You don’t need $t_j$ or $y_j$. $\endgroup$
    – RobPratt
    Apr 3 at 4:26
2
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.