For CP-SAT add_automaton, is it better to use one big automaton or multiple small ones?

[J. E. Marca]

Hi all, 

I am testing out the add_automaton calls for a scheduling problem.  So far everything is working nicely.

My long winded question I get to below is this:  Does the CP-SAT solver perform better if the links are explicit in the incoming automata?  Or can it do the work itself to recognize the overlaps on its own?

Details:

I have been taking the approach of breaking down the scheduling problem into smaller constraints and then overlapping multiple distinct automata.  To take the canonical nurse rostering example, I made one automata for the "work no more than three shifts before being assigned an off shift" constraint, and another for the "no more than two consecutive night shifts in a row" constraint.  Again, that worked fine.

I'm gradually adapting more realistic examples from a working, large scale rostering project.  I am on the edge of being able to replace my existing code with a new automata-based approach to encoding the day to day rules.  But I wonder if it is better to just bite the bullet and generate one giant scheduling automata for each person.

Specifically, I have three kinds of shifts.  One can be assigned any day.  The other two classes of shifts, call them  A and B,  are special. They require two (for A) and three (for B) days after each before another A or B shift can be assigned.   So [A, other, other, B, other other other, A, ...] etc.  

The way I am approaching the problem now, I make one automaton for each A and B shift and overlay them, as they are independent of each other, which gives me about 10 independent automata constraints for each person.  It is the case that each of these shifts has special rules, so I can't just simplify to some generic A shift or generic B shift.  For example, some have specific post-shift rules, others require pairing with other regular shift, etc.  So I need one automaton for each of these shifts at the moment.

I was just thinking that I can combine them together, so that I have one giant automaton for each person.  Right now, there is a link in each automaton that assigns "other A or B shift"; I could just make that into ten separate arrows, one for each of the A and B shifts, copy in the transition rules for each, and I'd have my one big automaton.

Which brings me to my question.

Does the solver perform better if the links are explicit in the incoming automata?  Or can it do the work itself to recognize the overlaps on its own?

My suspicion is that it will be better to make one giant automata with all the links and nodes already embedded, so that the solver has more to work with when optimizing.

On the other hand, independent smaller automata might be easier to isolate and test for infeasibilities.

Any insights would be appreciated.  I have a few quickie blog post up that I can link if anybody want more detail.

Regards,

James

[Laurent Perron]

Automata are blunt instruments. To answer your question, I would agree that one is better.

Still, I would just do:

  forall day: shitft_a(day) => not(shift_a(day+1)) && not(shift_a(day + 2))

Laurent Perron | Operations Research | lpe...@google.com | (33) 1 42 68 53 00

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/83675b46-36ba-4f84-89e3-9f4cf1915b80n%40googlegroups.com.

[J. E. Marca]

Okay thanks.

I thought perhaps automata were all around better.

My current (working just fine) approach is indeed the straightforward application of constraints.  I am playing with automata in the hopes that my current code can become faster, more maintainable, and hopefully easier to "sell" to other customers.

But if simple constraints like in your response are better, then maybe a more productive refactor effort would be to revisit my constraints code and focusing on simplicity rather than clever catch-all constraints.

I guess as always, the answer is try both and see which is better.  This is a side-project anyway, so it's not like I'm wasting anybody's money.

Regards,

James

[J. E. Marca]

So I tried it.  The code is not as pretty, and was harder to debug (in the end it was a python indentation error), but it is absolutely much faster than my automaton version.

With 65 workers, 14 days, 10 or so of these special shifts, and 50 or so regular shifts, my multiple automata version took about 30s, mostly just presolve.  This "just set the constraints" version took 1s.  It is also faster to find infeasible (55 workers is infeasible, 65 is feasible).  

The code is a bit more complicated than your pseudo code, as there are sets of possible shifts.  So I have to generate an indicator boolvar for if any of the expected shifts is today, and then if any of the denied shifts is tomorrow:

    # goal: if Today is a call shift, then Tomorrow is NOT a call shift

    for doc, day_shift_literals  in doc_day_shift_literals.items():
        for today, shift_literals in day_shift_literals.items():
            today_is_call = model.new_bool_var(f"call shift on day {today}")
            possibly_call_shift = []
            for shift, literal in shift_literals.items():
                if shift in relevant_shifts:
                    possibly_call_shift.append(literal)
            U.any_true_bools(model, possibly_call_shift, today_is_call)
            for i in range(deny_call_days):
                next_day = today + i + 1
                ...
                possibly_next_call_shift = []
                for shift, literal in doc_day_shift_literals[doc][next_day].items():
                    if shift in deny_shifts:
                        possibly_next_call_shift.append(literal)
                U.any_true_bools(
                    model, possibly_next_call_shift, ~next_day_is_not_call
                )

                # finally set the constraint: today call => not tomorrow call
                model.add_implication(today_is_call, next_day_is_not_call)

Most of the slowness of my DFA version is definitely down to the fact that I am using multiple automata.  I see 115,000 booleans in my DFA version, and just 34,000 in my "regular" one.  So I suspect I could improve the DFA speed by making it one big automaton.

However, for me one of the attractions of the DFA use was being able to split the problem up whenever it was convenient.  Clearly that is bad.

Anyway, thanks for the pointer.

Regards,

James