1
$\begingroup$

I am currently working with some network assignment problem as a network engineer. My engineering application can be stated as follows: There are $M$ users that needs to be assign to $N$ servers. This assignment can be characterised through the binary variable $a_{mn}$.

$$a_{mn} = \left\{ \begin{array}{*{20}{c}} 1 & \text{if user } m \text{ is assigned to server } n \\ 0 & \text{otherwise} \end{array} \right. $$

For a user, it can only connect to one server but for a server it can take in as many users as it wants and hence ${\sum\limits_{n = 1}^N {{a_{mn}}} \le 1,\forall m}$.

When a user is admitted to the server, the server will do some computing task for the user using its own CPU clock as a computational resource. The computing time (measured in seconds) is ${t_{mn}} = \frac{{{X_m}\left( {{\rm{cycle}}} \right)}}{{{\phi _{mn}}{F_n}\left( {{\rm{cycle/sec}}} \right)}}$. Here $0 \le {\phi _{mn}} \le 1$ is a decision variable that dictates the ratio of computing resource $F_n$ allocation from server $n$ to user $m$.

For example, if there is 1 server and 2 user then a 50-50 resource allocation will result in ${\phi _{11}} = {\phi _{21}} = \frac{1}{2}$ and hence the constraint ${\sum\limits_{m = 1}^M {{\phi _{mn}}} \le 1,\forall n}$ is formulated.

Furthermore, I want to enforce the constraint that if a user is not connected to a server $n$ then the resource $F_n$ will not flow to the user $m$ by using the constraint ${{\phi _{mn}} \le {a_{mn}}}$.

From the stated facts, I formulate the following problem:

$\begin{array}{*{20}{c}} {\mathop {\min }\limits_{{\phi _{mn}},{a_{mn}}} }&{\sum\limits_{m = 1}^{m = M} {\sum\limits_{n = 1}^{n = N} {{a_{mn}}{t_{mn}}} } }\\ {c1:}&{{\phi _{mn}} \le {a_{mn}}}\\ {c2:}&{0 \le {\phi _{mn}} \le 1}\\ {c3:}&{{a_{mn}} \in \left\{ {0,1} \right\}}\\ {c4:}&{\sum\limits_{n = 1}^N {{a_{mn}}} \le 1,\forall m}\\ {c5:}&{\sum\limits_{m = 1}^M {{\phi _{mn}}} \le 1,\forall n} \end{array}$

My problem is that when ${{\phi _{mn}}=0}$ due to $a_{mn}=0$ then ${{t_{mn}}}$ just blow up because of division by zero. Even worst, it looks like some kind of indeterminate form $\frac{0}{0}$ due to constraint $c1$.Therefore, my question is: how to avoid division by zero with a binary variable at the denominator in a network assignment problem?

Currently, the only quick and dirty way I can think of is to add a number $\epsilon$ like this ${t_{mn}} = \frac{{{X_m}\left( {{\rm{cycle}}} \right)}}{{{\phi _{mn}}{F_n}\left( {{\rm{cycle/sec}}} \right) + \varepsilon }}$ but I am not sure on how to choose the magnitude of $\epsilon$.

I hope that there are better ways to reformulate this problem but I cannot think of any ideas.

$\endgroup$
7
  • 1
    $\begingroup$ For the $ \varepsilon$ I would use a value very slightly higher than the machine epsilon your solver is using. You can also try doing $\phi \geq 2 \varepsilon$ instead of $0$. Also, with complex fractions like this, I believe it's usual to create an auxiliary variable $z = \frac{1}{\phi_{mn}F_n(cycle/sec)}$ and $t_{mn} = X_m(cycle)\cdot z$. $\endgroup$ Commented Jul 2 at 9:14
  • 1
    $\begingroup$ Depending on the specifics of your application, imposing a minimum $\phi_{mn}$ might make sense. This would also be beneficial because allowing for extremely small $\phi$'s (and thus extremely large $t$'s) might make your MIP numerically challenging. $\endgroup$ Commented Jul 2 at 9:21
  • $\begingroup$ $F_n$ is not a variable it is a numerical parameter $\endgroup$ Commented Jul 2 at 11:45
  • 3
    $\begingroup$ You are apparently minimizing overall computing time, and you apparently do not require every user to be assigned to a server. So the first question to answer is what you want the objective contribution of an unassigned user to be. One possibility is zero, since an unassigned user obviously consumes no compute time. Another possibility would be some arbitrarily large constant (possibly the same for all users, possibly user-specific) to penalize leaving the user unassigned. Once you decide how to handle this, reformulation can be discussed. $\endgroup$
    – prubin
    Commented Jul 2 at 16:31
  • $\begingroup$ Thank you can you discuss both case sfor me in an answer so that I can accept it. Now I reallize that it is more reasonable this way. The zero possibility and penalize leaving the user unassigned is quite a sharp observation and somehow I miss that due to tunnel vision. $\endgroup$ Commented Jul 2 at 19:52

1 Answer 1

2
$\begingroup$

The fundamental question to address is the time consumption to associate with a user that is not served ($a_{mn}=0$ for all $n,$ implying $\phi_{mn} = 0$ for all $n.$ Possibilities include no time consumption (realistic but might discourage the model from serving anyone) or a fixed "penalty" computing time $T.$

Once you have an answer to this, you can use introduce a binary variable $\sigma_m$ to indicate whether user $m$ is served at all (1) or not (0), along with constraints $$\epsilon_m \sigma_m \le \phi_{mn} \le \sigma_m$$ to enforce the definition of $\sigma$ (where $\epsilon_m > 0$ is the minimum nonzero amount of time that can be granted to user $m$) and implication constraints of the form $$\sigma_{m} = 0 \implies t_{mn} = 0$$ to eliminate division by zero. If the time penalty is zero for an unscheduled user, that is all you have to do. If the time penalty is $T$, then you need to add $T(1-\sigma_m)$ to the objective function.

Your objective function will remain nonlinear. If that is a concern, you can get a linear approximation by setting fixed breakpoints along the interval [0, 1], replacing the continuous variable $\phi_{mn}$ with the sum of weights on the breakpoints (SOS1 constraints) and doing a piecewise-linear interpolation of $t_{mn}.$ If you decide to go that route and need help with the formulation, I suggest a separate question.

$\endgroup$
8
  • $\begingroup$ I have discuss your idea with my colleagues and and now they have change the system spec to each server must serve at least one user to avoid the zero objective issue. Due to this reason will there be any change in the formulation of $\sigma_{mn}$ $\endgroup$ Commented Jul 2 at 21:10
  • 1
    $\begingroup$ If each server must serve at least one user, there cannot be any idle servers, but there can still be unserved users. I do not think this changes anything in my answer. $\endgroup$
    – prubin
    Commented Jul 2 at 22:05
  • $\begingroup$ Thank you but should it be $\sigma_{mn}$ - the penalty for an $m-n$ link or just $\sigma_m$ ? Also, why dont we just use ${\sigma_m}{a_{mn}} \le {\phi _{mn}} \le {a_{mn}}$ ? I find it hard to distinguish between $a_{mn}$ and $\sigma$ $\endgroup$ Commented Jul 2 at 23:05
  • 1
    $\begingroup$ $\sigma_m$ signals whether $m$ is ever served (1) or not served at all (0). That's different from $a_{mn},$ which signals whether $m$ is served by a particular server $n.$ As for the inequalities you suggested, they would imply that if $m$ is served by $n$ $(a_{mn}=1)$ then $\phi_{mn}=1,$ which contradicts your example of two servers each serving half of a user. $\endgroup$
    – prubin
    Commented Jul 3 at 2:42
  • 1
    $\begingroup$ You are correct that I misread that. That said, the part about $\sigma_m$ signaling whether $m$ receives any service from any server stands. $\endgroup$
    – prubin
    Commented Jul 3 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.