Linearizing a constraint containing a root square expression

1k Views Asked by At

We are working on a combinatorial optimization problem. In order to solve it using CPLEX, we need to linearize the non-linear constraint stated in the following.

Let $p_i, i \in I$ denotes a set of positive continuous decision variables. $y_i, i \in I$, $x_{ji}, j \in J, i \in I$ are two sets of binary decision variables. How to linearize the following constraint:$$p_i y_i - \sum_{j \in J}b_{j} x_{ji} \le \sqrt{\sum_{j \in J} x_{ji}^2 \sigma_j^2}, \quad\quad\forall i \in I$$

where $b_{j}$ and $\sigma_j$ are positive known parameters of the problem.

1

There are 1 best solutions below

2
On BEST ANSWER

Since you are using cplex, there is no need to linearize really, all you need is a second-order cone model.

Write as $$(p_i y_i - \sum_{j \in J}b_{j} x_{ji}) \le t,~t \leq \sqrt{\sum_{j \in J} x_{ji}^2 \sigma_j^2}$$ and square the nonlinear term (possible as the problematic term is non-negative, so there is no loss in generality to assume $t\geq 0$) $$t^2 \leq \sum_{j \in J} x_{ji}^2 \sigma_j^2$$ and use $x_{ji}^2 = x_{ji}$. From that, it follows that you have a convex quadratic constraint, i.e. second-order cone representable.