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

Resumo Técnico: Perfis de Domínio de Verificação para Certificados de Escalarização A Posteriori

1. Enunciado do Problema

Em muitos fluxos de trabalho de pesquisa operacional, o objeto que requer justificativa não é uma fronteira de Pareto inteira, mas sim um único candidato à decisão selecionado. Este candidato pode originar-se de resolvedores exatos, heurísticas ou negociações com stakeholders. O desafio matemático abordado neste artigo é a certificação a posteriori: verificar se um candidato específico é ótimo para uma escalarização escalar positiva declarada sobre um conjunto declarado de alternativas (o domínio de verificação).

O artigo destaca uma ambiguidade crítica na literatura existente: uma afirmação de que um candidato "possui um certificado de soma ponderada" é indefinida sem especificar o domínio de verificação. Na prática, a verificação ocorre frequentemente sobre um catálogo estruturado maior que o conjunto factível (por exemplo, todas as atribuições versus atribuições factíveis de recursos). Ampliar o domínio de verificação pode destruir um certificado, a menos que multiplicadores de restrições ativas (preços sombra) sejam aplicados para penalizar alternativas infactíveis. O problema central é quantitativo: Quanto de margem de certificado positivo é perdido ao usar um catálogo maior e qual orçamento de multiplicador normalizado é necessário para recuperá-lo?

2. Metodologia e Estrutura

Modelo Finito Normalizado
Os autores formalizam o problema usando um catálogo finito $K$ com objetivos $F$ e restrições $g$. Um candidato factível selecionado $x^0$ é fixado. O modelo introduz:

• Domínio de Verificação ($V$): Um conjunto tal que $K_0 \subseteq V \subseteq K$, onde $K_0$ é o conjunto factível.
• Escalas Declaradas: Escalas positivas $s_i$ e $r_j$ são fixadas antes da comparação de domínios para garantir a consistência de unidades. Isso evita que mudanças arbitrárias nas unidades de medida alterem os requisitos aparentes de multiplicadores.
• Pontuações Normalizadas: Diferenças em objetivos e restrições são normalizadas por estas escalas.
• Orçamento ($B$): Um limite superior para a soma dos multiplicadores de restrições ativas ($\nu$).

O Perfil de Domínio de Verificação ($\Gamma_V(B)$)
O objeto central é a função de perfil $\Gamma_V(B)$, definida como a maior margem de escala normalizada mínima obtível sobre todos os pesos de objetivos não negativos e multiplicadores de restrições ativas com um orçamento total de no máximo $B$.

• Interpretação: Quantifica a existência, o rigor, a robustez e o valor marginal de penalização adicional do certificado.
• Propriedades: O perfil é monótono sob inclusão de domínio, não decrescente e côncavo em $B$, plano quando $V$ é o conjunto factível, e afim por partes para dados racionais finitos.

Dualidade e Tricotomia
Usando dualidade minimax finita, o perfil é representado por uma "distribuição de estresse" esparsa sobre as alternativas. Isso resulta em uma tricotomia exata de inofensivo–reparável–irreparável:

1. Inofensivo: $B^*_V = 0$. O candidato é certificado sem multiplicadores.
2. Reparável: $0 < B^*_V < \infty$. Um orçamento positivo finito é necessário e suficiente para certificar o candidato.
3. Irreparável: $B^*_V = \infty$. Nenhuma quantidade de penalização de restrição ativa pode certificar o candidato; o domínio contém uma melhoria de objetivo média invisível às restrições ativas.

Algoritmos
O artigo propõe procedimentos exatos de geração de linhas (geração de restrições atrasada) em vez de garantias de tempo polinomial. Estes algoritmos alternam entre um problema mestre racional de baixa dimensão (dependente de objetivos e restrições ativas) e um oráculo de escala global estruturado (ex: dualidade de atribuição, caminhos mínimos).

• Certificação de Orçamento Mínimo: Computa o $B^*_V$ exato.
• Avaliação de Orçamento Fixo: Computa $\Gamma_V(B)$ para um orçamento específico.
• Intervalos de Tchebycheff Aumentados: Para escalarizações de Tchebycheff ponderadas aumentadas, o artigo deriva o intervalo admissível exato para o parâmetro de aumento $\rho$ dado um candidato e direção, mostrando que os limites padrão de "gap-over-range" podem ser arbitrariamente conservadores.

3. Principais Contribuições

1. Perfil de Certificado de Domínio de Verificação: Um perfil $\Gamma_V(B)$ invariante de unidade e consistente de escala que vincula explicitamente o candidato, o domínio, o orçamento de restrição ativa e a política de escala.
2. Dual Minimax Esparso & Tricotomia: Uma classificação exata de domínios em inofensivos, reparáveis ou irreparáveis, suportada por uma fórmula fechada para o orçamento de multiplicador normalizado mínimo e uma distribuição de estresse esparsa que explica a falha do certificado.
3. Algoritmos Exatos de Geração de Linhas: Procedimentos exatos finitos para computar orçamentos mínimos e valores de perfil usando oráculos estruturados, evitando a enumeração completa de grandes domínios.
4. Intervalos de Tchebycheff Aumentados Exatos: Uma afirmação de admissibilidade a nível de certificado para o parâmetro de aumento, demonstrando que os limites suficientes clássicos podem ser arbitrariamente conservadores.
5. Validação Computacional: Um estudo de falsificação exata através de catálogos explícitos, atribuições com restrições laterais e caminhos mínimos em camadas.

4. Resultados

O estudo computacional validou a estrutura em 84 pares candidato-domínio (incluindo 12 casos de atribuições com restrições laterais e 12 casos de caminhos mínimos em camadas) com até 177.147 alternativas.

• Corretude: 100% de concordância (84/84) na classificação de domínio e nos cálculos de orçamento mínimo entre o método de geração de linhas proposto e as linhas de base de domínio completo.
• Concordância de Perfil: 100% de concordância (196/196) nos valores de perfil de orçamento fixo.
• Economia de Linhas: Em casos de escalonamento estruturado, a geração de linhas reteve uma mediana de apenas 0,904% dos resultados do desafiante (máximo de 5,79%), com no máximo 15 chamadas de oráculo necessárias para a corretude.
• Limites de Tchebycheff: Para 36 candidatos com limiares exatos finitos, a razão mediana do limiar exato para o limite conservador "gap-over-range" foi de 16,5, com um máximo de 193,08, confirmando o conservadorismo dos limites suficientes padrão.
• Desempenho: Embora a otimização de domínio completo tenha sido mais rápida em alguns casos pequenos, a abordagem estruturada de geração de linhas demonstrou ganhos significativos de eficiência em domínios maiores onde a enumeração completa era inviável.

5. Significância e Alegações

O artigo posiciona-se não como um método para gerar fronteiras de Pareto ou provar a não-suportabilidade, mas como uma linguagem de verificação reutilizável para candidatos únicos.

• Clareza Semântica: Argumenta que um certificado é incompleto sem domínios de verificação e convenções de escala explícitos. O perfil torna estas escolhas de modelagem explícitas em vez de escondê-las em multiplicadores de magnitude incomparável.
• Utilidade Operacional: A estrutura fornece uma resposta quantitativa a "quão forte é este certificado?" quando o escopo de verificação muda. Transforma a questão qualitativa de reparabilidade em uma estatística computável ($B^*_V$).
• Modéstia: Os autores declaram explicitamente que a contribuição é a montagem de ingredientes clássicos (relaxação lagrangiana, dualidade minimax, programação linear paramétrica) em um objeto de verificação ao nível do candidato. Eles não reivindicam superioridade de tempo de execução universal sobre softwares de geração de fronteira ou garantias de tempo polinomial para o processo de geração de linhas. O resultado é um contrato de certificado específico (perfil, orçamento mínimo e cenário de estresse) em vez de uma estrutura de fronteira global.

O trabalho conclui que certificados de escalarização positiva são inerentemente incompletos sem definições explícitas de domínio e unidade, e o perfil proposto fornece a semântica quantitativa invariante de unidade necessária para completá-los.