Saltar a contenido

MMCS: por qué es más rápido, y valoración de un artículo de framework

Documento interno. Fecha: 2026-11-17. Etiqueto como hecho lo que sale del código o de una medición, y como inferencia lo que es interpretación mía.

1. MMCS en una página

MMCS (Minimal-to-Maximal Conversion Search, Murakami y Uno, 2014) enumera los minimal hitting sets de un hipergrafo. En nuestro lenguaje: las filas de la matriz básica son las hiperaristas y las columnas son los vértices. Un reducto es un conjunto de columnas que toca todas las filas y del que no se puede quitar ninguna.

Mantiene tres cosas en cada nodo de la búsqueda:

  • S: las columnas elegidas.
  • uncov(S): las filas que S todavía no toca.
  • crit(v, S): para cada columna v de S, las filas que toca solo v. Si una columna se queda sin filas críticas, sobra, y S ya no puede crecer hasta un reducto.

El paso recursivo:

  1. Si uncov(S) está vacío, S es un reducto: se reporta.
  2. Se elige la fila no cubierta con menos columnas candidatas (la fila pivote).
  3. Solo se ramifica sobre las columnas de esa fila. Al probar la i-ésima, las i−1 anteriores se sacan de las candidatas para ese subárbol, así no se repite ningún conjunto.
  4. Se descarta S+v si alguna columna de S pierde sus filas críticas.

Todo se actualiza de forma incremental: uncov(S+v) = uncov(S) − Occ(v), crit(v, S+v) = uncov(S) ∩ Occ(v) y crit(u, S+v) = crit(u, S) − Occ(v). En java/src/mhs/Mmcs.java son operaciones de bits sobre filas.

2. Qué tiene MMCS que GCreduct y fast-BR no tienen

Lo que comparten (hecho, del código)

  • La prueba de filas críticas ya está en fast-BR. La "exclusión" de fast-BR (FastBR.extraerTT, condición #2) calcula la máscara de compatibilidad (filas cubiertas por exactamente una columna) y descarta el candidato si alguna columna elegida no tiene ninguna fila en esa máscara. Eso es exactamente la prueba de crit de MMCS. GCreduct no la tiene: solo pide que la columna nueva contribuya, y comprueba la tipicidad cuando ya encontró un testor.
  • La fila pivote ya está en la tesis, pero solo en la raíz. El arreglo de la tesis pone arriba la fila con menos unos y sus columnas a la izquierda. GCreduct y fast-BR terminan cuando el primer atributo del candidato ya no tiene un 1 en esa fila (firstRowOnes, posUltColumUnitaria). Es la regla de MMCS aplicada una sola vez, al inicio.

Lo que MMCS añade

Aplica la regla de la fila pivote en cada nodo, con la fila que en ese momento tiene menos candidatas. Después de la raíz, GCreduct y fast-BR recorren las columnas en orden lexicográfico: prueban toda columna posterior aunque no toque la fila no cubierta más difícil. Un callejón sin salida se descubre tarde. MMCS en cambio obliga a cada rama a cubrir ya la fila más restringida. Si una fila se queda sin candidatas, el nodo se descarta de inmediato.

Es la misma idea que la heurística de "variable más restringida primero" en búsqueda con restricciones.

La ablación (hecho, medición)

experiments/baseline/why_mmcs.py. Una escalera de programas en la que cada peldaño añade una sola idea. Métrica: trabajo por reducto (candidatos en GCreduct y fast-BR, nodos en MMCS y SHD), límite de 30 s, 12 matrices. Los conteos de reductos coinciden en todas las corridas que terminaron.

Matriz Dens. Reductos GCreduct fast-BR Sin pivote (SHD 9D) MMCS, primera fila MMCS MMCS de Uno RS de Uno
MED 0.03 3 9.1 M 4.7 M t/o 13.3 9.7 8.7 12.3
soybean 0.20 570 41 451 3 189 t/o 11.6 1.4 0.4 9.7
biodeg 0.08 256 29 328 14 282 t/o 8.9 1.8 0.8 5.1
anneal 0.13 313 1 147 827 t/o 5.3 2.1 1.0 2.4
heart-c 0.49 97 11.1 9.3 28.3 3.3 1.7 0.7 1.8
dermatology 0.34 112.7 K 1 308 196 t/o 1.5 1.4 0.4 0.4
lung-cancer 0.46 4.2 M t/o 20.1 t/o 3.0 1.4 0.3 1.0
student-mat 0.44 617.9 K t/o t/o t/o 2.5 1.8 1.0 0.8
sint. 0.17 0.17 130.1 K 159 t/o t/o 166 4.3 3.4 25.3
sint. 0.32 0.32 2.0 M t/o t/o t/o 18.2 3.1 2.0 3.8
sint. 0.52 0.52 1.4 M 52.2 23.0 t/o 4.7 2.3 1.3 1.5
sint. 0.80 0.80 30.8 K 6.2 3.7 2.6 1.7 1.5 0.5 0.6

Tiempos en experiments/baseline/results/why_mmcs.md.

Lectura:

  1. Prueba de filas críticas (GCreduct → fast-BR): entre 1.2 y 13 veces menos trabajo. Ayuda, pero no explica la distancia.
  2. Sin fila pivote, la prueba de filas críticas sola no sirve: SHD con 9D (filas críticas, columnas en orden de índice, sin pivote) agota el límite en 10 de 12 matrices, incluso donde fast-BR termina en 0.2 s. Inferencia: fast-BR y GCreduct sobreviven gracias al pivote de la raíz y a la eliminación de brechas.
  3. Pivote en cada nodo (fast-BR → MMCS): es el salto grande. Soybean pasa de 3 189 a 1.4 por reducto, biodeg de 14 282 a 1.8, MED de 4.7 M a 9.7. En densidad alta el salto se reduce: 2.5 veces en la sintética de 0.80.
  4. Qué fila se elige importa: con la primera fila no cubierta en vez de la más restringida, la sintética de 0.17 pasa de 4.3 a 166 por reducto, peor que GCreduct. La regla "menos candidatas" no es un detalle.
  5. Nuestra implementación frente a la de Uno: SHD visita entre 1.5 y 4 veces menos nodos. Inferencia: se debe a su reducción de datos y a que calcula las columnas añadibles por adelantado. La conclusión no cambia: la ventaja es algorítmica, no de lenguaje.

Precauciones:

  • "Candidato" y "nodo" no son la misma unidad. La comparación vale como orden de magnitud. Una diferencia de 2 veces en esta tabla no significa nada; una de 1 000 sí.
  • Una corrida por matriz y 12 matrices.

Tres consecuencias

  • El orden de columnas casi no afecta a MMCS (piloto de anoche: razón máxima 2.1) porque elige la fila pivote de forma dinámica. GCreduct sí depende del orden, porque su único pivote es estático. Inferencia, coherente con la ablación.
  • La ventaja es mayor en matrices dispersas. Filas con pocos unos dan filas pivote pequeñas y ramificación baja. Es el mismo eje que la regla de densidad de la tesis (GCreduct por debajo de 0.36). Inferencia.
  • MMCS no es mágico en el peor caso: el preprint de 2026 (arXiv 2608.02159) prueba que no es output-polynomial. En estas matrices el trabajo por reducto se mantuvo entre 0.3 y 4.3.

Una lectura útil para la línea de investigación

Inferencia: el arreglo de la tesis era la idea correcta aplicada solo en el primer nivel. Llevarla a todos los niveles es MMCS. Eso da una narrativa honesta: el resultado no es "nuestros algoritmos pierden", sino "la heurística que ya usábamos explica la diferencia cuando se aplica de forma recursiva". La prueba dentro de fast-BR está en la sección siguiente.

fast-BR con fila pivote en cada nodo (hecho, medición del 2026-11-17)

java/src/mhs/Br.java reescribe fast-BR con bitsets, en forma recursiva, con las mismas pruebas que el original: aporte, exclusión y filtrado de la lista de la rama hija. Tiene tres modos, y entre ellos solo cambia qué posiciones de la lista se prueban como siguiente columna y en qué orden:

  • root: la regla de la tesis. En la raíz van primero las columnas de la fila con menos unos, y solo esas se prueban.
  • bound: igual que root, más un corte en cada nodo. Solo se prueban posiciones hasta la última columna de cada fila no cubierta. No reordena.
  • pivot: la regla de la raíz en cada nodo. Elige la fila no cubierta con menos columnas en la lista, la pone al frente y prueba solo esas columnas. Es la ramificación de MMCS dentro de fast-BR.

Validación: 300 matrices aleatorias con columnas repetidas y columnas llenas, los tres modos, 0 diferencias por conjunto con experiments/lib/bm.py. Las pruebas de regresión incluyen br y br-pivot (11 de 11).

Fidelidad: br-root evalúa los mismos candidatos por reducto que el fast-BR original en soybean, anneal, heart-c, lung-cancer y las sintéticas de 0.52 y 0.80. En MED y biodeg evalúa entre 1.5 y 3 veces más; inferencia: el desempate del orden de columnas es distinto.

Resultado (experiments/baseline/br_pivot.py, límite de 30 s; candidatos por reducto y tiempo en ms):

Matriz Dens. Reductos fastbr br-root br-bound br-pivot mmcs (ms) shd-mmcs (ms)
MED 0.03 3 4.7 M; 1341 14.1 M; 4780 185; 14 116; 17 0 0
soybean 0.20 570 3 189; 167 3 189; 150 9.4; 21 3.7; 15 3 1
biodeg 0.08 256 14 282; 462 21 305; 536 67.5; 33 5.8; 21 2 1
anneal 0.13 313 827; 105 828; 67 74.9; 27 6.6; 24 4 2
heart-c 0.49 97 9.3; 15 9.2; 21 5.9; 22 3.4; 33 1 2
dermatology 0.34 112.7 K 196; 5318 214; 3298 26.9; 670 3.4; 626 424 166
lung-cancer 0.46 4.2 M 20.1; 10720 20.0; 6420 8.3; 3037 2.6; 1188 1352 2371
student-mat 0.44 617.9 K t/o t/o 106; 26780 4.9; 2734 1912 1923
sint 0.17 0.17 130.1 K t/o t/o 90.3; 4392 16.6; 1767 678 886
sint 0.32 0.32 2.0 M t/o t/o 54.1; 29467 10.4; 10448 6927 7258
sint 0.52 0.52 1.4 M 23.0; 11092 23.3; 5753 17.2; 4857 7.0; 3841 2065 3665
sint 0.80 0.80 30.8 K 3.7; 125 3.7; 87 3.7; 62 3.3; 92 87 72

Tabla completa, con nodos por reducto: experiments/baseline/results/br_pivot.md.

Lectura:

  1. La explicación queda probada. Solo con cambiar dónde se ramifica, fast-BR pasa de agotar el límite (student-mat, sintéticas de 0.17 y 0.32) a terminar a menos de 2.6 veces del tiempo de MMCS. En lung-cancer br-pivot es más rápido que nuestro MMCS y que SHD. Los candidatos por reducto bajan de 3 189 a 3.7 en soybean y de 214 a 3.4 en dermatology.
  2. Reordenar importa, no solo cortar. bound usa la misma información que pivot pero no reordena la lista, y queda entre 2 y 20 veces por encima de pivot en candidatos por reducto. El orden fijo de columnas es lo que hace caro a fast-BR.
  3. Lo que queda de diferencia con MMCS (hasta 2.6 veces en tiempo, en la sintética de 0.17) es inferencia: fast-BR filtra toda la lista de la rama hija al entrar, y MMCS solo prueba las columnas de la fila pivote. No lo medí.
  4. En densidad alta todo converge: en la sintética de 0.80 las seis variantes están entre 62 y 125 ms.

Precaución: una corrida por matriz, 12 matrices, máquina de 2 núcleos.

Inferencia para el artículo: br-pivot no es un algoritmo nuevo; es MMCS con filtrado anticipado. Sirve como ablación limpia, porque usa el código de pruebas de fast-BR y solo cambia la regla de ramificación. No lo presentaría como aporte algorítmico sin una revisión bibliográfica: el filtrado anticipado dentro de MMCS puede estar publicado.

3. Estado del código de Uno

Compilado con tu permiso (scripts/fetch_shd.sh). Está integrado en el runner como shd-mmcs (opción D) y shd-rs (opción 0). Coincide por conjunto de reductos con la referencia en Python en las 442 matrices de verificación.

4. ¿Vale un artículo de congreso?

Criterios

  1. Aporte nuevo para la comunidad que lo lee. No basta con "corregimos nuestro código".
  2. Solidez de la evidencia. Validación por conjunto, baselines fuertes y corridas en una máquina adecuada.
  3. Esfuerzo frente a la fecha límite.
  4. Riesgos: licencias de código de terceros y exposición de los errores.
  5. Encaje con la línea de investigación y con las ideas 1 y 3 de la página de asesores.

Valoración

Solo con las correcciones: no. Un artículo cuyo aporte principal es "arreglamos fallos de conteo en nuestros programas" no pasa el criterio 1. En el mejor caso es una nota de errata.

Solo con el framework en Java: débil. Gainer-Dewar y Vera-Licona ya publicaron un banco de pruebas con 17 implementaciones de hitting sets y contenedores (repositorio). Otro framework, por sí solo, no es nuevo.

Con el enfoque correcto: sí, y es buen material. Lo que no encontré publicado es esto:

  • El cruce de las dos comunidades: algoritmos de testores y reductos (GCreduct, fast-BR, fast-CT_EXT, MinReduct, sRGA, CAMARDF) contra MMCS y RS, sobre las mismas matrices.
  • En un solo lenguaje, lo que separa algoritmo de implementación. La comparación entre nuestro MMCS en Java y SHD en C mide ese efecto directamente.
  • Con validación por conjunto de reductos y una referencia independiente. Los errores encontrados son el argumento de por qué hace falta: programas publicados y usados como referencia daban conteos distintos, y nadie podía notarlo porque solo imprimían conteos.
  • Con la ablación, que explica la diferencia y la conecta con la tesis.

Propuesta de título de trabajo: "Testor and reduct algorithms meet minimal hitting set enumeration: a validated Java framework and a cross-community comparison".

Los errores van en una sección de "validación y hallazgos", no en el título ni en el resumen.

Riesgos y condiciones

  • Los errores se hacen públicos. Hasta ayer el criterio era no llevarlos ni a la página de asesores. Un artículo los pone frente a ellos y frente a quien use los paquetes. Creo que bien enmarcados juegan a favor (muestran rigor), pero es tu decisión. Hay que hacerlo antes de escribir.
  • Código de terceros sin licencia. CAMARDF y MiLIT no traen licencia. Camardf.java se escribió leyendo Cpp1.cpp y reproduce su conteo de candidatos con -faithful. Eso puede contar como obra derivada. Opciones: pedir permiso a los autores, o publicar solo implementaciones hechas desde la descripción del artículo. SHD permite uso académico y redistribución con enlace a la página de Uno; el framework puede bajarlo y compilarlo sin incluirlo.
  • La máquina. Con 2 núcleos y límites de 30 s, la mitad de las celdas de GCreduct y fast-BR son "límite". Para un artículo hacen falta corridas largas en otra máquina.
  • Alcance de "implementar en Java lo que no está". Hoy en C o C++: CAMARDF (ya hecho), MMCS (hecho), RS (falta) y HTC-BDD de Toda (falta; usa diagramas de decisión binaria, más trabajo). Recomiendo RS sí y HTC-BDD no para la primera versión: se compara contra el binario original y se declara.

Lugar y fechas

  • IJCRS 2027 (Winnipeg, 8 a 11 de junio de 2027; Springer LNCS/LNAI). Artículo completo de 12 a 15 páginas, fecha límite 15 de diciembre de 2026, es decir, en cuatro semanas. La convocatoria no nombra reductos; lo más cercano es rough-set-based feature selection (convocatoria). Es la audiencia natural de MinReduct.
  • MCPR 2027. No encontré la convocatoria. Las ediciones anteriores tuvieron fecha límite en enero o febrero (2026: 31 de enero). Es donde publicaste la comparación de MiLIT y MinReduct.

Con cuatro semanas, IJCRS es ajustado pero posible si el alcance se congela ya.

Qué falta para un primer borrador

  1. RS en Java y validación por conjunto.
  2. Que GCreduct, fast-BR, fast-CT_EXT y MinReduct corregidos listen reductos, para validarlos por conjunto y no solo por conteo.
  3. Corridas completas en una máquina con más núcleos: las 500 sintéticas y todas las UCI, con límites de horas, no de segundos.
  4. Ablación con un pivote dinámico dentro de fast-BR, para cerrar el argumento.
  5. Decidir lo de licencias y lo de hacer públicos los errores.
  6. Escribir.

5. Lo que no sé

  • Si existe una comparación previa de algoritmos de testores contra MMCS o RS. No encontré ninguna en dos búsquedas; no es prueba de que no exista. Es la pregunta 5 de la página de asesores y conviene resolverla antes de afirmar novedad.
  • Si la ventaja de MMCS se mantiene con matrices de muchas columnas (arrhythmia tiene 279). Esta noche ningún programa de "todos los reductos" terminó ahí en 30 s.

Fuentes

  • Murakami y Uno, Efficient algorithms for dualizing large-scale hypergraphs: https://arxiv.org/abs/1102.3813
  • Gainer-Dewar y Vera-Licona, survey y banco de pruebas: https://arxiv.org/abs/1601.02939 y https://github.com/VeraLiconaResearchGroup/MHSGenerationAlgorithms
  • Código SHD de Uno: https://research.nii.ac.jp/~uno/dualization.html
  • Convocatoria de IJCRS 2027: https://www.roughsets.org/news/cfp/2026-09-21/call-for-papersthe-2027-international-joint-conference-on-rough-sets-ijcrs-2027/
  • MCPR 2026, fecha límite según el boletín de la IAPR: https://iapr.org/docs/newsletters/2026-Vol-48-No-1.pdf