2
$\begingroup$

The problem that I'm trying to solve is as follows. A server has at its disposal a pool of video encoders (each encoder has different settings and causes a different load on the server) that can be enabled or disabled. All clients need to be connected to exactly one of those encoders, but one encoder can accomodate multiple clients. The objective is that the clients are connected to an encoder that suits their bitrate capacity (so an encoder that sends approx. the same bitrate as the client can handle is a 'good' encoder for that client).

This is a rather easy linear problem and the objective function can be described as follows

$$ \max{ \sum_{j \in encoders} \sum_{i \in clients} u_{ij} x_{ij}} $$ with $u_{ij}$ being a utility that is high when a client is assigned a 'good' encoder and $x_{ij}$ a binary variable that is 1 if client i is connected to server j, and 0 otherwise.

One of the constraints is of course the constraint that each client can only be connected to 1 encoder.

$$ \sum_{j \in encoders} x_{ij} = 1, \forall i \in clients $$

The problem now is that there is also a constraint that says that the sum of the loads of all the encoders that are enabled cannot be bigger than the maximum load of the server. The encoders that are enabled are the ones that are connected to at least 1 client. So every encoder that has at least one $x_{ij}=1$ is enabled and brings an extra load $load_{j}$ on the server. The constraint is thus that the sum of all these $load_j$ of the enabled encoders should be smaller than the maximum load on the server. The way i translated this into a constraint is:

$$ \sum_{j \in encoders} load_j *\max_{i \in clients}{x_{ij}} \leq load_{max} $$

E.g. if encoder $3$ is connected to at least one client, at least one of the $x_{i3}$ of that encoder will be one, and thus the max term will be equal to one, and encoder $3$ contributes $load_3$ to the sum. If no client is connected to the encoder, the max term will be equal to zero and this encoder will not contribute to the sum. This is exactly the behaviour that I need.

My question: is it really necessary to write this last constraint this way (using the max operator, which introduces non-linearity)? Or am i overlooking something and is it possible to write this constraint in a simpler/linear way.

If it is not possible to write this in a linear way, which optimization framework or toolbox could I possibly use to implement and solve this problem?

Thanks!

$\endgroup$
  • 1
    $\begingroup$ It would help to have it explicitly stated that each $load_j$ is nonnegative. $\endgroup$ – hardmath Mar 6 '15 at 19:00
  • 1
    $\begingroup$ Well, $load_j$ is actually part of the given input data (also $load_{max}$ and the bitrates of the clients and encoders are given). So we already know the $load_j$ of every encoder. So I don't think that I should put the constraint that you mention? The only thing that actually has to be decided is the assignment $x_{ij}$ between clients and encoders. $\endgroup$ – HaS Mar 6 '15 at 19:26
  • 1
    $\begingroup$ While it may be perfectly clear to you that these given values are indeed non-negative, nothing in the Question's statement promises that this is the case. It is relevant in any case to answering your Question. $\endgroup$ – hardmath Mar 6 '15 at 19:28
1
$\begingroup$

It should be possible to introduce an auxiliary variable $p_{j}$ so that $p_{j} \geq x_{ij}$ for all $i$. If $p_{j}$ is binary and the $x_{ij}$ are binary, you should be able to construct, at worst, a relaxation. It might be an equivalent formulation, although that depends on the whole formulation, and you should prove that. You might even be able to relax the binary constraint on the $p_{j}$ so that they are continuous variables on $[0,1]$.

$\endgroup$
  • $\begingroup$ Thanks, intuitively that seems like a good idea. But how can I make sure that when all $x_{ij}$ are zero for a given $j$, that $p_j$ is also chosen zero? Because if it is chosen as one, than it still complies to the constraint that $p_j \geq x_{ij}$. Is it possible to do this without putting the $p_j$ in the objective function? $\endgroup$ – HaS Mar 7 '15 at 18:15
  • $\begingroup$ Actually I think I see what you mean now. The last constraint( $\sum_{j \in encs}{p_j * load_j} < load_{max}$) will automatically make sure that $p_j$ will be chosen zero if all $x_{ij}$ are zero. And that's also the same reason why $p_j$ even might be non-binary, because it will still only be chosen as one or zero, because of this last constraint. Correct? $\endgroup$ – HaS Mar 8 '15 at 10:57
  • $\begingroup$ Re: your first question, that is why it might be a relaxation. Re: your second question, one typically shows that the solution sets of both formulations are equal and have the same objective function value. $\endgroup$ – Geoff Oxberry Mar 8 '15 at 18:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.