8
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Is that the same as $\min\sum{y_e}$? $\endgroup$ – Stradivari Oct 14 at 14:18
  • $\begingroup$ @Stradivari I think you are right. I'll just test your suggestion. $\endgroup$ – Georgios Oct 14 at 14:38
  • 1
    $\begingroup$ 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. $\endgroup$ – Alexandre Frias Oct 14 at 18:12
  • $\begingroup$ @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$. $\endgroup$ – Georgios Oct 15 at 10:25
  • $\begingroup$ @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. $\endgroup$ – Alexandre Frias Oct 15 at 16:11
4
$\begingroup$

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).

$\endgroup$
5
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Alexandre Frias Oct 14 at 16:29
  • $\begingroup$ I feel that in his case maybe $\sum_{e,j} x_{e,j}$ is constant. $\endgroup$ – Stradivari Oct 14 at 19:59
  • $\begingroup$ @Stradivari , maybe $\sum_{e} x_{e,j} =1 \forall j$ but, only Georgios knows that. $\endgroup$ – Alexandre Frias Oct 15 at 4:40
  • $\begingroup$ I want to say " All project $j$ must be completed." $\endgroup$ – Alexandre Frias Oct 15 at 4:44
  • $\begingroup$ @AlexandreFrias yes this is exactly what I meant. I will add that to the description. $\endgroup$ – Georgios Oct 15 at 10:30
4
$\begingroup$

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

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:

\begin{equation} \max \sum_{j} a_{j} w_{j}. \end{equation} Introduce a constraint: \begin{equation} \sum_{j} b_{j} w_{j}=1 \end{equation} 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.

Reference: Model Building in Mathematical Programming

$\endgroup$

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.