problema de satisfacción de restricción falta una restricción

Soy tutor de prácticas de laboratorio en la universidad, según los comentarios de los estudiantes del año pasado, queríamos que mi jefe y yo nos dirigiéramos a ellos. Mi jefe decidió escribir un script en C y elegí python (restricción de python) para tratar de resolver nuestro problema.

Informaciones

Hay 6 sesiones
Hay 4 roles
Hay 6 prácticas
Hay 32 estudiantes
Hay 4 estudiantes por equipo.

Problema:

Asigne a cada alumno a 4 roles, en 4 prácticas en 4 sesiones diferentes.

Restricciones:

Los estudiantes deben hacer un papel una vez
Los estudiantes deben hacer 4 prácticas diferentes de 6
Los estudiantes deben hacer solo una práctica por sesión
El estudiante debe encontrarse con el mismo compañero solo una vez

Plantillas:

Aquí está la plantilla que siento con los estudiantes, donde cada equipo está compuesto por 4 estudiantes, las posiciones [0, 1, 2 o 3] son roles asignados a ellos. Cada posición disponible está numerada del 1 al 128

[# Semester
   [ # Session
     [ # Practice/Team
1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12],
  [13, 14, 15, 16],
  [17, 18, 19, 20],
  [21, 22, 23, 24]],
 [[25, 26, 27, 28],
  [29, 30, 31, 32],
  [33, 34, 35, 36],
  [37, 38, 39, 40],
  [41, 42, 43, 44],
  [45, 46, 47, 48]],
 [[49, 50, 51, 52],
  [53, 54, 55, 56],
  [57, 58, 59, 60],
  [61, 62, 63, 64],
  [65, 66, 67, 68],
  [69, 70, 71, 72]],
 [[73, 74, 75, 76],
  [77, 78, 79, 80],
  [81, 82, 83, 84],
  [85, 86, 87, 88],
  [89, 90, 91, 92],
  [93, 94, 95, 96]],
 [[97, 98, 99, 100],
  [101, 102, 103, 104],
  [105, 106, 107, 108],
  [109, 110, 111, 112]],
 [[113, 114, 115, 116],
  [117, 118, 119, 120],
  [121, 122, 123, 124],
  [125, 126, 127, 128]]]

En otras palabras :

Esta es una sesión:

 [[1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12],
  [13, 14, 15, 16],
  [17, 18, 19, 20],
  [21, 22, 23, 24]],

Esos equipos hacen la misma práctica:

[
    [1, 2, 3, 4],
    [25, 26, 27, 28],
    [49, 50, 51, 52],
    [73, 74, 75, 76],
    [97, 98, 99, 100],
    [113, 114, 115, 116]
]

Esas posiciones hacen el mismo papel:

[
   1,
   5,
   9,
   13,
   17,
   21,
   25,
   ...
]

Lo que tengo hasta ahora:

Usando python-restriction pude validar las tres primeras restricciones:

Valid solution : False
            - sessions  : [True, True, True, True, True, True]
            - practices : [True, True, True, True, True, True]
            - roles     : [True, True, True, True]
            - teams     : [False, False, True, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, True, False, False, False, False, False]

Para aquellos que pueden ser interesantes, simplemente hago esto:

Para cada condición uso AllDifferentConstraint . Por ejemplo, para una sesión hago:

problem.addConstraint(AllDifferentConstraint(), [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24])

No puedo encontrar una manera de restringir al equipo, mi último intento semesterfue:

    def team_constraint(self, *semester):
        students = defaultdict(list)

        # get back each teams based on the format [# Semester [ #Session [# Practice/Team ... 
        teams = [list(semester[i:i+4]) for i in range(0, len(semester), 4)]

        # Update Students dict with all mate they work with
        for team in teams:
            for student in team:
                students[student] += [s for s in team if s != student]

        # Compute for each student if they meet someone more than once 
        dupli = []
        for student, mate in students.items():
            dupli.append(len(mate) - len(set(mate)))

        # Loosly constraint, if a student meet somone 0 or one time it's find
        if max(dupli) >= 2:
            print("Mate encounter more than one time", dupli, min(dupli) ,max(dupli))
            return False
        pprint(students)
        return True

Preguntas:

¿Es posible hacer lo que quiero para las condiciones del equipo? Lo que quiero decir es que no tengo idea si es posible asignar 12 compañeros a cada estudiante y cada uno de ellos se encuentra con el mismo compañero solo una vez.
Para la restricción del equipo, ¿me perdí un algoritmo más eficaz?
¿Algún pistón que pueda seguir?

python algorithm python-constraint Florian Bernard
fuente

¿Por qué son los dos últimos conjuntos de sesiones a la forma del (4, 4)lugar de (4, 6)como los otros?

r.ook

Es coincidir con el hecho de que este curso es solo un crédito y requiere mucho trabajo, por lo que mi jefe decide que los estudiantes solo deben hacer 4 prácticas. Entonces se nos ocurrió esto, tenemos 32 estudiantes, que deben hacer 4 prácticas (128 puestos).

Florian Bernard

Intentaría un enfoque aleatorio y de fuerza bruta. Simplemente haga una permutación en la que elija Sesión 1: Rol 1 Estudiante 1 Práctica 1 ... lo mismo con 2 a 4. Luego incremente por cada 6 sesiones, descarte a los estudiantes que ya conocieron. Lo mismo con al azar. ¿Por qué 128 posiciones y no uso por sesión 32 número de estudiantes como máximo en diferentes permutaciones? Tal vez en stackMath puedan decirte si esto es posible combinación / permutación

Cristo

Actualmente el método de fuerza bruta funciona, mi jefe volvió a mí con su guión y su trabajo realmente bien. Pero todavía quiero usar Python.

Florian Bernard

Respuestas:

La pregunta principal se respondería con algo como ...

   def person_works_with_different():
        # over all the sessions, each person works with each other person no more than once.
        # 'works with' means in 'same session team'
        for p in all_people:
            buddy_constraint = []
            for s in all_sessions:
                for g in all_teams:
                    p_list = [pv[k] for k in filter(lambda i: i[P] == p and i[S] == s and i[G] == g, pv)]
                    for o in all_people:
                        if o != p:  # other is not person
                            o_list = [self.pv[k] for k in filter(lambda i: i[self.P] == o and i[self.S] == s and i[self.G] == g, self.pv)]
                            tmp = model.NewBoolVar('')
                            buddy_constraint.append(tmp)
                            model.Add(sum(o_list) == sum(p_list)).OnlyEnforceIf(tmp)
                            # tmp is set only if o and p are in the same session/team
            # The number of times a student gets to take part is the number of roles.
            # The size of the group controlled by the number of roles
            model.Add(sum(buddy_constraint) = all_roles * (all_roles - 1))

Edición añadida

Ayer volví a ver tu problema (ciertamente no mucho, ya que tengo mucho trabajo por el momento) y ...

En primer lugar, veo que su entidad de "equipo" es más o menos lo que yo llamé una entidad de "acción", y en retrospectiva creo que "equipo" (o "grupo") era una mejor palabra para ello.

Si todavía encuentra difíciles las restricciones, le sugiero que las separe y trabaje en ellas individualmente, particularmente las restricciones de equipo / persona / sesión, seguidas de las restricciones de rol / tarea.

/ Agregado Editar

team: a gathering of 4 persons during a session
person (32): a participant of a team
session (6): time: eg, 8am -10am
role (4): what responsibility a person has in an action
task (6): type of action

A person does:
 0..1 action per session-group
 1 role per action
 1 task per action
 0..1 of each task
 1 of each role in an action
 4 persons in an action

A person meets each other person 0..1 times
An action requires exactly 4 people

Tuve un problema similar recientemente, y al final recurrí a las herramientas OR. https://developers.google.com/optimization/cp/cp_solver

En particular, eche un vistazo al problema de programación de enfermeras: https://developers.google.com/optimization/scheduling/employee_scheduling#nurse_scheduling

De todos modos, el problema no es demasiado complejo, por lo que tal vez usar un solucionador sería excesivo para usted.

Del mismo modo, para este tipo de problema puede ser mejor usar un dict con clave de tupla para contener sus variables, en lugar de listas anidadas:

{Equipo, Sesión, Persona: BoolVar}

La razón principal es que luego puede aplicar restricciones a través de filtros, lo cual es mucho más fácil que tener que hacer manipulaciones de listas anidadas, por ejemplo, para aplicar una restricción entre personas / equipos, puede hacerlo (donde la persona es el índice 2 y el equipo es el índice 0):

for p in all_persons:
    for t in all_teams:
        stuff = [b_vars[k] for k in filter(lambda i: i[2] == p and i[0] == t, b_vars)]
        model.Add(sum(stuff) == 4)  # persons per team == 4

Konchog
fuente

Gracias, ¿por el bucle que quisiste decir p for p in all_people?

Florian Bernard

Sí, lo siento 'Traduje' mis nombres a su modelo, pero estaba en el trabajo, así que fue un poco rápido.

Konchog

Además, la lista de correo es realmente de apoyo en las herramientas OR. Si necesita ayuda para modelar su problema, le indicarán un código de ejemplo o le darán una gran idea sobre cómo establecer restricciones de grupo / dependencia

Konchog

Lo siento, pero su solución principal es difícil de seguir, ¿de dónde viene el yo? ¿Y qué son las variables P, S y G? ¿Qué es pv? Gracias por tu ayuda.

Florian Bernard

Solo una idea de algoritmo de permutación, para cada iteración podría centrarse en uno de cada alumno o en una de cada sesión:

Session 1:
Roles
1,2,3,4
Students
1,2,3,4

(Note is 1st permutation 1234)

Sess 2 for student 1
Roles 1234
Students 5,1,7,6

Aquí el estudiante 2 toma lugar del estudiante 1 en la sesión 1 y continúa así

Roles 1234
St 2,5,6,7

Continuar con el alumno 1 S3 R 1234 St 10,9,1,8

S4
R 1234
St 11,12,13,1

Al final, elimina las interacciones para el alumno 1, como en las permutaciones para la próxima iteración, elimina la actual.

Es como un cubo de rubik.

Si puede codificar esto o conocer algún código con este algo, hágamelo saber.

Tal vez con las permutaciones de itertools

Las sesiones son más que prácticas, creo que no es tan relevante su número. Solo un grupo para tomar más cuando te quedas sin espacio o más espacio para la rotación. ¿Quizás podría simplificar el problema primero apuntando a 4 sesiones = prácticas?

Cristo
fuente