question - validate decisions dynamically based on values of other decisions

[szymon-szym]

Hi!

First of all, thank you for the great library and all your work around spreading knowledge about mathematical planning. It is amazing.

I am struggling with modeling my problem, and I wonder if the problem is not a great fit for flips, or am I missing something. It would be great if you could give me a hint about the direction I should go.

Here is the problem:

I have a list of desks and a list of people. I want to assign desks to people. One person can be assigned to one desk, one desk can be assigned max to one person. People are grouped into teams. Desks are grouped into "desk groups" and have specific order so we can say which desk is next to another. We also know what desk was assigned to the person during the previous assignment. I am trying to optimize the way desks are assigned, so as many people as possible are sitting together with the rest of the team (the main objective), and, if possible, people are not changing desks compared to the previous assignment (secondary objective). My domain looks like this (I will eventually ad single case discriminated unions)

type Desk = { Id: string; OrderId: int }

type DeskGroup = { Desks: List<Desk> }

type Person =
    { Id: string
      Team: string
      LastDayDesk: Desk option}

type Team = { Members: List<Person>; Name: string }

My input is

• people // []
• desks // []

Decision

let assignments =
    DecisionBuilder "DeskAssignment" {
        for team in people do
        for person in team.Members do
        for deskGroup in desks do
        for desk in deskGroup.Desks ->
            Boolean
    } |> SMap4

Constraints

let deskAssignmentConstraint =
    ConstraintBuilder "OnePersonssignedExactlyToOneDesk" {
        for team in people do
        for person in team.Members ->
            sum assignments.[All, person, All, All] == 1.0
    }

let daskAssignmentConstrainDesks =
    ConstraintBuilder "OneDeskAssignedToOnePersonOrNone" {
        for dg in desks do
        for desk in dg.Desks ->
            sum assignments.[All, All, All, desk] <== 1.0
    }

Linear expression for checking for the secondary objective

let isDeskChanged  person desk =
    match person.LastDayDesk with
    | Some ld -> desk.OrderId <> ld.OrderId 
    | None -> false

let linearExpressionWhoChangedDesk = 
    assignments
    |> SMap4.toList
    |> List.filter (fun ((t, p, dg, d), dec) -> printfn $"checking if desk was changed for person {p.Id}: {isDeskChanged p d}";isDeskChanged p d)
    |> SMap4.ofList
    |> sum

So far so good. I have meaningful assignments, and I can optimize for the secondary objective. But now I am trying to create the linear expression for the main objective - do teams sit together. I can check this only in the context of all decisions. My first idea was to filter positive decisions and check assigned desks, but I am not sure if this is doable. I was trying to start with something like this:

let positiveDecisionsByTeams = 
    assignments
    |> SMap4.toList
    |> List.filter (fun ((team, person, desksGroup, desc), decision) -> decision = 1.0)
    |> List.map (fun ((t, p, dg, d), dec) -> {Person=p;Team=t;Desk=d;DeskGroup=dg})
    |> List.groupBy (fun d -> d.Team)

Which obviously won't work, because the comparation decision = 1.0 doesn't make any sense from types perspective.

Is there a way I can filter positive decisions? Does it even make sense? Is there a way to validate decisions based on the value of other decisions? In my example, I can validate the given decision only knowing other results, so I can say if team members were assigned to the desks next to each other.

It would be great if anyone has any idea in what direction I could move with my problem. Thank!

[matthewcrews]

Ah, yes. This is doable by using indicator variables. Would you be alright if I turned this into a blog post?

[szymon-szym]

Hi Matthew! Sure, it would be great. Please let me know if you need more input about the domain. By the way, your blog is a really amazing learning resource!

[matthewcrews]

Here's the post: https://matthewcrews.com/blog/2021/11/team-desk-assignments/ Sorry for the delay.

[szymon-szym]

Thank you, Matthew! This is super helpful. I believe that the idea of indicator variables will be useful for many developers out there. Your responsiveness is amazing!