Solved

# Linearizing a constraint

• 2 replies
• 409 views

Userlevel 1 +3
• Enthusiast
• 9 replies

Dear staff,

I would like to receive your help with linearizing the following constraint.

Given the indexes i, j, c, a

I have the following variables and parameters:

x (i,j,a) continuous variable

y (i,j,a) continuous variable

R (i,j,c,a) binary variable

A (i,j) parameter

B (c) parameter

The constraint that I need to write is the following:

y(i,j,a) = (x(i,j,a) / A(i,j)) * (1 - sum((c,a1)|ord(a1) <= ord(a), R(i,j,c,a1))) + sum((c,a1)|ord(a1) <= ord(a), (x(i,j,a) / B(c)) * R(i,j,c,a1)) forall i, j, a

I am struggling in particular with the linearization of the second part:

sum((c,a1)|ord(a1) <= ord(a), (x(i,j,a) / B(c)) * R(i,j,c,a1))

Please note that there are already other constraints imposing that sum((c,a), R(i,j,c,a)) <= 1 forall i, j, therefore the summation of sum((c,a1)|ord(a1) <= ord(a), R(i,j,c,a1)) is always either 0 or 1.

Thank you,

Kind regards,

icon

Best answer by mohansx 1 November 2021, 22:22

View original

### 2 replies

Userlevel 5 +5

@Chibo have you looked at Section 7.7 Elimination of products of variables in the AIMMS optimization modelling guide ? It contains an example on how to formulate products of continuous variables and binary variables (in your case, x(i, j, a) and R(i, j, c, a)).

Consider lb(i, j, a) and ub(i, j, a) to be the lower and upper bounds of variable x(i, j, a). So,

lb(i, j, a) <= x(i, j, a) <= ub(i, j, a) forall (i, j, a)

The binary variable is R(i, j, c, a) and the product you need to linearize is x(i, j, a) * R(i, j, c, a1).

This product is equal to 0 when R = 0 and x when R = 1.

Introduce a continuous variable z(i, j, c, a, a1) with bounds [0, ub(i, j, a)]. Use index domain condition |ord(a1) <= ord(a).

Then introduce the below constraints -

`forall (i, j, c, a, a1) | ord(a1) <= ord(a)`

`z(i, j, c, a, a1) <= x(i, j, a)`

`z(i, j, c, a, a1) <= R(i, j, c, a1) * ub(i, j, a)`

`z(i, j, c, a, a1) >= R(i, j, c, a1) * lb(i, j, a)`

`z(i, j, c, a, a1) >= x(i, j, a) - ub(i, j, c) * (1 - R(i, j, c, a1))`

When R(i, j, c, a) = 0, these four constraints become

`z <= x, z <= 0, z >= 0, z >= -ub. z <= 0 and z >= 0 make z = 0`

When R(i, j, c, a ) = 1, they become

`z <= x, z <= ub, z >= lb, z >= x. z <= x and z >= x make z = x`

The expression in your constraint can now be

`sum[(c,a1)|ord(a1) <= ord(a), (z(i, j, c, a, a1) / B(c))].`

You can drop the a1 index from z and use R(i, j, c, a) instead of R(i, j, c, a1) in the constraints if you need to linearize x(i, j, a) * R(i, j, c, a) instead of x(i, j, a) * R(i, j, c, a1)

Userlevel 1 +3

Dear Mohansx,

thank you very much for your kind reply. I will study your suggestions and try to implement them!

I will write again if I have any questions.

Thanks very much!