Conciliación de Haberes con Subset Sum

En la liquidación de haberes de grandes instituciones como la UBA, es común encontrar discrepancias entre lo liquidado y lo reportado a entes externos (AFIP, ANSES).

El problema no es detectar que hay una diferencia, sino cuál es su origen. Con cientos de conceptos (sueldos, aportes, adicionales, descuentos), encontrar manualmente qué combinación de ellos suma exactamente la diferencia detectada es un problema de complejidad exponencial.

Implementé una solución basada en el problema matemático Subset Sum (Suma de Subconjuntos). El objetivo es encontrar, dado un conjunto de valores (conceptos del legajo), qué subconjunto suma un valor objetivo (la diferencia detectada).

Optimizaciones Críticas (Pruning)

Para manejar la explosión combinatoria, el algoritmo utiliza técnicas de poda:

• Ordenamiento Previo: Procesar elementos de mayor a menor para descartar ramas de búsqueda rápidamente.
• Suma Restante: Si la suma actual más todos los elementos restantes no alcanza el objetivo, se aborta la rama.
• Tolerancia Dinámica: Manejo de errores de redondeo de punto flotante típicos en sistemas financieros.

El núcleo de la solución es una función recursiva optimizada que explora el espacio de búsqueda con un límite de tolerancia configurable.

// Implementación del núcleo recursivo con poda
private function findSubsets(
    array $items,
    float $targetSum,
    array $currentSubset,
    int $index,
    float $currentSum,
    array &$results,
    float $tolerance
): void {
    // Éxito: diferencia dentro de la tolerancia
    if (abs($currentSum - $targetSum) <= $tolerance) {
        $results[] = ['items' => $currentSubset, 'total' => $currentSum];
    }

    // Poda: si excedemos demasiado o no quedan elementos
    if ($index >= count($items) || $currentSum > $targetSum * 1.5) {
        return;
    }

    // Poda: si lo que queda no alcanza para llegar al objetivo
    if ($currentSum + $this->getRemainingSum($items, $index) < $targetSum - $tolerance) {
        return;
    }

    // Exploración de ramas (con y sin el elemento actual)
    $this->exploreBranch($items, $index, $currentSubset, $currentSum, ...);
}

Esta herramienta transformó un proceso de investigación manual de horas por legajo en un diagnóstico instantáneo. Al identificar exactamente qué conceptos causan la falla, el equipo de nómina puede corregir las fórmulas en el sistema base (SIU Mapuche) de forma quirúrgica, eliminando errores sistémicos en lugar de hacer ajustes manuales temporales.