Um algoritmo de planos-de-corte para o número cromático fracionário de um grafo

Pesquisa Operacional

Manoel Campêlo²  Victor A. Campos¹  Ricardo C. Corrêa¹ 

[1] ,Universidade Federal do Ceará Dep. de Estatística e Matemática Aplicada Prog. de Mestrado e Doutorado em Ciência da ComputaçãoFortaleza CE ,Brasil

关键词: número cromático;    planos-de-corte;    otimização combinatória;    chromatic number;    cutting planes;    combinatorial optimization;   

DOI  :  10.1590/S0101-74382009000100009

来源: SciELO

【 摘 要 】

O número cromático fracionário χF(G) de um grafo G é um conhecido limite inferior para seu número cromático χ(G). Experimentos relatados na literatura mostram que usar χF(G), em lugar do tamanho da clique máxima, pode ser muito mais eficiente para orientar a busca em um algoritmo tipo branch-and-bound para determinação de χ(G). Uma dificuldade, porém, é tratar o modelo linear conhecido para χF(G), o qual apresenta um número exponencial de variáveis e demanda um caro processo de geração de colunas. Neste trabalho, examinamos uma formulação alternativa para obter um limite inferior para χF(G) que possui um número de variáveis linear no tamanho do grafo, porém um número exponencial de restrições. Utilizamos o método de planos-de-corte para lidar com esse inconveniente. Algumas heurísticas de separação são propostas, e experimentos computacionais mostram que valores muito próximos de χF(G), em muitos casos iguais, são encontrados em tempo inferior à implementação com geração de colunas.

【 授权许可】

CC BY   
 All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License