Academic Journals Database
Disseminating quality controlled scientific knowledge

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

ADD TO MY LIST
 
Author(s): Manoel Campêlo | Victor A. Campos | Ricardo C. Corrêa

Journal: Pesquisa Operacional
ISSN 0101-7438

Volume: 29;
Issue: 1;
Start page: 179;
Date: 2009;
Original page

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

ABSTRACT
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.The fractional chromatic number χF(G) of a graph G is a well-known lower bound for its chromatic number χ(G). Experiments reported in the literature show that using χF(G), instead of the size of the maximum clique, can be much more efficient to drive a search in a branch-and-bound algorithm for finding χ(G). One difficulty though is to deal with the linear program that is known for χF(G). Such a formulation has an exponential number of variables and demands an expensive column generation process. In this work, we investigate the use of an alternative formulation to find a lower bound for χF(G), which has a linear number of variables but an exponential number of constraints. We use a cutting plane method to deal with this inconvenience. Some separation heuristics are proposed, and some computational experiments were carried out. They show that values very close to χF(G) (in many cases exact values) are found in less time than that required by the column generation.
Affiliate Program      Why do you need a reservation system?