Universidade Federal do Rio de Janeiro COPPE

Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia

Instituto de Matemática

 
Visualizar Meses
Visualizar Meses
Visualizar Flat
Visualizar Flat
Visualizar Semanas
Visualizar Semanas
Visualizar Dias
Visualizar Dias
Categorias
Categorias
Procurar
Procurar

Evento: 'Palestra: Compact Formulations for the Prize Collecting Steiner Tree Problem'

Eventos PESC (Palestras, Seminários, etc.)
Palestras, Seminários, etc. do PESC/COPPE/UFRJ.
Data: Friday, October 29, 2010 At 11:00
Duração: 2 Horas

Compact Formulations for the Prize Collecting Steiner Tree Problem

Palestrante: Mohamed HAOUARI


Full Professor, Department of Mathematics and Computer Science, National Institute of Applied Sciences and Technology, Tunis, Tunisia.

Data: sexta-feira, 29 de outubro de 2010
Horário: 11:00 horas
Local: sala H-324B, Centro de Tecnologia, UFRJ, Ilha do Fundão

Título:
Compact Formulations for the Prize Collecting Steiner Tree Problem

Abstract:
We investigate a generalized version of prize collecting Steiner tree problem (PCSTP) where each node of a given weighted graph is associated with a prize together with a penalty cost.

The problem is to find a tree spanning a subset of nodes and collecting a total prize not less than a given quota. The objective is to minimize the sum of theweights of the edges in the tree plus the sum of the penalties of those nodes that are not covered by the tree.

We describe several compact mixed-integer programming formulations.These formulations are enhanced through appending valid inequalities, lifting constraints, or reformulating the model using RLT. A theoretical comparison of the relative strength of the associated LP relaxations is described.

Computational experimentscarried out on a large set of benchmark instances provide empirical evidence that a compact fomulation proves capable to provide optimal or very near-optimal solution for large PCSTP instances.

Responsável: Nelson Maculan


Procurar no Calendário

Powered by ExtCalendar 2

© 2017 PESC/COPPE - Programa de Engenharia de Sistemas e Computação

Cidade Universitária, Centro de Tecnologia, Bloco H, Sala 319
Caixa Postal: 68511 CEP: 21941-972 Fones: +55 21 3938-8672 / +55 21 3938-8673 Fax: +55 21 3938-8676
Rio de Janeiro - RJ - Brasil
Horário de atendimento da Secretaria: 2a. a 6a. de 7:00 às 16:00 horas (exceto feriados escolares)