How is this type of function treated in mathematical programming?

Question

I'm trying to solve a problem for human resource allocation that has a function that receives the number of people working on a project and returns the time to finish it. The number of employees in a project has a nonlinear relation with the time to end it, therefore it can be represented as a matrix, the line controlling the number of employees, and the column controlling the project. For example, in the matrix below (in days), if I allocate 3 people in the 1° project, it will end in 5 days.

$$ A=\begin{bmatrix} 10 & 9 & 7\\ 8 & 7 & 6.5\\ 5 & 6.5 & 6\\ \end{bmatrix} $$

I think I can use binary variables, having one of these for each position of the matrix, to transform the problem into a mixed-integer linear problem, which is what I prefer so I can assess a metaheuristic that I used to solve it. But I also think that it isn't the right approach to solve it.

Answer 1

If the time for any project fails to be a convex function of the number of employees assigned to the project, I think your best bet is indeed to use a binary variable for each combination of project and employee count. Note that, in your example, completion time is a linear function of head count for the third project and a convex function for the second project, but the time-head count relationship is nonconvex for the first project (adding the second employee is less beneficial than adding the third employee is).

If the relationship is convex for all projects, you have an alternative choice for formulating it, using an integer variable (number of employees assigned) for each project. It is based on the observation that a convex piecewise-linear function is the max of the linear functions describing each segment, along with the assumption that your model would favor lower completion times over higher completion times.

Suppose we change the 10 in the upper left corner of your matrix to 14. Let $x_1$ be the number of employees assigned to project 1 and $t_1$ its completion time. The first two entries in the modified column 1 give us the line $t_1 = 20 - 6 x_1$, while the second and third give us the line $t_1 = 14 - 3 x_1$. So you could just add the constraints $t_1 \ge 20 - 6x_1$ and $t_1 \ge 14 - 3x_1$ and rely on the solver to pick the smallest value of $t_1$ (given $x_1$) that satisfies both constraints. This generalizes to more than 3 employees on a project as long as the time-count relationship is convex.