Exponential constraint

[Dinna]

Hi,

Is it possible to have exponential constraints such as a*exp(b*x) in gurobi with matlab interface? The decision variable is x. Thanks.

Regards,

Dinna

[Tobias Achterberg]

No, unfortunately not. You would need to model it with a piece-wise linear
approximation.

Tobias

[Dinna]

Hi Tobias,

Could you show me how to do it?

Regards,

Dinna

[Tobias Achterberg]

This depends a bit on how the constraint is used.

Assume you want to model the constraint

y = 2^x

with continuous non-negative variables x and y, 0 <= x,y <= 100. Then you could
do the following:

- x + 0.0 z0 + 0.1 z1 + 0.2 z2 + 0.3 z3 + ... + 10.0 z100 = 0
- y + 2^0.0 z0 + 2^0.1 z1 + 2^0.2 z2 + 2^0.3 z3 + ... + 2^10.0 z100 = 0
z0 + z1 + z2 + z3 + ... + z100 = 1
SOS2: z0, z1, z2, z3, ..., z100
0 <= zj <= 100 for all j = 0,...,100

Note that the 2^t values are just regular constants (which you would express as
regular floating point values in your code), so for example 2^0.0 = 1, and 2^0.1
= 1.0717734625. Of course, you would not add the "0.0 z0" coefficient to the x
constraint; I just added it to make it more clear what happens.

The trick is the SOS2 constraint, which makes sure that at most two of the zj
variables are non-zero, and if there are two non-zero zj, then these two are
adjacent (i.e., some zj and z(j+1)).

For example, if z2 = 0.3 and z3 = 0.7 (which is valid, because the sum of zj is
1, at most two zj are non-zero, and the two are adjacent), then x = 0.2*0.3 +
0.3*0.7 = 0.27. Consequently, y = 2^0.2*0.3 + 2^0.3*0.7 = 1.2064, which is
slightly larger than the correct value 2^0.27 = 1.2058. This is because the
above constraint system only yields a piece-wise linear approximation and thus
is not fully correct between the break-points. The more break-points you add,
the better the approximation becomes, but the harder the model will be to solve.


Tobias

[Dinna]

That works perfectly! Thanks Tobias.

[Dinna]

Hi Tobias. I have another question. If this is a constraint:

 - y + (2^0.0) z0 + (2^0.1) z1 + (2^0.2) z2 + (2^0.3) z3 + ... + (2^10.0) z100 = 0 

Based on your example, 0.0; 0.1; 0.2;...10 are weight of z, arent't they?

And when we define SOS2 in gurobi with matlab interface, we also define the weight like this:

model.sos(1).type   = 2;

model.sos(1).index  = [1 2 3 4 ... 100];

model.sos(1).weight = [0.1 0.2 0.3 0.4 .... 10];

I don't know how SOS2 works exactly, but I think there is a redundancy since the weight is written twice: in the constraint and in SOS2 definition. 

Did I miss something here?

Regards,

Dinna

On Monday, 30 May 2016 11:33:38 UTC+2, Tobias Achterberg wrote:

[Tobias Achterberg]

Hi Dinna,

the SOS weights are traditionally used to influence the branching strategy for
SOS constraints. Namely, when an SOS constraint is violated by the current LP
solution (for the case of SOS2 this means that there are two non-adjacent
variables with non-zero LP value), a branching split is performed that
partitions the variables of the SOS into two subsets and asks in the left child
node in the search tree to fix one part of the variables to zero, and in the
right child to fix the other part to zero. The SOS weights were a way to
influence how this partition is generated.

But note that Gurobi does not use the weights in this way. Gurobi always uses
its own internal procedure to split the SOS variables into two sets. The weights
are only used to specify the order of the variables. Thus, weights 0.1, 0.2,
..., 10.0 are really equivalent to 1, 2, ..., 100, or 1, 7, 15, ..., 8437 or
whatever numbers you want, as long as they are increasing. On the other hand, if
you specify weights like 3, 1, 2, 5, 4 it would mean that the variables are
reordered according to their weights. For SOS1 this is not important (SOS1
requires that at most one of the variables is non-zero, so the concept of
adjacency is not present), but for SOS2 the order is important.

So, in short, those weights are somewhat old-fashioned and a bit of an overkill
for the Gurobi API. Thus, setting the weights to the same values as the
breakpoints of the x coordinate is exactly what you want to do.


Best regards,

Tobias

[Dinna]

Thanks Tobias! That's very helpful.

[Saeed Poormoaied]

Is it possible to have exponential constraints such as a*exp(b*x) in gurobi with matlab interface?

Is it possible for C++ interface? Should we always use piece-wise linear approximation in any interface?

[Tobias Achterberg]

You need to do a PWL approximation in all interfaces, because the exponential
function is not natively supported by Gurobi.


Tobias

[saeed Poormoaied]

thank you very much

--

---
You received this message because you are subscribed to a topic in the Google Groups "Gurobi Optimization" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/gurobi/HhPF7Yvqq3s/unsubscribe.
To unsubscribe from this group and all its topics, send an email to gurobi+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[王以萱]

Hi Tobias ,

I have continuous negative x in my model,

and my objective function is to maximize (1/(1+exp(x))

Is it possible for Gurobi +python? Do you have any advice?

Regards,

Hsuan

[Tobias Achterberg]

If this is the only contribution to the objective function (i.e., there are no objective
coefficients for other variables), then "max 1/(1+exp(x))" is equivalent to "min x". But I
guess you have other objective coefficients, so this transformation won't help.

Gurobi does not support exp(), log(), sin(), cos() or other general non-linear functions.
But you can approximate this using a piece-wise linear objective. Depending on how good
the approximation should be, you select a number of break-points x1,...,xk and define your
PWL objective using the points (xi, f(xi)) for i=1,...,k. Please see

http://www.gurobi.com/documentation/8.0/refman/py_model_setpwlobj.html

for more details.

Regards,

Tobias

[王以萱]

okay, thank you very much!

--

--- You received this message because you are subscribed to the Google Groups "Gurobi Optimization" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+unsubscribe@googlegroups.com.

[Martine R]

Hi Tobias,

What is the best way to add the breakpoints of the piecewise linear approximation stepwise. So ather than choosing a number of breakpoints and evenly spacing these point on the range for which the function needs to be approximated, I want to add a new breakpoint at the previously obtained solution point. I looked in to the documentation and I think this could be possible with callback function and lazy constraints? Could you help me out on how to do this? Or do you have a better suggestion?

Thank you!

Martine Ruigrok

Op maandag 30 mei 2016 11:33:38 UTC+2 schreef Tobias Achterberg:

[Tobias Achterberg]

This depends on whether your function is convex or not.

In the convex case, you can easily use the callback to produce lazy constraints, which
should be tangents of your non-linear function at the current LP solution.

In the non-convex case this is not so easy, because a tangent at the current LP solution
might cut off feasible points somewhere else. There, you would need to refine your
piecewise linear function, but this means to also add new variables to model the
additional breakpoints. Adding new variables during the solving process is not possible
with Gurobi. You would need to exit the solving process, modify the model, and start the
solving process from scratch.

Hence, I think the best solution is to use a more fine-grained relaxation at areas of the
solution space where you think feasible and optimal solutions could be. Then, you solve
the model as a MIP. Afterwards, you check the solution (and maybe other solutions from the
solution pool as well) whether the violation to your non-linear function is too large. If
so, you refine the breakpoints of the corresponding piecewise linear function and solve
the model again.

Best regards,

Tobias

[Martine Ruigrok]

Hi Tobias,

Thank you for your helpful reply! The function I want to approximate is the exponential function. This is is convex however this is not considered a convex program since i'm maximizing rather than minimizing. So I am using extra binary variables for each breakpoint to make sure the MILP chooses two weights of breakpoints next to each other.

So in this case, do you think the first method using the tangent is possible? And if so could you help me with how to use the callback function to produce lazy constraints?

Thank you!

Martine

Tobias

--

--- You received this message because you are subscribed to a topic in the Google Groups "Gurobi Optimization" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/gurobi/HhPF7Yvqq3s/unsubscribe.
To unsubscribe from this group and all its topics, send an email to gurobi+unsubscribe@googlegroups.com.

[Tobias Achterberg]

No, this is unfortunately not possible with lazy constraints and callbacks. The reason is
that for non-convex functions the tangent is not globally valid.

Take the convex case as an example: you want to minimize exp(x). Of course, if you only
want to minimize exp(x) you can just minimize x instead. So, we assume that there are
other (say, linear) parts of the objective function that depend directly or indirectly on
x, and we cannot get rid of the exp function.

You would model this with an auxiliary variable z that should denote the objective
function contribution of exp(x). Hence, you write

min z
s.t. z >= exp(x)

and then model the constraint "z >= exp(x)" with a piece-wise linear approximation. For
example, you could start with

min z
s.t. z >= 0
z >= x+1

which is a PWL with two pieces. But note that each linear constraint (z >= 0 and z >= x+1)
is globally valid, so we do not need any SOS2 formulation or the like.

Now, in the absence of other constraints and variables, the LP solution in this case is
(x,z) = (-1,0). Then you would generate the tangent at x=-1, which is

z >= exp(-1)*x + 2*exp(-1).

Again, this is globally valid. Those tangents can be generated on the fly in the callback
as lazy constraints.

But if you deal with the non-convex situation, this is no longer possible. In your case
you have

max z
s.t. z <= exp(x)

So, you need to deal with the upper envelope of exp(x). The piece-wise linear function to
use is then (of course) non-convex, so it requires auxiliary variables and usually an SOS2
constraint (or some binary variables). If you want to refine the relaxation, this requires
to introduce additional break-points, which means to add more variables to the model and
to modify existing constraints. Adding variables and modifying existing constraints is not
possible during the solving process in Gurobi.

What you *can* do is to solve the model with some piece-wise linear approximation, either
to optimality or until you found some reasonably good solution, and then adjust the
piece-wise linear relaxation so that it becomes tighter at the optimal or best solution
you found. Then, solve this refined model again and repeat.


Best regards,

Tobias