Skip to main content

How to use LinExpr to code the entropy function in Gurobi?

Answered

Comments

5 comments

  • Daniel Espinoza

    Hi Laaziz,

    Short answer... no, as of 8.1.1, Gurobi is not able to directly deal with logarithmic functions of variables, but there is a simple way to approximate that through a piece-wise linear representation of the logarithmic function.

    In your case the domain of the logarithmic function is [epsilon,1-epsilon] for some positive epsilon, probabli epsilon=1/Card(V).

    then you decide in which points to evaluate the function (x0,....,xk) and compute its image (y0,....,yk),

    where yi=xi * log_2(xi) + (1-xi)*log_2(1-xi).

    and then you say:

    pdc = sum(lambda_i * xi: i=1...k)

    1  = sum(lambda_i)

    {lambda_i}_{i=0}^k is an SOS2 set (asuming xi<x[i+1])

    Hc = sum(lambda_i * yi)

    The quality of the approximation depends both on how you select xi and how many points there are.

    Hope this helps,

    Daniel

     

    2
  • Daniel Espinoza

    Hi Laaziz,

    Note that to build a PWL approximation of your non-linear function, you do not evaluate the model's variables, let me ilustrate this with a simple example:

    Let say I have a constraint of the form:

    y = f(x)

    where f(x) is non-linear, but whose domain is [0:1], to build an approximation of this constraint you may decide to build a piece-wise linear function at points x={0.00, 0,25, 0,50, 0.75, 1.00}, to do that, you would introduce one extra variable for each evaluation point, i.e.:

    z_{0.00}, z_{0.25}, z_{0.50}, z_{0.75} and z_{1.00}

    with the following constraints:

    0 <= z_k <= 1

    sum(z_k:k) = 1

    x = 0.00 * z_{0.00} + 0.25 * z_{0.25} + 0.50 * z_{0.50} + 0.75 * z_{0.75} + 1.0 * z_{1.0}

    y = f(0.00) * z_{0.00} + f(0.25) * z_{0.25} + f(0.50) * z_{0.50} + f(0.75) * z_{0.75} + f(1.00) * z_{1.00}

    SOS2(z_{0.00},z{0.25},z{0.50},z_{0.75},z_{1.00})

     

    Of course, the more "breaking points" the closer your approximation to the original problem (but the model get's larger and might be slower to solve).

    I hope this is clearer,

    Daniel

    1
  • Daniel Espinoza

    Probably.... by directly evaluating the function x*log_2(x)+(1-x)*log_2(1-x) you can consider as your domain [0:1]

    0
  • lahlou Laaziz
    Gurobi-versary
    First Comment
    First Question

    Hi Daniel,

    Thanks a lot for your answer. Is that correct to put Sigma[c, i] which is a decision variable into the log funcrion knowing that the log function expect a numerical value rather than a decision variable which is not known in advance ? 

    Regards,

    Laaziz

    0
  • lahlou Laaziz
    Gurobi-versary
    First Comment
    First Question

    Hi Daniel, 

    Its more than clear, thanks a lot for such a nice explanation.

    Laaziz

    0

Please sign in to leave a comment.