Verification-domain profiles for a posteriori scalarisation certificates in finite multi-objective optimisation

Resumen Técnico: Perfiles de Dominios de Verificación para Certificados de Escalarización A Posteriori

1. Planteamiento del Problema

En muchos flujos de trabajo de investigación operativa, el objeto que requiere justificación no es una frontera de Pareto completa, sino un único candidato a decisión seleccionado. Este candidato puede originarse de resolvedores exactos, heurísticas o negociaciones con las partes interesadas. El desafío matemático abordado en este artículo es la certificación a posteriori: verificar que un candidato específico es óptimo para una escalarización escalar positiva declarada sobre un conjunto declarado de alternativas (el dominio de verificación).

El artículo destaca una ambigüedad crítica en la literatura existente: una afirmación de que un candidato "posee un certificado de suma ponderada" carece de definición sin especificar el dominio de verificación. En la práctica, la verificación suele ocurrir sobre un catálogo estructurado más grande que el conjunto factible (por ejemplo, todas las asignaciones frente a las asignaciones factibles de recursos). Ampliar el dominio de verificación puede destruir un certificado a menos que se apliquen multiplicadores de restricciones activas (precios sombra) para penalizar las alternativas no factibles. El problema central es cuantitativo: ¿Cuánta margen de certificado positivo se pierde al usar un catálogo más grande y qué presupuesto de multiplicador normalizado se requiere para recuperarlo?

2. Metodología y Marco de Trabajo

Modelo Finito Normalizado
Los autores formalizan el problema utilizando un catálogo finito $K$ con objetivos $F$ y restricciones $g$. Se fija un candidato factible seleccionado $x^0$. El modelo introduce:

• Dominio de Verificación ($V$): Un conjunto tal que $K_0 \subseteq V \subseteq K$, donde $K_0$ es el conjunto factible.
• Escalas Declaradas: Escalas positivas $s_i$ y $r_j$ se fijan antes de comparar dominios para asegurar la consistencia de las unidades. Esto evita que cambios arbitrarios en las unidades de medida alteren los requisitos aparentes de los multiplicadores.
• Puntuaciones Normalizadas: Las diferencias en los objetivos y las restricciones se normalizan mediante estas escalas.
• Presupuesto ($B$): Un límite superior en la suma de los multiplicadores de las restricciones activas ($\nu$).

El Perfil de Dominio de Verificación ($\Gamma_V(B)$)
El objeto central es la función de perfil $\Gamma_V(B)$, definida como el mayor margen escalar normalizado mínimo obtainable sobre todos los pesos de objetivos no negativos y multiplicadores de restricciones activas con un presupuesto total de máximo $B$.

• Interpretación: Cuantifica la existencia, rigurosidad, robustez y el valor marginal de la penalización adicional del certificado.
• Propiedades: El perfil es monótono bajo la inclusión de dominios, no decreciente y cóncavo en $B$, plano cuando $V$ es el conjunto factible, y afín por tramos para datos finitos racionales.

Dualidad y Tricotomía
Utilizando la dualidad minimax finita, el perfil se representa mediante una "distribución de estrés" dispersa sobre las alternativas. Esto produce una tricotomía exacta de inofensivo–reparable–irreparable:

1. Inofensivo: $B^*_V = 0$. El candidato está certificado sin multiplicadores.
2. Reparable: $0 < B^*_V < \infty$. Es necesario y suficiente un presupuesto positivo finito para certificar al candidato.
3. Irreparable: $B^*_V = \infty$. Ninguna cantidad de penalización por restricciones activas puede certificar al candidato; el dominio contiene una mejora de objetivos promediada que es invisible para las restricciones activas.

Algoritmos
El artículo propone procedimientos exactos de generación de filas (generación de restricciones retardada) en lugar de garantías de tiempo polinómico. Estos algoritmos alternan entre un problema maestro racional de baja dimensión (dependiente de los objetivos y las restricciones activas) y un oráculo de escalar global estructurado (por ejemplo, dualidad de asignación, caminos cortos).

• Certificación de Presupuesto Mínimo: Computa el $B^*_V$ exacto.
• Evaluación de Presupuesto Fijo: Computa $\Gamma_V(B)$ para un presupuesto específico.
• Intervalos de Tchebycheff Aumentados: Para las escalarizaciones de Tchebycheff ponderadas aumentadas, el artículo deriva el intervalo admisible exacto para el parámetro de aumentación $\rho$ dado un candidato y una dirección, demostrando que los límites estándar de "brecha sobre rango" pueden ser arbitrariamente conservadores.

3. Contribuciones Clave

1. Perfil de Certificado de Dominio de Verificación: Un perfil $\Gamma_V(B)$ invariante a la unidad y consistente en la escala que vincula explícitamente el candidato, el dominio de verificación, el presupuesto de restricciones activas y la política de escala.
2. Dual Disperso Minimax y Tricotomía: Una clasificación exacta de dominios en inofensivos, reparables o irreparables, respaldada por una fórmula cerrada para el presupuesto de multiplicador normalizado mínimo y una distribución de estrés dispersa que explica el fallo del certificado.
3. Algoritmos Exactos de Generación de Filas: Procedimientos exactos finitos para computar presupuestos mínimos y valores de perfil utilizando oráculos estructurados, evitando la enumeración completa de grandes dominios.
4. Intervalos Exactos de Tchebycheff Aumentados: Una declaración de admisibilidad a nivel de certificado para el parámetro de aumentación, demostrando que los límites suficientes clásicos pueden ser arbitrariamente conservadores.
5. Validación Computacional: Un estudio de falsificación exacta a través de catálogos explícitos, asignaciones con restricciones laterales y caminos cortos por capas.

4. Resultados

El estudio computacional validó el marco en 84 pares candidato-dominio (incluyendo 12 casos de asignaciones con restricciones laterales y 12 casos de caminos cortos por capas) con hasta 177,147 alternativas.

• Corrección: Acuerdo del 100% (84/84) en la clasificación de dominios y cálculos de presupuesto mínimo entre el método de generación de filas propuesto y las líneas base de dominio completo.
• Acuerdo de Perfil: Acuerdo del 100% (196/196) en los valores de perfil de presupuesto fijo.
• Economía de Filas: En casos de escalado estructurado, la generación de filas retuvo una mediana de solo el 0.904% de los resultados del desafiante (máximo 5.79%), requiriendo a lo sumo 15 llamadas al oráculo para la corrección.
• Límites de Tchebycheff: Para 36 candidatos con umbrales exactos finitos, la mediana de la relación entre el umbral exacto y el límite conservador de brecha sobre rango fue de 16.5, con un máximo de 193.08, confirmando el conservadurismo de los límites suficientes estándar.
• Rendimiento: Aunque la optimización de dominio completo fue más rápida en algunos casos pequeños, el enfoque de generación de filas estructurado demostró ganancias de eficiencia significativas en dominios más grandes donde la enumeración completa era inviable.

5. Significado y Reivindicaciones

El artículo se posiciona no como un método para generar fronteras de Pareto, sino como un lenguaje de verificación reutilizable para candidatos únicos.

• Claridad Semántica: Argumenta que un certificado está incompleto sin dominios de verificación y convenciones de escala explícitos. El perfil hace que estas elecciones de modelado sean explícitas en lugar de ocultarlas en multiplicadores de magnitudes incomparables.
• Utilidad Operativa: El marco proporciona una respuesta cuantitativa a "¿qué tan fuerte es este certificado?" cuando el alcance de la verificación cambia. Transforma la pregunta cualitativa de reparabilidad en un estadístico computable ($B^*_V$).
• Modestia: Los autores declaran explícitamente que la contribución es el ensamblaje de ingredientes clásicos (relajación Lagrangiana, dualidad minimax, programación lineal paramétrica) en un objeto de verificación a nivel de candidato. No reclaman una superioridad de tiempo de ejecución universal sobre el software de generación de fronteras ni garantías de tiempo polinómico para el proceso de generación de filas. El resultado es un contrato de certificado específico (perfil, presupuesto mínimo y escenario de estrés) en lugar de una estructura de frontera global.

El trabajo concluye que los certificados de escalarización positiva son inherentemente incompletos sin definiciones explícitas de dominio y unidades, y el perfil propuesto suminista la semántica cuantitativa invariante a la unidad necesaria para completarlos.