CODEWITHSUNDEEP
or-toolsconstraint-programmingcp-sat
John
John

Reputation: 1828

How to maximize the number of "concordance pairs" in task allocations to days with ortools constraint programming

Suppose we have three ordered tasks [0, 1, 2] and two ordered days [0, 1] and we would like to allocate the three tasks to the two days.

Meanwhile, we would like to minimize the occurrance of discordance.

For example, if task 1 is allocated to day 1, then task 2 shall not be allocated to day 0.

There is an illustration: enter image description here

The code is presented here and it is pretty difficult to come up with the objective function:

from ortools.sat.python import cp_model

model = cp_model.CpModel()

# data
tasks = [0, 1, 2]
days = [0, 1]

all_possible_allocations = {
    (task, day)
    for task in tasks
    for day in days
}

# decision variables
allocation = {
    (task, day): model.NewBoolVar(f"task {task} --> day {task}")
    for (task, day) in all_possible_allocations
}

# constraints
for task in tasks:
    model.Add(sum(allocation[task, day] for day in days) == 1)

# objective
model.Minimize(1)

# solve
solver = cp_model.CpSolver()
status = solver.Solve(model=model)


# show results
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
    for task in tasks:
        for day in days:
            if solver.Value(allocation[task, day]):
                print(f'Task {task} --> Day {day}')
elif status == cp_model.INFEASIBLE:
    print("No optimal or feasible solution")

Upvotes: 0

Views: 49

Answers (1)

Laurent Perron
Laurent Perron

Reputation: 11064

small comments:

    model.Add(sum(allocation[task, day] for day in days) == 1)

could be

    model.AddExactlyOne(allocation[task, day] for day in days)

We can make a simple model.

  day_of_task_0 = model.NewIntVar(0, len(days))
  day_of_task_0 = model.NewIntVar(0, len(days))
  model.Add(day_of_task_1 == sum(allocation[1, day] * day for day in days))
  model.Add(day_of_task_2 == sum(allocation[2, day] * day for day in days))
  
  # You have a discordance if task2 is done before task1
  d1_2 = model.NewBoolVar('d1_2')
  model.Add(day_of_task_1 > day_of_task_2).OnlyEnforceIf(d1_2)
  model.Add(day_of_task_2 <= day_of_task_1).OnlyEnforceIf(d1_2.Not())

  # The objective tries to minimize the number of discordances.
  model.Minimize(d1_2)  # Only one currently.

Upvotes: 1

Related Questions