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: 'Conferência do Prof. Gérard Plateau, Université Paris 13'

Eventos PESC (Palestras, Seminários, etc.)
Palestras, Seminários, etc. do PESC/COPPE/UFRJ.
Data: Wednesday, March 11, 2009 At 14:00
Duração: 2 Horas

Conferência do Prof. Gérard Plateau, Université Paris 13

Conferencista:
Prof. Gérard Plateau
Université Paris 13
Institut Galilée
Laboratoire d'Informatique de Paris-Nord

Título:
Heuristiques duales pour le sac à dos quadratique avec contrainte de cardinalité

Autores :
Lucas Létocart*, Marie-Christine Plateau** et Gérard Plateau*
*LIPN UMR CNRS 7030, Université Paris 13, Villetaneuse, France
**GDF SUEZ, Direction de la Recherche, Saint Denis La Plaine, France

Resumo :
Le problème du sac à dos avec contrainte de cardinalité (E-kQKP) consiste à maximiser une fonction quadratique soumise à deux contraintes linéaires, l´une portant sur la capacité du sac et l´autre imposant le nombre d´objets à mettre dans le sac. Ce problème est donc une extension du problème du sac à dos quadratique classique dans lequel le nombre d´objets à mettre dans le sac est fixé à k (nombre entier positif).
Ce problème NP-difficile peut être considéré comme non traitable pour des tailles au delà de 40 variables (à partir de 50 variables, un logiciel commercial comme CPLEX 10.2 ne peut résoudre toutes les instances en temps raisonnable, ie. en moins d´une heure de temps de calcul).
L´objet de cet exposé est donc de proposer des heuristiques duales qui engendrent en temps raisonnable, à la fois des bornes inférieures et supérieures sur la valeur du problème. Ainsi, trois types de dualité sont exploitées pour (E-kQKP). Elles sont basées respectivement sur les relaxations Lagrangiennes, semidéfinies et agrégées (surrogate).
De nombreux résultats expérimentaux sur des instances générées aléatoirement montrent l´intérêt de ces nouvelles bornes. Tout particulièrement, les résultats produits par la dualité agrégée (surrogate) allient à la fois qualité et efficacité.

Dia: 11 de março de 2009 (quarta-feira)
Horário: 14h00
Local: sala H-324B do Centro de Tecnologia da UFRJ

Responsável: Nelson Maculan (maculan@cos.ufrj.br)


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)