Let's assume I have a sequence of non-overlapping tasks of type X and Y mixed. I have various runs of such sequences where it is known how many times Xs and Ys were executed as well as the approximate total runtime of the sequence. I'd like to calculate how long a task type takes. I was suggested to use LP, however, using a basic objective function with weights of 1 results in an optimum point where one of the task length is zero, which is almost certainly wrong.
A toy example: let's assume the actual task lengths are $x=1$ and $y=2$, then the following two runs were generated and made into constraints:
$2y' <= 4$
$x' + 3y' <= 7$
($x', y' >= 0$ of course)
If I apply LP with the objective function: maximize $x'+y'$, the optimum will be $x'=7$ and $y'=0$ which are not the generator values from above (1, 2 respectively).
What objective function should I pick to avoid such situations with the toy example, or in general?
Introduce nonnegative surplus and slack variables $s_i$ and $t_i$, respectively. The problem is to minimize $\sum_i (s_i+t_i)$ subject to $a_i x^\prime + b_i y^\prime - s_i + t_i = c_i$. For your example, the problem is to minimize $s_1+t_1+s_2+t_2$ subject to \begin{align} 2y^\prime - s_1 + t_1 &= 4 \\ x^\prime + 3y^\prime - s_2 + t_2 &= 7 \\ x^\prime, y^\prime, s_1, t_1, s_2, t_2 &\ge 0 \end{align} An optimal solution is $(x^\prime, y^\prime, s_1, t_1, s_2, t_2)=(1, 2, 0, 0, 0, 0)$.