2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I edited my question. $\endgroup$ – Farouk Hammami Apr 26 '19 at 16:30
  • $\begingroup$ But what have you tried and where are you stuck? $\endgroup$ – Saad Apr 26 '19 at 16:31
  • $\begingroup$ Well, i have tried to square the expression wich gives: $(p_i y_i)^2 - 2 p_i y_i \sum_{j \in J}b_{j} x_{ji} + (\sum_{j \in J}b_{j} x_{ji})^2 \le \sum_{j \in J} x_{ji} \sigma_j^2, \quad\quad\forall i \in I$ and here i'm stuck $\endgroup$ – Farouk Hammami Apr 26 '19 at 16:40
  • $\begingroup$ Squaring inequalities can be tricky. It is not an equivalence relation. For example left hand side could be negative, but a square can never be. $\endgroup$ – mathreadler Apr 26 '19 at 18:52
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Are you sure we can't accidentally disqualify valid solutions by doing this? LHS could be negative and after squaring it becomes positive for sure, while RHS is always positive. $\endgroup$ – mathreadler Apr 26 '19 at 18:56
  • $\begingroup$ True, incorrect transformation, will adjust, think is salvageable $\endgroup$ – Johan Löfberg Apr 26 '19 at 19:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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