Parrainage

Usage:

Deux fichiers situé dans le même repertoire que cette feuille:

parrains.csv
filleuls.csv

Les fichiers doivent être au format CSV.

parrains.csv
- NomPrénom, Option, Primant, GroupeTutorat
filleuls.csv
- NomPrénom, Option, Primant, GroupeTutorat

Le programme calcule une affectation et l'écrit dans le fichier parrainage.csv.

Nom des fichiers Les noms des fichiers sont définis par les variables suivantes.



In [ ]:

    
# Nom de fichiers

fichierParrain = "parrains.csv"
fichierFilleul = "filleuls.csv"

fichierResultat = "parrainage.csv"



In [ ]:

    
# Imports

import csv
import glob

import pulp # LP
# pulp.pulpTestAll() # Test

Données



In [ ]:

    
def fetch_row_parrain(row, line, file):
    """
    Renvoie une ligne de type `parrain`
    """
    try:
        return row[0], [row[1], row[2], row[3]]
    except:
        print("Erreur de lecture fichier {}, ligne: {}".format(file, line))
        return []

def fetch_row_filleul(row, line, file):
    """
    Renvoie une ligne de type `filleul`
    """
    try:
        return row[0], [row[1], row[2], row[3]]
    except:
        print("Erreur de lecture fichier {}, ligne: {}".format(file, line))
        return []



In [ ]:

    
def fetch_row(row, line, file, category):
    """
    Renvoie une ligne sous forme d'un tableau
    
    Input:
        - row: ligne
        - line: numéro de la ligne dans le fichier
        - file: nom du fichier
        - category: `parrain` ou `filleul`
        
    Output:
        - un tableau
    """
    if category == "parrain":
        return fetch_row_parrain(row, line, file)
    elif category == "filleul":
        return fetch_row_filleul(row, line, file)
    else:
        raise Exception("Un fichier doit être de type `parrain` ou `filleul`")
        
def fetch_from_file(file, category):
    """
    Importe un fichier cvs dans un dictionnaire
    
    Input:
        - file: nom du fichier
        - category: `parrain` ou `filleul`
    """
    data = dict()
    
    with open (file, 'r') as csv_file:
        spamreader = csv.reader(csv_file, delimiter=';', skipinitialspace=True)

        for row in spamreader:    
            # Fetch line
            line = fetch_row(row, spamreader.line_num, file, category)
            if line == []: # Si erreur de lecture, passer au suivant
                continue
            if line[0] in data:
                print("Doublon {}, dans le fichier {}".format(line[0], file))
            else:
                data[line[0]] = line[1]
    return data



In [ ]:

    
dataParrains = fetch_from_file(fichierParrain, "parrain")
dataFilleuls = fetch_from_file(fichierFilleul, "filleul")

# On s'assure que les tables construites ne sont pas vides...
assert(len(dataParrains) > 0)
assert(len(dataFilleuls) > 0)

Programmation linéaire

Objectif

Recherche d'un matching optimal entre une liste de parrains et une liste de filleuls. Les pénalités sont les suivantes (voir la fonction matching)

Default: 1
Primant / Non-primant: +2
Option différente: +7
Tuteur + Parrain: + 10

Contraintes

Chaque filleul doit avoir exactement 1 parrain
Chaque parrain a au plus 5 filleuls

Limitations:

Pas de gestion des doublons, attention à ne pas avoir deux entrées avec même NomPrénom (première colonne identique)



In [ ]:

    
def matching(s, t):
    """
    Renvoie une note de compatibilité entre `s` et `t`.
    
    Plus la note est élevée, moins `s` et `t` sont compatibles.
    """
    res = 1
    if (s[0] != t[0]): # Option
        res += 7
    if (s[1] != t[1]): # Primant
        res += 2
    if (s[2] == t[2]): # Tutorat
        res += 10
    return res

Variables et Objectif



In [ ]:

    
arrow_set = [(s, t) for s in dataParrains for t in dataFilleuls]
assert(len(arrow_set) == len(dataParrains) * len(dataFilleuls))

# Variables
print("Variables...")
arrows = pulp.LpVariable.dicts('affectation', arrow_set, lowBound = 0, upBound = 1, cat = pulp.LpInteger)

# Modèle
print("Modèle...")
model = pulp.LpProblem("Parrainage", pulp.LpMinimize)

# Objectif
print("Objectif...")
model.setObjective(pulp.lpSum([matching(dataParrains[s], dataFilleuls[t]) * arrows[(s, t)]
             for (s, t) in arrow_set]))

Contraintes



In [ ]:

    
# Au plus 4 filleuls par parrain
for s in dataParrains:
    model.addConstraint(pulp.lpSum(arrows[(s, t)] for t in dataFilleuls) <= 4)

# Exactement 1 parrain
for t in dataFilleuls:
    model.addConstraint(pulp.lpSum(arrows[(s, t)] for s in dataParrains) == 1)

Résolution



In [ ]:

    
print(model.solve())

parrainage = [a for a in arrow_set if arrows[a].value() == 1]

Parrainage



In [ ]:

    
# Écrit la solution dans `fichierResultat`

with open(fichierResultat, 'w') as csv_file:
    writer = csv.writer(csv_file)
    writer.writerows(parrainage)

# Afficher la solution ici

# print("Parrain -> Filleul\n")
# for x in parrainage:
#     print("{} -> {}".format(x[0], x[1]))



In [ ]: