CODEWITHSUNDEEP
pythonlinear-programmingor-tools
pavvvkin
pavvvkin

Reputation: 31

Is there any way to set disjunctive constraints using Google OR Tools for python?

I'm trying to build integer LP model using Google OR for Python 3.7. And I can't figure out how to create disjunctive constraints. Suppose, there are {x1, x2, x3, x4, x5, ...} variables, and I want to disjunct several conditions in one, kind of: x1 + x2 = 2 | x2 + x3 = 2 | x3 + x4 = 2 So, to satisfy that condition x2 + x3 = 2 is enough.

As I understood, it's possible and called disjunctive conditions. For OR Tools I found some explanation, but it's for C++ and look outdated. There are also tutorial by google, but its's for CP, not LP task, so I have no idea how to use it in my case (I haven't model, just solver)

My task is to define dinner time (let's say 2 hour) during work shift with as little overlapping as possible. For variable 0 stands for dinner and 1 for work time. So, here is a bit simplified version of what I got now:

...
solver = pywraplp.Solver('SolveIntegerProblem', pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
objective = solver.Objective()

for e in employees:
  for d in days:
    # setting up a constraint that during workday employee should have a dinner time for 2 hours
    dinner_constraint = solver.Constraint(-solver.infinity(), e.end_hour - e.start_hour - 1) # force to spend at least 2 hours for dinner
    for h in range(e.start_hour, e.end_hour):
      variables[(e, d, h)] = solver.IntVar(0.0, 1.0, 'mhr_{}_{}_{}'.format(e, d, h))
      objective.SetCoefficient(variables[(e, d, h)], 1)
      dinner_constraint.SetCoefficient(variables[(e, d, h)], 1)
    for h in range(e.start_hour, e.end_hour - 1): # e.end_hour - 1 due to dinner is 2 hours
      dinner_sub_constraint = solver.Constraint(2)
      dinner_sub_constraint.SetCoefficient(variables[(e, d, h)], 1)
      dinner_sub_constraint.SetCoefficient(variables[(e, d, h + 1)], 1)
      # here I want to disjunct dinner_sub_constraint for each iteration in one constraint
objective.SetMaximization()
result_status = solver.Solve()
...

So, I just want to disjunct all of dinner_sub_constraint and set it as single constraint.

It's might be a weired approach, but I have no idea how to provide two hours of dinner in row, so it's not acceptable to have two 1 hour dinners during one shift. Is there any way to disjunct conditions? Or my approach is wrong? Or should I use another library?

Upvotes: 2

Views: 725

Answers (1)

Laurent Perron
Laurent Perron

Reputation: 11014

You should use the CP-SAT solver. Look for shift_scheduling_sat.py in examples/python.

Upvotes: 4

Related Questions