# Modelling problem with JuMP

**URL:** <https://discourse.julialang.org/t/modelling-problem-with-jump/94520>\
**Category:** Optimization (Mathematical)\
**Tags:** question, jump\
**Created:** [February 12, 2023, 3:59pm UTC](https://discourse.julialang.org/t/modelling-problem-with-jump/94520 "2023-02-12T15:59:48Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Karajan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/karajan/32/8545_2.png) [@Karajan](https://discourse.julialang.org/u/Karajan)\
**Post date:** [February 12, 2023, 3:59pm UTC](https://discourse.julialang.org/t/modelling-problem-with-jump/94520/1 "2023-02-12T15:59:48Z")

</div>

Hi there!

I have the following problem: I have `n >= 8` people who are supposed to do a “shift” (this is not for a job but for a hobby. I would hope HR people know how to properly do this 😁). There is one shift each on Saturday and Sunday, in the morning and in the evening (so 4 each weekend), in teams of 2. I now want to create a plan so that everyone …

1. has to be there equally often
2. only has to be there once every weekend (that’s why `n >= 8` is relevant)
3. is there the same number of mornings and evenings
4. is there the same number of Saturdays and Sundays
5. has a new partner every time (until they have to start from the beginning)
6. has the same time (in weeks) between each shift (as close as possible)
7. a few more parts I’m going to worry about later

I’m trying to use constraints in JuMP and I managed to get the first 5 points working (although I’m sure it’s not very pretty).

```julia
using JuMP
using HiGHS

model = Model(HiGHS.Optimizer)

nperson = 14
nteams = sum(1:nperson-1) # Number of possible teams (person with a different person)
nweeks = nteams # So each team can have a shift on Saturday/Sunday, morning/evening each
npersonperteam = 2
sat_sun = 2
morning_evening = 2
nshifts_perperson = (npersonperteam * nweeks * sat_sun * morning_evening) ÷ nperson

# Each bit indicates which two people have a shift, each morning/evening of each
# Saturday/Sunday of each week
# E.g. plan[1, 2, 3, 1, 2] = 1 means person 1 and person 2 have a shift in third week,
# on Sunday (2) morning (1).
@variable(model, plan[1:nperson, 1:nperson, 1:nweeks, 1:morning_evening, 1:sat_sun], Bin)

# I'm mirroring the matrix so I can later sum over whole rows/columns
# This should also work with Symmetric constraints, but I couldn't get it to work
for i1 in 1:nperson, i2 in i1+1:nperson, j in 1:nweeks, k in 1:morning_evening, l in 1:sat_sun
    @constraint(model, plan[i1, i2, j, k, l] == plan[i2, i1, j, k, l])
end

# each shift consists of 2 people = 1 Team (= 2 here since I mirrored the matrix)
for j in 1:nweeks, k in 1:morning_evening, l in 1:sat_sun
    tst = @constraint(model, sum(plan[:, :, j, k, l]) == 2)
end

# a team can't be the same person twice
for i in 1:nperson, j in 1:nweeks, k in 1:morning_evening, l in 1:sat_sun
    tst = @constraint(model, plan[i, i, j, k, l] == 0)
end

# 2) ... only has to be there once every weekend
for i in 1:nperson, j in 1:nweeks
    @constraint(model, sum(plan[i, :, j, :, :]) <= 1)
end

# 3) ... is there the same number of mornings and evenings
for i in 1:nperson, k in 1:morning_evening
    @constraint(model, sum(plan[i, :, :, k, :]) == nshifts_perperson ÷ 2)
end

# 4) ... is there the same number of Saturdays and Sundays
for i in 1:nperson, l in 1:sat_sun
    @constraint(model, sum(plan[i, :, :, :, l]) == nshifts_perperson ÷ 2)
end

# 5) ... has a new partner every time
# implemented here a "has each partner the same amount of times"
for i1 in 1:nperson, i2 in i1+1:nperson
    @constraint(model, sum(plan[i1, i2, :, :, :]) == 4nweeks ÷ nteams)
end

@objective(model, Min, 0)
optimize!(model)
p = round.(Int, value.(plan))
display(p)

```

Now I’m lost at point 6 since I don’t know how to get “distances” between the shifts out of the `plan` matrix. In normal Julia code I would count the indices between `true`s for each person in the matrix, but I don’t think this works in JuMP.

I also though about turning everything on its head, and instead modelling the time between each shift instead. However, then I don’t know how to check which people are there the same time (in order to limit them to two, for example).

Is something like this possible in JuMP or should I use a different tool?

---

<div class="post-metadata">

**Author:** ![trulsf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/trulsf/32/46751_2.png) [@trulsf](https://discourse.julialang.org/u/trulsf)\
**Post date:** [February 12, 2023, 7:46pm UTC](https://discourse.julialang.org/t/modelling-problem-with-jump/94520/2 "2023-02-12T19:46:54Z")

</div>

Solving this with JuMP and a MIP solver like e.g. HiGHS should be doable. Since you are only looking for a feasible solution, constraint programming could also be a viable approach.

The distance between shifts could be modelled by requiring just a single shift for every M consecutive weeks. Something along these lines should work (but I have not tested)

```julia
# 6) ...only one shift per M consecutive weeks
M = nweeks ÷ nshifts_perperson
for i in 1:nperson, j in 1:nweeks-M
    @constraint(model, sum(plan[i, i2, jj, k, l] for i2 in i+1:nperson, jj in j + M, k in 1:morning_evening, l in 1:sat_sun) <= 1)
end

```

---

<div class="post-metadata">

**Author:** ![Karajan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/karajan/32/8545_2.png) [@Karajan](https://discourse.julialang.org/u/Karajan)\
**Post date:** [February 14, 2023, 2:47pm UTC](https://discourse.julialang.org/t/modelling-problem-with-jump/94520/3 "2023-02-14T14:47:12Z")

</div>

Thank you, this idea worked!

It takes quite long now to generate a solution (like ~9h) but at least I’m getting one. 👍