6
$\begingroup$

I have a weird planning problem. I think it falls under the assignment category, but I'm not sure because I'm not familiar with assignment problems, and also because there is a "temporal" angle to it, which maybe makes it a bit different from classical assignment problems.

We have $k$ workers $\{W_1,\dots,W_k\}$ ($k=2$ currently, but it could change in the future), and a sequence of tasks of different value $L=[v_1,\dots,v_n \mid v_i\in Z^{\neq}]$ such that $V=\sum_iv_i$. I want to assign tasks to each worker in such a way that $\sum v_{iW_1}=0.3V$ and $\sum v_{iW_2}=0.7V$, i.e., minimizing the cost

$$L=\left(\sum v_{iW_2}-0.7V\right)^2$$

However, the tasks are assigned in order (i.e., task $v_i$ is assigned before task $v_{i+1}$) and for some reason, the number of "switches" $m$ is to be minimized. With switch, I mean the action of assigning task $v_{i+1}$ to a different worker than the one to which I assigned task $v_i$. Obviously $m\geq1$. The overall number of switches should be minimized, and a "batched assignment" solution would be preferred: say, assign at least 3 consecutive tasks to the same worker.

I understand the problem is underspecified: the internal customer I'm doing this for, doesn't really know what they want. For example, rather than saying "don't switch too often", they should actually quantify the cost of switching from a worker to another.

Even then, I think there should be a way to find a solution which is "optimal" in some sense, like for example minimizing both the cost and the number of switches:

$$L'=\left(\sum v_{iW_2}-0.7V\right)^2+cm^2,\ c>0$$

$\endgroup$
6
$\begingroup$

You can model this with a binary variable $x_{i,j}$ to indicate whether task $i$ is assigned to worker $j$, and a binary variable $y_{i,j}$ to indicate whether task $i$ is the first task assigned to worker $j$ in the current batch. The number of switches is then $\sum_{i\ge 2} \sum_j y_{i,j}$ because this sum counts the number of times that any worker starts a new batch of tasks (except the first batch that contains task $i=1$). The constraints are: \begin{align} \sum_j x_{i,j} &= 1 &&\text{for all $i$}\\ x_{1,j} &= y_{1,j} &&\text{for all $j$} \\ x_{i,j} - x_{i-1,j} &\le y_{i,j} &&\text{for $i\ge 2$ and all $j$} \\ y_{i,j} &\le x_{i+k,j} &&\text{for $k\in\{0,1,2\}$}\\ \end{align} The first constraint assigns each task to exactly one worker. The second constraint forces task 1 to start a new batch. The third constraint enforces the logical implication that, if task $i$ is assigned to worker $j$ and task $i-1$ is assigned to a different worker, then task $i$ starts a new batch for worker $j$; that is, $(x_{i,j}=1 \land x_{i-1,j}=0) \implies y_{i,j}=1$. The fourth constraint enforces the logical implication that, if task $i$ start a new batch for worker $j$, then tasks $i$ through $i+2$ (3 consecutive tasks) must be assigned to worker $j$; that is, $y_{i,j}=1 \implies x_{i+k,j}=1$.

You specified a quadratic objective, so you could use an MIQP solver. Or you could change the objective to $$\left|\sum_i v_i x_{i,2} - 0.7V\right| + c \cdot m,$$ linearize the absolute value and use an MILP solver.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I understand that $\sum_j x_{i,j} = 1 \ \text{for all $i$}$ because each task is assigned to one and only one worker. However, can you explain the other constraint equations? Also, can you show why $\sum_{i\ge 2} \sum_j y_{i,j}=m$? Finally, once I have defined all these linear constraints, what solver should I use to find a solution? $\endgroup$ – DeltaIV Jan 24 at 16:55
  • $\begingroup$ I added more explanation just now. $\endgroup$ – RobPratt Jan 24 at 18:27
  • $\begingroup$ Thanks a lot. Just a last doubt: what do you mean by "linearizing" a nondifferentiable function? Should I solve two different optimization problems subject to same constraints, $\sum_i v_i x_{i,2} - 0.7V + c \cdot m$ and $0.7V-\sum_i v_i x_{i,2}+ c \cdot m$, then compare the solutions? $\endgroup$ – DeltaIV Jan 24 at 22:31
  • 1
    $\begingroup$ Since you are minimizing, you just need to add a single nonnegative continuous variable (call it $d$), change the objective to minimize $d+c\cdot m$, and add the constraints $-d \le \sum_i v_i x_{i,2} - 0.7V \le d$. $\endgroup$ – prubin Jan 24 at 22:53
2
$\begingroup$

When you have two objective functions, and your client can't articulate exactly how the two are to be weighed against one another, sometimes the easiest solution is to avoid making that decision. Instead of trying to figure out the client's priorities and find the single best solution, you can present them with a small list of options guaranteed to contain the best solution, and then let them choose from that list.

A solution is called "nondominated" or "Pareto efficient" if there's no way to improve one objective without worsening another. The Pareto front is the set of all nondominated solutions. It follows that no matter how heavily your client weights cost vs. switches, or vice versa, their best solution will lie somewhere in the Pareto front.

Here's one way to calculate the solutions on that front. Letting $x$ and $y$ stand for the two objective functions:

  1. Solve the problem, optimising only for $x$, and record this solution $S_0$. Let the resulting objective values be $x_0$ and $y_0$.
  2. Solve the problem again, adding a constraint that $y<y_0$. Record the solution $S_1$ and OF values $x_1, y_1$.
  3. Solve again, with the constraint that $y<y_1$...
  4. Keep going until the problem becomes infeasible.

You will now have a set of solutions where $x$ decreases as $y$ increases. Any solution outside this set will be worse than some solution within it.

(Strictly speaking, this set might contain a few non-Pareto-efficient ones too, e.g. if the first one gives $x=100, y=200$, the second one could have $x=100, y=199$, in which case the first solution is dominated by the second and could be discarded. So if you want to be really rigorous, you should go back through the results and cull any of those dominated solutions. Alternately, instead of optimising on $x$, you could optimise on something like $x+0.00001*y$ to avoid these "almost-Pareto-efficient" solutions.)

If you like, you can then plot the x- and y-values for each solution and let your client pick off the chart. It's often much easier for people to choose between options than to explain their general rule for choosing.

If you're feeling bold you can then use their preferred solutions to deduce how much priority they put on each of the two objective functions, and use that to construct a single OF to use next time around.

| improve this answer | |
$\endgroup$
  • $\begingroup$ 1. if the first solution is $x=100, y=200$, how can the second solution, with the constraint $y>y_0$, be $𝑥=100,𝑦=199$? Also, instead of performing multiple successive optimizations, wouldn't it be better to use a multiobjective optimization method which can directly build the (approximate) Pareto front, such as evolutionary algorithms? $\endgroup$ – DeltaIV Jan 27 at 13:15
  • 1
    $\begingroup$ @DeltaIV Whoops, sign error in the inequality - I've been working with a maximisation problem along these lines so I had the other version stuck in my head. Have fixed now. And yes, if you have access to a method that can directly and efficiently build the Pareto front, by all means use it - I was just giving one example of how that can be done, even with just a basic MIP solver. $\endgroup$ – Geoffrey Brent Jan 27 at 13:52

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.