Pioneering Team Diversity with Constraint Programming

As a team leader within your organization, your role extends beyond the routine task assignments. Your mission is to foster diversity within project teams, a strategic imperative for success, and you're about to employ the precision of mathematical optimization and constraint programming to achieve this goal.

You're entrusted with the task of crafting groups of four individuals, each carefully curated for a unique blend of skills and expertise, ensuring that no team member is confined to a single type of assignment. This intricate task isn't solely based on intuition; it's underpinned by mathematical optimization principles that help you create teams that excel in synergy.

The organizational chart, the blueprint of your team's composition, holds the key to eligibility. Your objective: assemble teams that harmoniously balance horizontal and vertical skills, employing constraint programming to ensure every project benefits from a diverse set of capabilities. Picture it as a jigsaw puzzle, where two members exhibit matching horizontal proficiency, and two others boast complementary vertical skills. Or, think of it as an engaging challenge, akin to crafting rectangles, a creative twist introduced by your HR team to infuse a dash of fun into the process.

You can see some possible teams as follows:

Each team member can potentially be assigned to any of the four different tasks, namely, report writing, analysis, coding and R&D.

The question is how to do it ? Let's go to the mathematical world and try to solve it there.

Consider a m by n board. There are mn points on the grid (our staffs). The goal is to paint the points in a way that no monochromatic rectangles can be selected (not all members of a single team have the same color).

To put it differently, there are no axis-aligned rectangles with all four corner grid points having the same color.

I think the problem description is clear enough. Let's formulate it mathematically:

1- Each point should be assigned to only one color

2- For each Rectangle R(p1,p2,p3,p4) and color c , max three of the points can be assigned to color c.

3- Up,c is a binary variable which assigns p to c (if it is 1).

The OR-Tools code will be as follows:

First we need to import the required packages:

from ortools.sat.python import cp_model
import numpy as np
import matplotlib.pyplot as plt
import random        

class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback):
    """Print intermediate solutions."""
    def __init__(self, variables,points):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__variables = variables
        self.__solution_count = 0
        self.__dic = points
    def on_solution_callback(self):
        self.__solution_count += 1
        print('-------------------------')
        KOLOR= ['r','dodgerblue','g','k','gold','navy']
        random.shuffle(KOLOR)
        for (p,c) in self.__variables:
            if self.Value(self.__variables[p,c]) >0:
                [i,j] = self.__dic[p]
                plt.scatter(i,j , c=KOLOR[c-1], s=200)
        maxi= max([self.__dic[p][0] for p in self.__dic ])
        maxj= max([self.__dic[p][1] for p in self.__dic ])
        plt.xticks(range(1,maxi+1),fontweight='bold')
        plt.yticks(range(1,maxj+1),fontweight='bold')     
        plt.savefig(f'Vertex.png', format='png', dpi=500)

        
    def solution_count(self):
        return self.__solution_count

def SearchForAllSolutionsSampleSat(N,M,C):
    # Creates the model.
    model = cp_model.CpModel()

    # Creates the variables.
    rows = range(1,N+1)
    cols = range(1,M+1)
    colors = range(1,1+C)
    
    points = {}
    counter = 0 
    for i in rows:
        for j in cols:
            counter+=1
            points[counter] = [i,j]
  
    x = {(p,c):model.NewBoolVar(f"x_{p}_{c}") for p in points for c in colors}
    
    for p in points:
        model.AddExactlyOne([x[p,c] for c in colors])
    dic= {(points[p][0],points[p][1]):p for p in points}
    
    keep = []
    for p1 in points:
        for p2 in points:
            [i,j] =points[p1]
            [m,n] =points[p2]
            if p1!=p2 and m<i and n<j:
                keep.append([dic[m,n], dic[m,j] ,dic[i,n] , dic[i,j]])
            elif p1!=p2 and m>i and n>j:
                keep.append([dic[i,j],dic[i,n],dic[m,j] ,dic[m,n]])

    for c in colors:
        for K in keep:
            expression = [x[p,c] for p in K]
            model.Add(sum(expression) <= 3)
    
    # Create a solver and solve.
    solver = cp_model.CpSolver()
    solution_printer = VarArraySolutionPrinter(x,points)
    # Enumerate all solutions.
    solver.parameters.enumerate_all_solutions = False
    # Solve.
    
    status = solver.Solve(model, solution_printer)
    #status = solver.Solve(model)

    print(f"Status = {solver.StatusName(status)}")
    print(f"Number of solutions found: {solution_printer.solution_count()}")

SearchForAllSolutionsSampleSat(10,10,4)        

Results:

It is evident that any set of four points, forming the vertices of a rectangle, does not share the same color (are not monochrome).

Some other applications:

1. Frequency Assignment in Telecommunications: In wireless communication and frequency assignment problems, graph coloring is applied to allocate frequencies or channels to transmitters while avoiding interference.
2. Timetable and Classroom Scheduling: Educational institutions use graph coloring to create conflict-free timetables and classroom assignments, ensuring that classes and exams do not overlap.
3. Circuit Board Design: In electronic design automation, constraint programming-based graph coloring helps allocate pins and wires on circuit boards while avoiding signal crosstalk.
4. Map Coloring: In cartography and geospatial analysis, graph coloring is used to solve map coloring problems. This can help create maps where adjacent regions have distinct colors, such as in political districting or territory demarcation.
5. Network Routing: In computer networks, graph coloring is employed in the optimization of network routing protocols, ensuring that data packets do not collide or interfere with each other.
6. Sports Tournament Scheduling: For sports leagues and tournaments, constraint programming can be used to schedule matches, ensuring that teams do not have conflicting schedules.
7. Channel Allocation in Wireless Networks: In cellular networks and Wi-Fi, graph coloring can be applied to allocate communication channels to mobile devices or access points.
8. Resource Allocation in Project Management: In project management, especially in multi-project environments, graph coloring techniques can assist in allocating resources, such as personnel and equipment, to different projects to meet project goals and constraints.

The code developed in this episode is available on the github.

Thanks for sharing.