How to use LinExpr to code the entropy function in Gurobi?
Answered
Hi,
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(1-pcd)
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
-
Official comment
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?. -
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 -
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 -
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 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 -
Hi Daniel,
Its more than clear, thanks a lot for such a nice explanation.
Laaziz
0
Post is closed for comments.
Comments
6 comments