Skip to main content

Square roots

Answered
Bereket YILMA
  • Edited
Gurobi-versary
First Comment
First Question
Hi all, 
 
I am trying to solve the following objective function which maximizes the square root of the sum of scores of items.
 
sqrt( \sum_{a=1}^{R}  x_{a} * Score (x_a) ) 
 
x_{a}  is a binary variable and Score(x_a) is an intiger value
 
I discovered that Gurobi doesn’t support square roots. Any workaround to solve this with Gurobi?
 
Thanks!

Related to

1

Comments

7 comments

Date Votes
  • Official comment
    Simranjit Kaur
    Gurobi Staff Gurobi Staff
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
  • Jaromił Najman
    Gurobi Staff Gurobi Staff
    • Edited

    Hi,

    You can drop the \(\sqrt{\cdot}\) in your objective function because it is a concave monotonically increasing function. This means that \(\sqrt{a} \leq \sqrt{b}\) for \(a \leq b\). Once you have the optimal objective value, you can compute the \(\sqrt{\cdot}\) of it manually.

    Note that this is only ok, since it occurs in your objective only. It is not that straight forward if you have a \(\sqrt{\cdot}\) in one of your constraints.

    Best regards,
    Jaromił

    1
  • Bereket YILMA
    • Edited
    Gurobi-versary
    First Comment
    First Question

    Thanks for your answer  Jaromił!

    That certainly should work. Nevertheless, eventually, I am trying to solve a slightly complex case where dropping the  √ isn't going to do what I want.

    I have K groups and I want to maximise the TOTAL SUM of the square root of the sum of scores of items for each group. (i.e )

    \(\sum_{I=1}^{K} \sqrt{ \sum_{a=1}^{R}  x_{a} ^{ i } * Score (x_a) } \)

    I don’t think dropping the √ will give the desired result in such cases.

    For example  √ 2 +√ 1 + √ 1 > √ 4 + √ 0 + √ 0);

    But    2 + 1 + 1  = 4

    I was wondering if there is a way to model such objectives with √ in Gurobi?

     

    Thanks!

    1
  • Jaromił Najman
    Gurobi Staff Gurobi Staff
    • Edited

    Hi Bereket,

    You are right, in this case you can't simply drop the \(\sqrt{\cdot}\). You could try the addGenConstrPow() function with \(a=0.5\) to model a \(\sqrt{\cdot}\). For that you will have to introduce auxiliary variables and equality constraints\( w_k= \sum_{a=1}^{R} x_{a} ^{ i } * Score (x_a) \) and then use the auxiliary variables in your objective as \(\sum_{k=1}^{K}  \sqrt{w_k}\).


    Best regards,
    Jaromił

    1
  • Bereket YILMA
    Gurobi-versary
    First Comment
    First Question

    Thanks, Jaromił !

    It works with the addGenConstrPow() method.

    Best regards,

    Bereket.

    0
  • Nadi Serhan Aydin
    Gurobi-versary
    Conversationalist
    First Question

    I think there is a typo at the bottom of this page: addGenConstrPow(). The example usage should not read "LogA".

    0
  • Riley Clement
    Gurobi Staff Gurobi Staff

    Hi Nadi,

    This is true.  Please note that link is for 9.0 documentation, and the typo was fixed in 9.5 documentation: addGenConstrPow() but thank you for highlighting it.

    Given we maintain documentation for several versions on our website it is always useful to check in the URL to verify which version you are accessing.

    - Riley

    0

Post is closed for comments.

Didn't find what you were looking for?

New post