Nurse scheduling CpSolver stuck in some solutions

Question

I'm implement a complex nurse scheduling problem. I want the nurse work a continuous shifts and match minimum nurses required in every shift.

specifically, the problem hit me is I got feasible but stuck solution like:

Solution 0
 Day 0

  Nurse 0 works from shift 0 to 3
  Nurse 1 works from shift 4 to 7

Solution 1
 Day 0

  Nurse 0 works from shift 0 to 3
  Nurse 1 works from shift 4 to 7

the cp_model.CpSolver just gave me the same solution 200 times.

I want my solution is something like:

Solution 0
 Day 0

  Nurse 0 works from shift 0 to 3
  Nurse 1 works from shift 4 to 7

Solution 1
 Day 0

  Nurse 0 works from shift 0 to 2
  Nurse 1 works from shift 2 to 7

Solution 2
 Day 0

  Nurse 0 works from shift 5 to 7
  Nurse 1 works from shift 0 to 5

and more other feasible solutions.

I already take a look document about cp_model and cp_model.CpSolver cp_model.py reference.md

but none of above mentioned some choice when using CpSolver. I'm wondering is there some method I can choose when using CpSolver? Or anything I missed?

here is my code:

from ortools.sat.python import cp_model
num_nurses = 2    
num_shifts = 8    
num_days = 1      
all_nurses = list(range(num_nurses))
all_shifts = list(range(num_shifts))
all_days = list(range(num_days))
start_shift = list(range(num_shifts))
end_shift = list(range(num_shifts))
RESEARCH_model = cp_model.CpModel()


# Creates shift variables.
RESEARCH_shifts = {}
for n in all_nurses:
    for d in all_days:
        for start in start_shift:
            for end in end_shift:
                RESEARCH_shifts[(n, d, start, end)] =\
                RESEARCH_model.NewBoolVar('shift_n{}d{}start{}end{}'.format(n, 
                d, start, end))

# constraint with minimum required nurse equal to 1
for d in all_days:
    for s in all_shifts:
        RESEARCH_model.Add(sum(RESEARCH_shifts[(n, d, start, end)] 
        for n in all_nurses
        for start in start_shift  for end in range(start , num_shifts ) 
        if start <= s <= end) == 1)

# constraint with continuous shifts
for d in all_days:
    for n in all_nurses:
        RESEARCH_model.Add(sum(RESEARCH_shifts[(n, d, start, end)] 
        for start in start_shift
        for end in range(start, num_shifts )
        if 0 <= (end - start + 1) <= 8 ) <= 1)

# the callback

class RESEARCH_NursesPartialSolutionPrinter(cp_model.CpSolverSolutionCallback):
    """Print intermediate solutions."""

    def __init__(self, shifts, num_nurses, num_days, num_shifts ,start_shift, end_shift, sols):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self._shifts = shifts
        self._num_nurses = num_nurses
        self._num_days = num_days
        self._num_shifts = num_shifts
        self._solutions = set(sols)
        self._solution_count = 0
        self._start_shift = start_shift
        self._end_shift = end_shift

    def on_solution_callback(self):
        self._solution_count += 1
        if self._solution_count in self._solutions:
            print('Solution %i' % self._solution_count)
            for d in range(self._num_days):
                print(' Day {}'.format(d))
                for n in range(self._num_nurses):
                    for start in self._start_shift:
                        for end in range(start, self._num_shifts):
                            if self.Value(self._shifts[(n, d, start, end)]) == True:
                                print('  Nurse {} works from shift {} to {}'.format(n, start, end))

# create solver and solve it.
solver = cp_model.CpSolver()

# Display the first n solutions.
a_few_solutions = range(200)
RESEARCH_solution_printer = RESEARCH_NursesPartialSolutionPrinter(RESEARCH_shifts, 
                                                                  num_nurses, 
                                                                  num_days, 
                                                                  num_shifts, 
                                                                  start_shift, 
                                                                  end_shift,  
                                                                  a_few_solutions)


solver.parameters.max_time_in_seconds = 2.0
solver.SearchForAllSolutions(RESEARCH_model, RESEARCH_solution_printer)

I expect the output like:

Solution 0

 Day 0

  Nurse 0 works from shift 0 to 3
  Nurse 1 works from shift 4 to 7

Solution 1

 Day 0

  Nurse 0 works from shift 0 to 2
  Nurse 1 works from shift 3 to 7

Solution 2

 Day 0

  Nurse 0 works from shift 6 to 7
  Nurse 1 works from shift 0 to 5

BUT I got output like:

Solution 0
 Day 0

  Nurse 0 works from shift 0 to 3
  Nurse 1 works from shift 4 to 7

Solution 1
 Day 0

  Nurse 0 works from shift 0 to 3
  Nurse 1 works from shift 4 to 7

Solution 2
 Day 0

  Nurse 0 works from shift 0 to 3
  Nurse 1 works from shift 4 to 7

Which is not I want.

Answer 1

The solution was given on the github

https://github.com/google/or-tools/issues/1300

The issue is that this code creates a lot of unconstrained Boolean variables. When enumerating all solutions, you are exploring all 2^n combinations of these variables.