CODEWITHSUNDEEP
pythonconstraintsvariable-assignmentor-toolscp-sat
Betcha
Betcha

Reputation: 77

OR-tools: Force partial assignments

I want to solve an assignment problem: putting items in containers.

Each container must contain:

  1. a certain amount of items (sizes)
  2. certain allowed items (possibilities)
  3. at least one subset of items within a predefined subsets list (obligations)

So far, I can easily program the 2 first constraints with OR-tools, but I'm struggling with the third one.

Here is my attempt with toy data (12 items and 3 containers).

from ortools.sat.python import cp_model


class SolutionPrinter(cp_model.CpSolverSolutionCallback):

    def __init__(self, x, containers, items):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__x = x
        self.containers = containers
        self.items = items

    def on_solution_callback(self):
        print({container: [item for item in self.items if self.BooleanValue(self.__x[container, item])] for container in self.containers})


# Amount of items per container (sums to the total amount of items)
sizes = [5, 3, 4]

# Which container the items can possibly belong to.
possibilities = [[False, True, False],
                 [True, False, False],
                 [True, False, True],
                 [True, True, True],
                 [True, False, True],
                 [True, False, False],
                 [True, False, False],
                 [True, True, False],
                 [False, False, True],
                 [False, True, True],
                 [False, False, True],
                 [True, True, True]]


# The containers must contain one of these subsets.
obligations = {0: [[1, 2, 3],  # container 0 must contain at least the items (1, 2, 3) or the items (5, 6, 7).
                   [5, 6, 7]],
               1: [],          # container 1 does not have such constraint
               2: [[2, 3, 4],
                   [8, 9],
                   [9, 10, 11]]}


num_containers = len(sizes)
num_items = sum(sizes)
model = cp_model.CpModel()

# Variables
x = {}
for container in range(num_containers):
    for item in range(num_items):
        x[container, item] = model.NewBoolVar(f"x[{container},{item}]") if possibilities[item][container] else False

# Constraints
for item in range(num_items):
    model.AddExactlyOne(x[container, item] for container in range(num_containers))

for container in range(num_containers):
    model.Add(sum(x[container, item] for item in range(num_items)) == sizes[container])


# TODO: 3rd constraint

solver = cp_model.CpSolver()
solution_printer = SolutionPrinter(x, range(num_containers), range(num_items))
solver.parameters.enumerate_all_solutions = True
status = solver.Solve(model, solution_printer)

Expected solutions:

{0: [1, 4, 5, 6, 7], 1: [0, 3, 11], 2: [2, 8, 9, 10]}
{0: [1, 2, 5, 6, 7], 1: [0, 3, 11], 2: [4, 8, 9, 10]}
{0: [1, 2, 3, 5, 6], 1: [0, 7, 11], 2: [4, 8, 9, 10]}

I need to generate all the possible solutions.

Filtering out solutions that do not respect the 3rd constraint afterwards is not an option.

Upvotes: 0

Views: 124

Answers (1)

Betcha
Betcha

Reputation: 77

I'm not 100% sure that it is correct or optimal performance-wise, but it looks like the 3rd constraint could be handled like this:

for container, container_obligations in obligations.items():
    if not container_obligations:
        continue
    var_obligations = []
    for index, container_obligation in enumerate(container_obligations):
        var_obligation = model.NewBoolVar(f"obligation_{container}_{index}")
        items = [x[container, item] for item in container_obligation]
        model.AddBoolAnd(items).OnlyEnforceIf(var_obligation)
        model.AddBoolOr([var_obligation]).OnlyEnforceIf(items)
        var_obligations.append(var_obligation)
    model.AddBoolOr(var_obligations)

Upvotes: 0

Related Questions