Linearization of a scheduling objective function

I am trying to maximize the workload per employee.

An example:

• $$e$$ the index of an employee
• $$j$$ the index of a project
• decision variable: $$x_{e,j} \in \mathbb{Z}$$ and $$0 \leq x_{e,j} \leq 100$$ deciding with how much percent an employee may work on a project. (Yes it is possible that an employee works on a project with 40%. The remaining 60% should get covered from someone else and all projects should get covered but this is not a part of this problem.)
• decision variable: $$y_e \in \{0,1\}$$ deciding if employee e is working

I had in mind something like the following as a part of the objective function $$\max\sum\limits_{e,j}\frac{x_{e,j}}{y_e}$$

The problem is that this is not linear.

Example: $$\frac{160}{3} < \frac{160}{2}$$ thus 2 employees whould be preferred instead of 3.

Note:

The following constraint has to hold,

$$\sum\limits_e x_{e,j} = 1 \ \ \forall \ \ j$$

implying that all projects have to get covered.

• Is that the same as $\min\sum{y_e}$? – Stradivari Oct 14 '19 at 14:18
• @Stradivari I think you are right. I'll just test your suggestion. – Georgios Oct 14 '19 at 14:38
• Check this objective function. You wrote $\frac{x_{e,j}}{y_e}$ but If $y_e=0$ you will have a division by zero. Thus, there is no possible linearization. I guess your objective function is: (maximize workload per employee) $$\max \frac{\sum_{e}\sum_{j} x_{e,j} }{\sum_{e}y_e}$$ And you should add a constraint to guarantee more than zero employees. $$\sum_{e}y_e \geq 1$$ This problem needs more constraints yet. Probably, you need to describe constraints for work capacity per employee. – Alexandre Frias Oct 14 '19 at 18:12
• @AlexandreFrias This case will never occur since I already mentioned in the description that all projects $j$ should get fully covered. Thus, a constraint is implicitly implemented and not mentioned here avoiding the case of $\sum\limits_e y_{e} = 0$. – Georgios Oct 15 '19 at 10:25
• @Georgios, $y_e = 0$ for certain index $e$. Thus, your objective function has this problem yet. The term of the summation $\frac{x_{e,j}}{y_e}$ can be undefined. – Alexandre Frias Oct 15 '19 at 16:11

You can linearize the objective function, but at the cost of more binary variables and big-M type constraints.

Let's assume that we know a priori that the number of employees used will be between 0 (or maybe 1) and $$N$$. Introduce binary variables $$z_0, \dots, z_N$$ with the constraint $$\sum_{k=0}^N z_k = 1.$$The $$z$$ variables will determine how many employees are being used, via the constraint $$\sum_e y_e = \sum_k kz_k.$$

Next, introduce a continuous variable $$W$$ representing the objective value (to be maximized) and continuous variables $$S_0, \dots, S_k$$, along with the linear constraints $$S_k =\frac{1}{k}\sum_{e,j} x_{e,j}\quad \forall k$$(so that $$S_k$$ is the objective value you want if $$k$$ employees are used) along with the constraints $$S_k - \underline{M}_k (1-z_k) \le W \le S_k + \overline{M}_k (1-z_k)\quad \forall k,$$where $$\underline{M}_k$$ and $$\overline{M}_k$$ are sufficiently large constants (the sizes of which, as the notation suggests, may vary as $$k$$ varies). This ensures that $$W$$, the thing you are maximizing, equals $$S_k$$ if and only if $$z_k=1$$ (i.e., you are using $$k$$ workers).

Another approach to model the objective function could be the following where $$M$$ is a big number that forces the model to choose as few as possible numbers of operators.

$$\max \sum_{e,j} x_{e,j}-M\times \sum_e y_e$$

• When the question defines the profits, $d_e$ and $c_{e,j}$, associated to the variables $y_e$ and $x_{e,j}$ I agree with you. But, I do not understand the meaning of this objective function. In this case, what are you maximizing? – Alexandre Frias Oct 14 '19 at 16:29
• I feel that in his case maybe $\sum_{e,j} x_{e,j}$ is constant. – Stradivari Oct 14 '19 at 19:59
• @Stradivari , maybe $\sum_{e} x_{e,j} =1 \forall j$ but, only Georgios knows that. – Alexandre Frias Oct 15 '19 at 4:40
• I want to say " All project $j$ must be completed." – Alexandre Frias Oct 15 '19 at 4:44
• @AlexandreFrias yes this is exactly what I meant. I will add that to the description. – Georgios Oct 15 '19 at 10:30

Suppose that, the following non-linear objective arises (MAX/MIN): $$$$\max\frac{\sum\limits_{j} a_{j} x_{j}}{\sum\limits_{j} b_{j} x_{j}}$$$$

1) Replace the expression $$\dfrac{1}{\sum\limits_{j} b_{j} x_{j}}$$ by a variable $$t$$.

2) Represent the products $$x_{j} t$$ by variables $$w_{j}$$. The objective now becomes:

$$$$\max \sum_{j} a_{j} w_{j}.$$$$ Introduce a constraint: $$$$\sum_{j} b_{j} w_{j}=1$$$$ in order to satisfy condition 1.

Convert the original constraints of the form: \begin{align} \sum_{j} d_{j} x_{j} &\leqq e \\ \sum_{j} d_{j} w_{j}-e t &\leqq 0 \end{align} It must be pointed out that this transformation is only valid if the denominator $$\sum\limits_{j} b_{j} x_{j}$$ is always of the same sign and non-zero. If necessary (and it is valid), an extra constraint must be introduced to ensure this. If $$\sum\limits_{j} b_{j} x_{j}$$ always be negative the directions of the inequalities in the constraints above must, of course, be reversed.