Algorithm for resolving conflicts with overlapping choices

Question

I have a computational problem where I have a set of tags that can be given away exactly once, and a number of items that each have a set of possible choices of tags that they can accept. I need to assign the tags in such a way that each item gets a tag whenever there is a solution to the problem.

To give a specific example, if I had a dictionary like this:

options = {
  'a': [1],
  'b': [2, 3],
  'c': [1, 2]
}

..then the solution would be:

 {'a': 1, 'b': 3, 'c': 2}

I will also need to be able to expand the problem to handle multiple constraints, e.g.

[1], ['A', 'B']         # -> (1, A) or (1, B)
[1, 2, 3], ['A', 'C']   # -> (3, C)
[1, 2], ['A', 'C']      # -> (2, A) or (2, B)

I have tried to come up with workable solutions based on a priority queue for the simple case, but that completely falls apart with multiple constraints. I could brute-force a solution using itertools.permutations, but I'd prefer an efficient implementation. Is there any known algorithm that might be applicable to this problem?

Answer 1

Formally, what you have in the example is a simple constraint satisfaction problem with three variables ['a', 'b', 'c'], each with a finite domain of integers and the "all-distinct" constraint.

Backtracking search with appropriate heuristics can solve this type of problems fairly quickly in practice. E.g.

def backtracking(domains):
    if any(len(dom) == 0 for var, dom in domains.iteritems()):
        return None
    if all(len(dom) == 1 for var, dom in domains.iteritems()):
        return domains

    # minimum remaining values heuristic: process variables with few possible
    # values first (fail-first strategy)
    order = sorted(domains.iteritems(), key=lambda (var, dom): len(dom))
    for var, dom in order:
        if len(dom) == 1:
            continue

        for value in list(dom):
            doms = {v: d - {value} for v, d in domains.iteritems()
                                   if v != var}
            doms[var] = {value}

            solution = backtracking(doms)
            if solution is not None:
                return solution

print(backtracking({v: set(d) for v, d in options.iteritems()}))

Answer 2

I would use backtracking to resolve this problem. Depending on the constraints if a greedy algorithm can be implementing, choosing 1 tag at a time to achieve global optimum

Answer 3

You do not have to implement a whole backtracking system just to resolve this problem. Many researchers already built systems and modelling languages to facilitate this kind of problem solving.

Your problem is a very classic Constraint Satisfaction Problem where we have the AllDifferent Constraint. I propose to you to use a high level modelling language like minizinc (http://www.minizinc.org/) and you'll see by yourself the difference. Here a simple model (for your problem) written in this format :

include "globals.mzn";
var {1} : a;
var {2,3} : b;
var {1,2} : c;
constraint alldifferent([a,b,c]);

solve  satisfy;

output ["a :  ", show(a), "\n" ,
        "b :  ", show(b), "\n" ,
        "c :  ", show(c), "\n" ];

If this is your first time using minizinc, you can start with the latest tutorial here.

Answer 4

It is really a very basic AllDifferent Constraint. If interested in python, using https://pypi.python.org/pypi/python-constraint

problem = Problem()
problem.addVariable("a", [1, 2])
problem.addVariable( "b", [2, 3])
problem.addVariable("c", [1, 2])
problem.addConstraint(AllDifferentConstraint())
print problem.getSolution()

(will give you first one found if exists or

print sorted(sorted(x.items()) for x in problem.getSolutions())

will give all solutions)