How to minimize the variance of time intervals between scheduled slots?

Specific Domains Optimization (Mathematical)
1

Hi,
I’m trying to setup an optimization in JuMP. I do not have much experience in this field but it seems trivial:
The aim is assigns speaker to slots with respect to some conditions. I want to minimizes the variance of the time intervals between the scheduled slots for each speaker.

I’ve implemented a matrix of binary decision variables a[i,j] that is 1 if slot i is assigned to speaker j. With this I can encode my conditions easily, such as

@variable(model, a[1:n_slots, 1:n_speakers], Bin)
@constraint(model, sum(a, dims=1) .== 1)  # only one speaker per slot

Unfortunately, I get stuck with the loss. A possible loss function for speaker j is
l_k = \sum_k | (t_{k,j} - t_{k-1, j}) - \bar{d} |
where t_k is the slot number of the k-th assignment (i.e. the k -th occurrence of a[:,j] == 1) of speaker j, and \bar{d} the average time interval without constrains: \bar{d} = \frac{n_\text{speakers}}{n_\text{slots}}. (kind of a linearized variance)

My questions are:

  • How can I code such a loss compatible with JuMP? My problem is to get from the matrix a to the slot times t_k.
  • Could I use a different loss function instead?
  • I feel I probably should set up the problem complete differently. I’d appreciate any hint!

Many thanks in advance!
Andreas

2

You could use indicator constraints to create t_k - t_{k-1}:

@variable(model, time_since_last[1:nslots, 1:n_speakers])
@constraint(model, [j=1:n_speakers], time_since_last[1, j] == 0)
@constraint(model, [i=2:(n_slots-1), j=1:n_speakers], a[i, j] --> {time_since_last[i + 1, j] == 0})
@constraint(model, [i=2:n_slots, j=1:n_speakers], !a[i, j] --> {time_since_last[i, j] == time_since_last[i - 1, j] + 1})

For the objective, you can do as follows:

@variable(model, costs[1:nslots, 1:n_speakers] >= 0)
@constraint(model, [i=2:n_slots, j=1:n_speakers], a[i, j] --> {costs[i, j] >= time_since_last[i, j] - bar_d})
@constraint(model, [i=2:n_slots, j=1:n_speakers], a[i, j] --> {costs[i, j] >= bar_d - time_since_last[i, j]})
@objective(model, Min, sum(costs))
1 Like
3

Thanks a lot @blegat!
This is clever solution. As soon I have some time I will try to implement it.

1 Like