5
$\begingroup$

I am trying to linearize the constraint set (2) in the following simplified program. The parameters: $A,C,D,T\in\mathbb{R}^+$. The set $\mathcal{J}$ is polynomially-sized.

\begin{alignat}2\min &\quad \sum_{j\in\mathcal{J}}\left(Cb_j+D\lambda_j\right)\tag1\\ \text{s.t.}&\quad b_j\geq T\lambda_j+A\sqrt{T\lambda_j}\qquad j\in\mathcal{J}\tag2\\ &\quad \lambda_j,b_j\in \mathbb{R}^+.\end{alignat}

Seeing this post and the McCormick Envelope, I tried to implement it but did not seem to work as expected. Can you please help me debug where I am doing wrong? First, I re-write (2) as $b_j\geq T\lambda_j+Ae_j$, where $e_j=\sqrt{T\lambda_j}$. Then, squaring both sides, I get $f_j=T\lambda_j$, where $f_j=e_j^2$. Under these conditions and assuming $-M_j\leq e_j \leq M_j$, I replace (2) with the following set of constraints.

\begin{alignat}2 &\quad b_j\geq T\lambda_j+Ae_j\qquad j\in\mathcal{J}\tag3\\ &\quad M_je_j\geq f_j\qquad j\in\mathcal{J}\tag4\\ &\quad f_j\geq T\lambda_j\qquad j\in\mathcal{J}\tag5\\ &\quad M_j^2\geq f_j\qquad j\in\mathcal{J}\tag6\\ &\quad f_j\geq 2M_je_j-M_j^2\qquad j\in\mathcal{J}\tag7\\ &\quad e_j\leq M_j\qquad j\in\mathcal{J}\tag8\\ \end{alignat}

Although I defined $M_j$, I cannot define a strict big number for a specific index $j\in\mathcal{J}$. So, I assume $M=M_j$. Moreover, I use Gurobi to solve this problem and I am open to a quadratic constraint. Indeed, I also tried defining $e_j e_j \geq T\lambda_j$ in Gurobi and it also did not work. I assume I made a mistake in that definition.

$\endgroup$
5
  • $\begingroup$ First, why have you relaxed the equality $f_j = T\lambda_j$ to an inequality? And exactly what do you mean with "did not seem to work as expected"? $\endgroup$ Commented Jun 30, 2020 at 6:43
  • $\begingroup$ Did you check the mentioned post? I tried to follow the McCormick envelopes method given in the answers. $\endgroup$ Commented Jun 30, 2020 at 11:57
  • $\begingroup$ With “did not seem to work expected” I mean $b_j$, $e_j$, and $f_j$ do not get expected values. Specifically, $e_j =\sqrt{f_j}$ does not hold. $\endgroup$ Commented Jun 30, 2020 at 13:19
  • $\begingroup$ The McCormick envelope provides only a relaxation, so I don't think you should expect the original constraints to hold. $\endgroup$ Commented Jun 30, 2020 at 15:29
  • $\begingroup$ Oops! I thought It was going to hold the original. Is there any alternative solution? $\endgroup$ Commented Jun 30, 2020 at 15:39

1 Answer 1

3
$\begingroup$

Define $\mu_i = \sqrt{\lambda_i}$ and the problem is a convex quadratically constrained problem in $(b,\mu)$

$\endgroup$
6
  • $\begingroup$ Johan, do you know if Gurobi supports this? If yes, can you please provide a link to an example? Thanks! $\endgroup$ Commented Jun 30, 2020 at 18:04
  • 2
    $\begingroup$ Convex quadratic constraint? Of course. So does Mosek and Cplex. If you use a modelling language (such as YALMIP in MATLAB, disclaimer: developed by me) you simply write b>=T*mu.^2 + Asqrt(T)*mu or similar and you are done $\endgroup$ Commented Jun 30, 2020 at 18:13
  • $\begingroup$ I guess we do not need a lot of linearization procedures after all. I was using Gurobi 8 and just realized that Gurobi 9.0 does not mind about PSD anymore. $\endgroup$ Commented Jun 30, 2020 at 21:13
  • $\begingroup$ If you can solve it as a convex problem, you should do so. Keeping the nonconvex model can cause it to go from seconds to days in terms of solution time $\endgroup$ Commented Jul 1, 2020 at 6:06
  • $\begingroup$ Well, I tried the McCormick envelope and it doesn’t provide the exact solution. So, I had to go with MIQCP formulation and as you said, the solution time for some instances skyrocketed. $\endgroup$ Commented Jul 2, 2020 at 2:19

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.