Saltar a contenido

Continuación de la línea de cómputo de reductos: ideas priorizadas

Documento para discusión con asesores. Fecha: 2026-11-16. Nada de lo que sigue está decidido.

Punto de partida

El cómputo de todos los reductos sobre la matriz básica es el mismo problema que la enumeración de minimal hitting sets (dualización de hipergrafos). Hay tres comunidades trabajando en él y casi no se citan entre sí:

  • Testores y reductos: fast-BR, fast-CT_EXT, GCreduct, YYC, RoPM, RegularSearch.
  • Minimal hitting sets: MMCS y RS (Murakami y Uno), HTC-BDD (Toda), entre unos veinte algoritmos.
  • Perfilado de datos (HPI Potsdam): HPIValid, basado en MMCS, para unique column combinations.

El survey de Gainer-Dewar y Vera-Licona (SIAM J. Discrete Math., 2017) lista 22 algoritmos de hitting sets. Ninguno de la familia de testores aparece en la parte del texto que pude revisar (la sección de resultados quedó sin leer). En sentido inverso, no encontré ningún artículo de testores o reductos que se compare contra MMCS o RS. Esa ausencia es resultado de búsqueda, no una demostración de que no exista.

Evidencia preliminar obtenida esta semana

Se recuperaron los paquetes de replicación publicados en ccc.inaoep.mx/~ariel/ (GCreduct, MinReduct, CTBRES, CTHW) y se ejecutaron los JAR originales sin recompilar.

El orden de las columnas cambia el trabajo en órdenes de magnitud. Quince permutaciones aleatorias solo de columnas, candidatos evaluados (mínimo a máximo):

Matriz GCreduct Razón fast-BR Razón
soybean (33x35) 7.5 M a 94.1 M 12.5 0.58 M a 1.37 M 2.4
anneal (62x38) 0.65 M a 3.09 M 4.7 0.16 M a 0.25 M 1.5
MED (26x36) 395 a 41.9 M 106 000 17.5 K a 25.9 M 1 480

Permutando solo filas, fast-BR no cambia en ninguna de las tres matrices. GCreduct tampoco cambia en soybean y anneal, pero en MED va de 441 a 28.8 M candidatos. Interpretación probable, sin verificar en el código: el desempate al elegir la fila con menos unos depende del orden de entrada.

Limitaciones: son tres matrices pequeñas, se mide candidatos y no tiempo, los JAR ya aplican su propio arreglo interno, y MED es un caso extremo con solo 3 reductos.

Ideas por prioridad

1. Marco de ejecución reproducible y archivo histórico

Habilita todo lo demás; no es un artículo fuerte por sí solo.

  • Cada algoritmo como ejecutable (JAR o binario nativo) con contrato común: entra una matriz básica, sale JSON con tiempo, candidatos evaluados y el conjunto de reductos.
  • Python orquesta, valida que todos los algoritmos devuelvan el mismo conjunto, y grafica. Ejecutable en Colab.
  • Dos repositorios: uno de preservación con los paquetes tal como se publicaron, otro para la investigación nueva.
  • Justificación directa: el código actual solo imprime conteos, lo que impide validar que dos algoritmos devuelvan el mismo conjunto. Además, el enlace MRvsMiLIT ya devuelve 404.
  • Corrección a la idea original: Python puro no sirve para medir tiempos en este problema. Python coordina; los núcleos siguen en Java o C.
  • Riesgo: comparar Java contra C mezcla lenguaje con algoritmo. Se mitiga reportando contadores de operaciones y portando los finalistas a un mismo lenguaje.

2. Impacto del ordenamiento de filas y columnas

Mejor candidato a primer artículo.

  • La tesis fija un solo arreglo: fila con menos unos arriba y sus columnas a la izquierda. El orden del resto queda libre, y la evidencia preliminar muestra que importa mucho.
  • Preguntas: qué órdenes estáticos funcionan mejor (frecuencia, contribución, densidad por columna), si un orden dinámico por nodo compensa su costo, y si el mejor orden depende del algoritmo.
  • Antecedentes a citar: tesis de Hörmann (KIT) sobre orden de vértices en MMCS, tesis de Lischeid (HPI) sobre orden de atributos, y la regla de desempate de HPIValid. En la familia de testores no encontré estudio dedicado.
  • Costo bajo: usa los algoritmos y matrices que ya existen.

3. Comparación cruzada con algoritmos de minimal hitting sets

Mayor impacto potencial; puede ir dentro del artículo de la idea 2 o como artículo propio.

  • Ejecutar MMCS y RS (código público de Uno) junto a GCreduct, fast-BR, fast-CT_EXT y, si se consigue código, RoPM y RegularSearch, sobre las mismas matrices.
  • Resultado posible e incómodo: que MMCS o RS dominen. Sería igualmente publicable y redefiniría contra qué hay que compararse.
  • Resultado alternativo: que la ventaja dependa de la densidad, como ya ocurre entre GCreduct y fast-BR.

4. Estado del arte experimental sobre estrategias de poda

  • Taxonomía común de podas en las tres comunidades: contribución, eliminación de brechas, exclusión, reducción recursiva de la matriz, condición de crítico en MMCS.
  • Más sólido como survey experimental apoyado en el marco de la idea 1 que como revisión narrativa.
  • Trabajo posterior a la tesis que hay que cubrir: RoPM (2021), MiLIT para testores irreducibles de longitud mínima (IEEE Access, 2020), RegularSearch (Information Sciences, 2023; solo vi el resumen de búsqueda), CC-GEAC (Mathematics, 2024) y RCC-MAS (Machine Learning, 2025) para constructos, y un preprint de 2026 que prueba que MMCS no es output-polynomial.

5. Selección automática de algoritmo y de orden

  • El capítulo 5 de la tesis ya da una regla por densidad (GCreduct por debajo de 0.36, fast-BR entre 0.36 y 0.66). La extensión natural es un selector basado en rasgos de la matriz que elija algoritmo y orden.
  • Depende de los datos que produzcan las ideas 2 y 3.

6. Aceleración en GPU, acotada a reductos más cortos

  • Ya existen: hill-climbing en CUDA de Piza-Dávila y otros (2017, heurístico, devuelve un subconjunto), DABATestors (2021) y la búsqueda exhaustiva en clusters de GPU de Carastan-Santos (2017, 2019).
  • La enumeración completa con poda es un árbol irregular con muchas ramas; encaja mal en GPU. Esto es una valoración mía, no un resultado medido.
  • Nicho que sí parece viable: MinReduct. Candidatos acotados por cardinalidad y evaluación por lotes. No encontré un algoritmo exacto en GPU para reductos más cortos.
  • Riesgo alto y costo alto. Conviene decidirlo después de ver dónde está el cuello de botella real.

7. Exploratorias

  • Matriz parcial: HPIValid calcula los conjuntos de diferencia bajo demanda y evita construir la matriz de discernibilidad completa. Podría trasladarse a reductos.
  • Constructos: línea activa en 2024 y 2025; las podas de GCreduct parecen aplicables.

Qué se descarta o se reformula

  • Marco en Python puro: reformulado como orquestador (idea 1).
  • GPU para enumeración completa: descartado como primer objetivo; queda la versión acotada (idea 6).
  • Estado del arte narrativo: reformulado como survey experimental (idea 4).

Preguntas para los asesores

  1. ¿Hay acuerdo para republicar los paquetes históricos con licencia explícita y DOI? No encontré archivo de licencia en ellos.
  2. El código de MiLIT (Piza-Dávila y otros, IEEE Access 2020) es de otro grupo: ¿se puede redistribuir? ¿Se conserva el paquete MRvsMiLIT?
  3. ¿Hay código disponible de RoPM y RegularSearch?
  4. ¿Las ideas 2 y 3 van en un solo artículo o en dos?
  5. ¿Existe alguna comparación previa contra MMCS o RS que no haya encontrado?

Estado del material

  • legacy/ (377 MB, fuera de control de versiones): repositorios java_inaoe, latex_inaoe, latex, PDF de la tesis y los cuatro paquetes de INAOE.
  • Recuperado: fuentes Java de GCreduct, fast-BR, fast-CT_EXT, MinReduct y MiLIT (variantes NC y PFRC); 232 archivos VHDL de la plataforma FPGA; 500 matrices sintéticas 2000x30; datasets y matrices básicas de UCI.
  • No recuperado: paquete MRvsMiLIT, fuente de sRGA y de CAMARDF (solo binarios).

Referencias

  • Gainer-Dewar y Vera-Licona, The minimal hitting set generation problem: algorithms and computation: https://arxiv.org/abs/1601.02939
  • Repositorio de dualización de Uno (MMCS, RS): https://research.nii.ac.jp/~uno/dualization.html
  • Birnick y otros, HPIValid, PVLDB 2020: https://hpi.de/oldsite/fileadmin/user_upload/fachgebiete/naumann/publications/PDFs/2020_birnick_hitting.pdf
  • Hörmann, tesis de licenciatura, KIT: https://scale.iti.kit.edu/_media/resources/theses/ba_bennet_hoermann.pdf
  • Lischeid, tesis de licenciatura, HPI: https://hpi.de/fileadmin/user_upload/fachgebiete/friedrich/documents/Schirneck/Lischeid_bachelors_thesis.pdf
  • Minimal-to-Maximal Conversion Search Is Not Output-Polynomial: https://arxiv.org/abs/2608.02159
  • RoPM: https://www.researchgate.net/publication/354565660
  • RegularSearch: https://www.sciencedirect.com/science/article/abs/pii/S0020025523012501
  • Testores irreducibles de longitud mínima: https://rei.iteso.mx/items/5c69c665-2dad-47db-85bf-8048abe033f5/full
  • CC-GEAC: https://doi.org/10.3390/math12010090
  • RCC-MAS: https://mlanthology.org/mlj/2025/gonzalezdiaz2025mlj-rccmas
  • Hill-climbing en CUDA para testores irreducibles: https://www.bohrium.com/paper-details/a-cuda-based-hill-climbing-algorithm-to-find-irreducible-testors-from-a-training-matrix/813130730421878784-2594
  • DABATestors: https://rcs.cic.ipn.mx/2021_150_7/
  • Carastan-Santos y otros, hitting set en CPU-GPU-MIC: https://sol.sbc.org.br/index.php/sscad/article/view/250