Resumen Técnico: Un Análisis de las Formulaciones de Programación Lineal Entera (Mixta) para el Problema de Agrupación Máximamente Diversa

Definición del Problema

El Problema de Agrupación Máximamente Diversa (MDGP, por sus siglas en inglés) es un problema clásico de optimización combinatoria NP-duro. Dado un conjunto de elementos $I$ y un conjunto de grupos $G$, el objetivo es asignar cada elemento a exactamente un grupo de tal manera que la diversidad total dentro de los grupos se maximice. La diversidad de un par de elementos $(i, j)$ se define mediante un parámetro $d_{ij} \geq 0$. La diversidad total es la suma de todas las diversidades por pares de los elementos asignados al mismo grupo. El problema está sujeto a restricciones sobre el número de elementos por grupo, definidas por límites inferiores $l_g$ y límites superiores $u_g$ para cada grupo $g \in G$.

Las aplicaciones para el MDGP incluyen la asignación de estudiantes a grupos o cursos, la formación de equipos de proyecto, la creación de grupos de revisores y la programación de exámenes finales. Aunque los enfoques heurísticos son comunes en la literatura, los métodos de solución exacta se han limitado históricamente a instancias de problemas pequeños.

Metodología y Formulaciones de Modelos

El artículo analiza y compara cuatro formulaciones distintas de programación lineal entera (mixta) [(mixed-)integer linear programming (MILP)]:

1. Formulación Estándar (Weitz y Lakshminarayanan, 1998):

   • Variables: Variables binarias $x_{ig}$ que indican si el elemento $i$ es asignado al grupo $g$. Variables binarias auxiliares $y_{ijg}$ que representan si los elementos $i$ y $j$ están ambos en el grupo $g$.
   • Mecanismo: La función objetivo se linealiza mediante restricciones $y_{ijg} \leq x_{ig}$ y $y_{ijg} \leq x_{jg}$.
   • Debilidad: La relajación de Programación Lineal (LP) es débil. En la relajación, los elementos pueden ser asignados de forma fraccionaria a todos los grupos ($x_{ig} = 1/|G|$), lo que provoca que el valor de la función objetivo sume todos los pares posibles de $d_{ij}$, lo cual es un límite superior inalcanzable para las soluciones enteras factibles.

2. Formulación de Papenberg y Klau (2021):

   • Variables: Variables binarias $z_{ij}$ que indican si los elementos $i$ y $j$ están asignados al mismo grupo, sin especificar cuál.
   • Mecanismo: Utiliza restricciones de transitividad (por ejemplo, $-z_{ij} + z_{ik} + z_{jk} \leq 1$) para asegurar la consistencia y una restricción que asegura que cada elemento se agrupa con exactamente $|I|/|G| - 1$ otros elementos.
   • Fortaleza: El ramificado (branching) ocurre en las asignaciones de elemento-elemento ($z_{ij}$), las cuales influyen directamente en la función objetivo. La relajación de LP es significativamente más fuerte porque las restricciones limitan el número de pares por elemento al tamaño del grupo.
   • Limitación: Diseñada originalmente solo para grupos de igual tamaño.

3. Formulación Combinada:

   • Mecanismo: Combina la formulación estándar con el enfoque de Papenberg y Klau mediante el vínculo $z_{ij} = \sum_{g \in G} y_{ijg}$.
   • Contribución: Añade restricciones de transitividad al modelo estándar y adapta las restricciones de tamaño de grupo para tamaños variables. El artículo demuestra que, para grupos de igual tamaño, esta formulación tiene una relajación de LP al menos tan fuerte como la formulación de Papenberg y Klau.

4. Formulación Adaptada de Papenberg y Klau (para Tamaños de Grupo Variables):

   • Mecanismo: Extiende el modelo de Papenberg y Klau para manejar tamaños de grupo variables ($l_g \neq u_g$) mediante la introducción de un "elemento ficticio" (dummy item) para cada grupo.
   • Variables: Los elementos se asignan a elementos ficticios (que representan grupos) a través de $z_{i, \text{dummy}}$.
   • Restricciones: Las restricciones de transitividad se aplican a todos los elementos, incluyendo los ficticios. Las restricciones aseguran que cada elemento real sea asignado a exactamente un grupo fictivo, y que el tamaño del clúster alrededor de cada elemento fictivo cumpla con $l_g$ y $u_g$.

Principales Contribuciones

• Análisis Comparativo: El artículo proporciona una comparación teórica y empírica de la formulación estándar de asignación de elemento-grupo frente a la formulación de asignación de elemento-elemento.
• Perspectiva Teórica: Demuestra que el ramificado en las variables de asignación de elemento-elemento ($z_{ij}$) es superior al ramificado en las variables de asignación de elemento-grupo ($x_{ig}$), ya que la primera restringe directamente el valor de la función objetivo y produce una relajación de LP más ajustada.
• Nuevas Formulaciones: Se presentan dos nuevas formulaciones para manejar el caso general de tamaños de grupo variables, extendiendo la aplicabilidad de la lógica más fuerte de asignación de elemento-elemento.
• Ruptura de Simetría: El artículo discute y transfiere las restricciones de ruptura de simetría al caso general para la formulación estándar.

Resultados Computacionales

Se llevó a cabo un estudio computacional exhaustivo utilizando CPLEX 12.9 con instancias que van desde 10 a 30 elementos y 2 a 10 grupos. Se probaron tanto escenarios de grupos de igual tamaño como de tamaños variables.

• Calidad de la Relajación de LP: La formulación de Papenberg y Klau y sus adaptaciones produjeron consistentemente límites superiores significativamente más ajustados (brechas más pequeñas) en comparación con la formulación estándar. Las brechas de la relajación de LP de la formulación estándar fueron a menudo superiores al 100%, mientras que las de las formulaciones de elemento-elemento se mantuvieron mucho más bajas.
• Desempeño de Resolución:
  • Grupos de Igual Tamaño: La formulación de Papenberg y Klau resolvió casi todas las instancias a la optimalidad más rápido que la formulación estándar.
  • Tamaños de Grupo Variables: La formulación adaptada de Papenberg y Klau (Sección 3.4) fue la que mejor desempeño mostró, resolviendo instancias de hasta 30 elementos a la optimalidad o con brechas pequeñas dentro del límite de tiempo de 1800 segundos.
  • Formulación Estándar: Tuvo dificultades significativas, fallando a menudo en cerrar la brecha o en resolver instancias con más de 15 elementos dentro del límite de tiempo.
  • Formulación Combinada: Aunque es teóricamente fuerte, la formulación combinada no mostró una mejora sustancial en el desempeño respecto a la formulación estándar cuando se realiza el ramificado en las variables $x_{ig}$, lo que sugiere que las restricciones de transitividad por sí solas son insuficientes para superar la debilidad de la estrategia de ramificado de elemento-grupo.

Significado y Reivindicaciones

El artículo sostiene que el principal motor del desempeño superior de las nuevas formulaciones es la estrategia de ramificación (branching strategy). Al ramificar en las asignaciones de elemento-elemento en lugar de en las asignaciones de elemento-grupo, el optimizador puede podar el espacio de búsqueda de manera más efectiva debido a la relajación de LP más fuerte proporcionada por las restricciones de transitividad.

El estudio concluye que para el MDGP, especialmente en entornos con tamaños de grupo variables, la adaptación de la formulación de Papenberg y Klau es el enfoque exacto más efectivo disponible actualmente. Esta logra extender los beneficios de la lógica de asignación de elemento-elemento al caso general de restricciones de agrupación, superando las limitaciones de la formulación estándar de hace décadas. Los autores señalan que, aunque la formulación adaptada es la que mejor funciona, las instancias con tamaños de grupo variables siguen siendo más difíciles de resolver que las de tamaños iguales, debido probablemente a la mayor flexibilidad del espacio de soluciones.