Saltar a contenido

Plan del artículo: framework validado y comparación con MMCS y RS

Fecha: 2026-11-17. Decisión de Vladimir: los errores del código original se publican como parte del artículo. El objetivo es que quien use esos algoritmos hoy tenga implementaciones en las que pueda confiar.

Tesis del artículo

Reescrita el 2026-11-17, después de la revisión bibliográfica y de las mediciones con RUNC-M (docs/revision-bibliografica-br-pivot.md, sección 6). Sustituye a la versión anterior, según la cual "MMCS y RS superan a todos". Eso ya no es cierto: RUNC-M les gana en matrices densas o con pocas filas.

Hasta donde encontramos, los algoritmos latinoamericanos de testores típicos (fast-BR, fast-CT_EXT, GCreduct) no se habían comparado con los de minimal hitting sets, aunque calculan lo mismo. Las otras dos familias que resuelven el problema son la de Murakami y Uno (MMCS, RS) y la escuela rusa de Djukova (RUNC-M). Las comparamos en un framework común, validado por conjunto de reductos. En las matrices probadas, los algoritmos latinoamericanos quedan detrás de las otras dos familias; en la primera comparación, fast-BR tarda entre 1,4 y 12 veces lo que MMCS, o agota el límite (pendiente de las corridas completas). Una ablación dentro de fast-BR muestra la causa principal: fast-BR elige la fila pivote solo en la raíz. Si la elige en cada nodo, se convierte en RUNC-M y queda entre 0,9 y 3,3 veces el tiempo del RUNC-M original en C++. Entre las dos familias rápidas no hay una que gane siempre. El filtrado de toda la lista de candidatos (RUNC-M) gana con densidad alta o con pocas filas. La poda perezosa (MMCS) gana en matrices ralas con muchas filas. Además, el framework destapó errores de conteo en implementaciones publicadas; quedan corregidos, con pruebas de regresión.

Lo que no se reclama: br-pivot no es un algoritmo nuevo, es RUNC-M (Djukova y Prokofjev 2015) reconstruido desde fast-BR. Tampoco es nueva la comparación de RUNC-M con MMCS y RS: está en la tesis de Prokofjev (2016). Nuestro aporte en ese punto es repetirla con un MMCS más rápido que el de SHD, y con eso el cruce se mueve.

Título de trabajo: Three families, one problem: testor, Djukova-school and minimal hitting set algorithms compared in a validated framework.

Aportes

  1. Framework. Trece programas con un contrato común: entra una matriz básica, sale JSON con conteo, candidatos, tiempo y conjunto de reductos. La validación es por conjunto y la referencia es independiente.
  2. Auditoría de corrección. Cinco errores en código publicado, con la condición que dispara cada uno, su efecto en los paquetes públicos (pequeño: tres matrices) y pruebas de regresión.
  3. Comparación entre las tres familias. Algoritmos latinoamericanos, RUNC-M, MMCS y RS, en todos los reductos y en los más cortos.
  4. Ablación. Cuando fast-BR elige la fila pivote en cada nodo se convierte en RUNC-M. Ese es el ingrediente que explica la mayor parte de la diferencia.
  5. Cuándo gana cada estrategia. Un barrido controlado de densidad, filas y columnas, que da el cruce entre el filtrado de toda la lista y la poda perezosa. Sirve para elegir algoritmo según la matriz, y conecta con la idea de meta-algoritmo de la tesis de 2022.
  6. Secundario: sensibilidad al orden de filas y columnas.

Debilidades conocidas: - El cruce se midió en matrices aleatorias, y dermatology no lo sigue. - Todo corrió en una máquina de 2 núcleos. - RUNC-M no se puede redistribuir sin permiso de sus autores.

Inventario de algoritmos

Algoritmo Problema Original En el framework Validado por conjunto (442 pequeñas y 8 UCI)
GCreduct todos Java copia corregida sí
fast-BR todos Java copia corregida sí
fast-CT_EXT todos Java copia corregida sí
MMCS todos C (SHD de Uno) Java nuevo, y SHD como externo sí, los dos
fast-BR con pivote (ablación) todos no existe mhs.Br (modos root, bound, pivot) sí, 300 aleatorias y pruebas de regresión
RS todos C (SHD de Uno) Java nuevo, y SHD como externo sí, los dos
RUNC-M (Djukova y Prokofjev) todos C++ (Nikiforov, sin licencia) externo, scripts/fetch_runcm.sh, runcm en el runner sí, 453 matrices pequeñas
MinReduct más cortos Java copia corregida sí
sRGA más cortos Java copia corregida y Srga nuevo Srga sí; la copia corregida solo por conteo
CAMARDF más cortos C++ Camardf en Java sí
MMCS acotado más cortos no existe mhs.Mmcs -shortest sí

En las 8 UCI, lung-cancer quedó sin GCreduct ni fast-CT_EXT por el límite de 60 s.

Dentro de la primera versión, desde el 2026-11-20: RegularSearch y YYC de Lefebre (github.com/J41R0/RegularSearch, MIT; en el runner regsearch y yyc, ver scripts/fetch_regsearch.sh). Fuera de la primera versión: HTC-BDD (Toda), RoPM y MiLIT. De este último se puede correr el JAR, pero no redistribuirlo sin permiso. FastRS (Lefebre, sin publicar), MHS2 y el banco ampliado (HTC-BDD, datasets de Uno) quedan para un posible trabajo conjunto con Jairo Lefebre, decidido el 2026-11-20 (opción c en docs/regularsearch-y-jairo.md §3.2).

Hecho a la fecha

  • Verificación: 442 matrices pequeñas y 13 de UCI. Validación por conjunto de los 12 programas en las 442 y en 8 UCI.
  • Errores documentados en docs/hallazgos-errores.md; pruebas en tests/ (11 matrices, por conteo y por conjunto).
  • Auditoría de los paquetes publicados (experiments/audit/).
  • Piloto de ordenamiento (experiments/ordering/).
  • Primera comparación (experiments/baseline/) y ablación (docs/mmcs-y-propuesta-articulo.md).

Falta

  1. ~~Ablación que cierra el argumento: fast-BR con fila pivote dinámica.~~ Hecho el 2026-11-17: mhs.Br -mode pivot queda a menos de 2.6 veces del tiempo de MMCS, desde agotar el límite o 10 veces más (docs/mmcs-y-propuesta-articulo.md, sección "fast-BR con fila pivote en cada nodo").
  2. Corridas completas en una máquina con más núcleos: las 663 sintéticas distintas y las UCI, con límites de horas.
  3. Reductos más cortos: comparación sistemática de MinReduct, Srga, Camardf y MMCS acotado.
  4. Revisión bibliográfica: primera pasada hecha el 2026-11-17 (docs/revision-bibliografica-br-pivot.md). br-pivot es en esencia RUNC-M (Djukova y Prokofjev, 2015): no se presenta como algoritmo nuevo y hay que citar RUNC-M y OPT. La tesis de Prokofjev (2016) ya compara RUNC-M y OPT contra MMCS y RS; no se encontró comparación de BR, fast-BR, CT_EXT, YYC o GCreduct contra MMCS o RS. Falta leer el artículo original de RUNC-M y confirmarlo con los asesores (pregunta 5). El código de RUNC-M se recuperó de Software Heritage, quedó validado y entra como baseline. En la primera medición gana en matrices densas y pierde contra MMCS en las ralas (sección 6 de la revisión). Los artículos que faltan están en docs/articulos-por-conseguir.md. 4b. Explicar dermatology: sale del cruce del barrido. Probar matrices con columnas correlacionadas o filas de peso desigual. 4c. Hecho el 2026-11-19 (parcial): github.com/ppprok/dual (MIT, commit 224ebf9) se compila sin cmake con scripts/fetch_ppdual.sh (driver propio scripts/ppdual_main.cpp) y entra al runner como ppdual (RUNC-M) y ppdual-runc (fila 1). Validación por conjunto de reductos contra la referencia de Python en 453 matrices (experiments/baseline/ppdual_vs_runcm.py): coinciden ppdual, ppdual-runc y runcm en las 453. Nodos de búsqueda: 117879 contra 117060 (ppdual cuenta distinto; no se comparan como misma métrica). Tiempos (20 matrices, mediana de 3, results/ppdual_vs_runcm_time.md): ppdual es 2 a 5 veces más rápido que runcm de Nikiforov en las 12 sintéticas de 2000x30 y le gana a shd-mmcs en todas, incluidas las ralas (ej. densidad 0,17: 347 ms contra 1853 de runcm y 975 de shd-mmcs; antes mmcs en Java tardaba 737). runcm gana solo en dermatology y lung-cancer. Consecuencia: la afirmación «MMCS gana en ralas con muchas filas» no se sostiene contra la implementación de Prokofyev; era en parte efecto de la implementación de Nikiforov. Hay que rehacer el barrido (runcm_sweep.py) con ppdual y reescribir esa parte del artículo. Pendiente: causa (la ruta de ancho fijo de 32/64/128 columnas es hipótesis, no medida), medir ppdual-runc contra ppdual por nodos y tiempo para separar fila mínima de filtrado, y correr sobre synth.py. runcm de Nikiforov queda solo como comparación. 4d. Verificación del sesgo y candidatos (2026-11-19). (a) El driver ppdual no sesga: leer la matriz y arrancar cuesta 2 ms, mismas banderas -O3 que runcm, salida a /dev/null en ambos. (b) Candidatos evaluados de nuestros programas Java (experiments/baseline/candidates.py, results/candidates.md): mmcs evalúa menos que br-pivot en 17 de 20 matrices (br-pivot/mmcs entre 0,94 y 2,76 en las sintéticas; en lung-cancer es 0,63) y que rs en todas (1,0 a 10). br sin pivote agota 60 s o evalúa de 1 a 1,5 millones de veces más en matrices ralas pequeñas. Es decir: por candidatos MMCS gana casi siempre, y por tiempo ppdual le gana en ralas. El contador de cada programa externo tiene otra unidad (iteraciones de SHD, nodos de runcm/ppdual), así que no entra. La diferencia de tiempo a igualdad de trabajo es costo por candidato de la implementación, no del algoritmo. Esto no se puede cerrar con programas heterogéneos: hace falta el framework de abajo. 4e. Framework Java de primitivas equivalentes (pedido por Vladimir). Un solo núcleo con la misma representación (bitsets), el mismo lector y los mismos contadores, donde MMCS, RUNC-M, br-pivot y RS son combinaciones de políticas intercambiables: elección de fila (primera, mínimos candidatos), filtrado de candidatos (ninguno, lista completa por nodo, perezoso), mantenimiento de filas críticas, orden de columnas. Cada primitiva cuenta sus ejecuciones (extensiones probadas, actualizaciones de crit, palabras tocadas). Así, tiempo y candidatos se comparan con todo lo demás igual, y los programas externos (SHD, ppdual) quedan como referencia de corrección y de cota, no como base de la tesis. Diseño por acordar antes de escribir código. Decidido el 2026-11-19: el núcleo convive con mhs.Mmcs, Rs y Br y se valida contra ellos por conjunto de reductos. 4e-bis. Núcleo escrito (2026-11-19): java/src/mhs/core/ (Core, Rep, BitsetRep, ListRep, Matrix; build.sh lo compila). Un motor y tres ejes: -rep bitset|list, -row min|first, -cand lazy|filter; ocho configuraciones en el runner como core-<rep>-<row>-<cand>. Identidades que declara: bitset-min-lazy = mhs.Mmcs; bitset-first-lazy = Mmcs -firstrow; *-min-filter = RUNC-M; *-first-filter = RUNC. Verificado (experiments/baseline/core_validate.py, results/core_validate.md): las 8 configuraciones coinciden por conjunto de reductos con la referencia de Python en 453 matrices, y las dos identidades lazy coinciden con mhs.Mmcs en Nodes y Candidates en las 453. Las identidades con RUNC-M y RUNC no están verificadas (solo por conjunto): falta comparar nodos con ppdual y ppdual-runc, que cuentan distinto. Contadores iguales en todas: Nodes, Extends, Filters, Candidates = Extends + Filters, RowScans, Work (palabras o elementos). Fuera de la v1: RS (orden fijo de filas con prefijo) y Br. Comparación completa en experiments/baseline/core_compare.py (en curso al escribir esto). Resultados completos (20 matrices, mediana de 3, límite 30 s; results/core_compare.md). Corrección: un dato parcial que escribí antes («list 10 a 25 veces más lento que bitset») era un error de lectura de columnas: esos 19 s eran bitset-first-lazy. Lo correcto: (1) Con la misma representación, lazy gana a filter en tiempo en las 20 matrices con bitset-min (ej. 744 contra 1730 ms; student-mat 1836 contra 5540). Filter hace 3 a 4 veces más pruebas de extensión (785 mil contra 2,84 millones) a cambio de solo 5 % menos nodos (556100 contra 524946). (2) Fila mínima contra primera fila: first se dispara en matrices ralas (19258 ms contra 744; con filter agota 30 s) y se acerca a min al subir la densidad; en la más densa (0,80) first-lazy es más rápido que min-lazy (52 contra 97 ms). (3) Representación: list hace de 3 a 6 veces menos operaciones elementales que bitset (unidad distinta: elementos contra palabras), pero el tiempo es parecido o algo peor (867 contra 744 ms en la más rala); gana en pocas matrices (student-mat 1070 contra 1836 ms; dermatology 103 contra 116). Con 2000 filas y densidad ≥ 0,17, las listas no ganan de forma clara. (4) Consecuencia para ppdual: en este motor, min-filter (la estrategia de RUNC-M) no es más rápida que min-lazy (MMCS), y sus nodos (524946) son cercanos a los de ppdual (541149) y runcm (544566) en la primera matriz: parecido, no idéntico. Entonces la ventaja de 2 a 5 veces de ppdual sobre mhs.Mmcs no sale de la estrategia sino del costo por candidato de la implementación (C++, estructuras). Es una inferencia: falta construir una configuración Java que reproduzca ese costo, o instrumentar ppdual. Y no sé cuánto aporta C++ frente a JVM. No hay base para la frase «MMCS gana en ralas» ni para «RUNC-M gana en ralas»; sí para: a igualdad de implementación, lazy gana a filter y fila mínima gana a primera fila en ralas. Zona muy rala (2026-11-20, experiments/baseline/core_sparse.py, results/core_sparse.md): 14 matrices de densidad real 2,7 a 5,2 % (913×60 a 4000×100, 2 semillas, mediana de 3, límite 40 s). list-min-lazy gana a bitset-min-lazy en 13 de 14, hasta 2,2 veces (4000×100, 0,029: 6542 contra 14198 ms); list-min-filter gana a bitset-min-filter en las 14. Confirma la hipótesis de Vladimir (4f(e)) en ese rango. Falta el cruce entre 5 y 17 % y matrices de cientos de columnas, donde la cantidad de reductos explota. 4f. Comentarios de Lazo (2026-11-19) y decisiones que implican. (a) Construcción de la matriz básica: unos algoritmos parten de la tabla de decisión y otros de la matriz básica; Lazo pide contar el tiempo de construirla, Vladimir prefiere tratarla aparte. Propuesta: reportar siempre tres cifras, t_construcción, t_búsqueda y su suma, y un algoritmo que no construye la matriz (RegularSearch, CAMARDF desde la tabla) entra con su tiempo total. Lazo envió un artículo con Memo (autómata para la matriz básica, sección To Appear de la revista): pendiente recibirlo y leerlo. (b) Densidad de unos como variable de referencia: Lazo y Saúl Solorio lo empezaron y no lo terminaron; coincide con nuestro cruce y con dermatology (4b). No decir «la densidad predice el ganador» sin probar que filas, columnas y distribución de pesos no lo explican mejor. (c) Lazo trabaja con colegas de Namibia en cotas de teoría de hipergrafos para MiLIT y MinReduct (más cortos); preguntar por el artículo. (d) Lista de «cosas que hacen los algoritmos» de Lazo (core, orden, fila pivote): pedirla; es casi el mismo eje de políticas del framework. (e) Hipótesis de Vladimir: los algoritmos que guardan el discernimiento en listas enlazadas son muy eficientes en matrices ralas por el bajo costo por candidato. Contrastar en el framework con la representación como un eje más (bitset contra listas de adyacencia), sin tocar la estrategia.
  5. Licencias: pedir permiso a Nikiforov, Djukova o Prokofjev para RUNC-M. Pedir permiso para Camardf.java a los autores de CAMARDF, o declararlo reimplementado desde el artículo y comprobar que lo es.
  6. Repositorio público para el artículo: separar lo que se puede publicar (código propio, correcciones, código nuevo) de lo que no (legacy/, SHD, MiLIT).
  7. Redacción.

Calendario hacia IJCRS 2027 (fecha límite: 15 de diciembre de 2026)

Semana Trabajo
17 a 23 nov Congelar el alcance. Ablación de fast-BR con pivote. Correo a los autores de CAMARDF. Conseguir la máquina.
24 a 30 nov Corridas completas. Comparación de reductos más cortos.
1 a 7 dic Borrador completo.
8 a 15 dic Revisión de los asesores y envío.

Si la máquina o la revisión de los asesores se retrasan, MCPR 2027 (fecha probable: enero o febrero, sin confirmar) es la alternativa.

Decisiones pendientes

  1. IJCRS o MCPR.
  2. Qué máquina usar para las corridas largas.
  3. Si MiLIT entra en la comparación (corriendo el JAR, sin redistribuirlo).
  4. ~~Cuándo se les cuenta a los asesores.~~ Hecho el 2026-11-17: la página de ideas tiene una sección con los errores, RUNC-M y la nueva tesis.