How to find absolute of a linear expression?

944 views
Skip to first unread message

Suman L

unread,
Jul 12, 2016, 1:02:27 AM7/12/16
to Gurobi Optimization

I am currently working on a optimization problem on GUROBI.All my variables are of binary type.I have a variable y which is equal to the absolute of difference of two binary decision variables.However,when i tried to use the abs() function,i get this output.


TypeError: bad operand type for abs(): 'gurobipy.LinExpr'
 

Therefore,i am now squaring the difference (since difference is always -1,0 or 1). But this causes higher optimization time(quadratic expressions after squaring). Is there any alternative to this?


Also,there is a case(not binary variables) where the difference of two variables may not be -1,0 or 1.How do i take the absolute in this case?

Kostja Siefen

unread,
Jul 12, 2016, 6:32:25 AM7/12/16
to Gurobi Optimization
Hi Suman,

The absolute value is a non-linear function. However, abs(x) is a piecewise-linear function and you can use a linearization technique. 
Let x be your decision variable and z = abs(x). You can use two separate variables p, n >= 0 and use an indicator variable y to ensure that only p or n can have a value other than zero at any time.

1) Add variables p, n >= 0
2) Add binary variable y
3) Add constraint x = p - n.
4) Add constraints p <= M*y and n <= M * (1-y) with suitable values for M
5) Add constraint z = p + n

Then you have z = abs(x). Make sure that you set proper bounds for x in your model (i.e. allow negative values). 

Here is another way using SOS1 sets:

1) Add variables p, n >= 0
2) Create SOS set {p,n} so that in any feasible solution only one of the two variables may be positive non-zero
3) Add constraint x = p - n.
4) Add constraint z = p + n

This also gives you z = abs(x).

Kostja

Suman L

unread,
Jul 21, 2016, 1:31:55 AM7/21/16
to Gurobi Optimization

Hi,

Will this method work even if x is already an expression whose absolute was calculated using the above method?

Thank you
Reply all
Reply to author
Forward
0 new messages