How to use LinExpr to code the entropy function in Gurobi?
AnsweredHi,
My mathematical model includes optimizing a cost function that makes use of entropy formula which uses the logarithmic function.
I'd like to know if Gurobi is able to optimize this kind of particular functions ?
If no is there a way to deal with it ?
In my mathematical model my objective function looks like this :
Hc= pcd*log2 (pcd) + (1 pcd)*log2(1pcd)
where pcd = Sum_over_i(Sigma[c, i])/ Card (V)) and Sigma[c, i] is a binary decision variable.
Could anyone help me with this ?
Thanks

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 piecewise linear representation of the logarithmic function.
In your case the domain of the logarithmic function is [epsilon,1epsilon] 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) + (1xi)*log_2(1xi).
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 
Probably.... by directly evaluating the function x*log_2(x)+(1x)*log_2(1x) you can consider as your domain [0:1]
0 
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 
Hi Laaziz,
Note that to build a PWL approximation of your nonlinear 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 nonlinear, but whose domain is [0:1], to build an approximation of this constraint you may decide to build a piecewise 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 
Hi Daniel,
Its more than clear, thanks a lot for such a nice explanation.
Laaziz
0
Please sign in to leave a comment.
Comments
5 comments