Multiplication and addition in constraints

[Enes Erdin]

Hello all,

I am trying to implement such a constraint

\sum_{j\in S_i} b_{ij} \sum_{k\in E} x_{ij}^k = s_{i}

the equation is also attached as picture. What I am trying to do is basically this:

user i tries to reach a set of servers, j. The set of the servers are limited.

However, during this routing the connection can go through nodes k. k can be any node so it is an element of the universal set.

x is the flow matrix (from user i to destination j via k)
b is binary variable to see if x is using/or should use the path (i,j)
s is the traffic generated by i and it is known.

I tried many sums quicksums but I could not find a way to realize the function.

Any help is appreciated.

Thanks in advance,
Enes.

[Tobias Achterberg]

As far as I understand, what you have is a classical fixed charge network problem.

What you want is that b_ij = 1 if x_ij^k > 0 for any k. So, you need to
introduce inequalities that force this relationship. One way is to use indicator
constraints:

b_{ij} = 0 -> x_{ij}^k = 0 for all i,j,k

If this generates too many constraints, you can also use the equivalent formulation

b_{ij} = 0 -> sum_k {x_{ij}^k} = 0 for all i,j

But note that the latter formulation has a weaker LP relaxation.

If you have reasonable upper bounds for the x_{ij}^k variables, you can also use
a big-M formulation:

x_{ij}^k - u_{ij}^k x_{ij}^ <= 0

with u_{ij}^k being an upper bound for x_{ij}^k.

Of course, all this holds only if the x_{ij}^k variables are non-negative.

Finally, your constraint then becomes just

\sum_{k \in E} x_{ij}^k = s_i


Regards,

Tobias