Conferência do Prof. Gérard Plateau

Criada em 10/03/2009 21:33 por mmc | Marcadores: evento fen prof

Universidade Federal do Rio de Janeiro
COPPE-Programa de Engenharia de Sistemas e Computação
Instituto de Matemática - DCC
 
Conferencista:Prof. Gérard Plateau
Université Paris 13
Institut Galilée
Laboratoire d'Informatique de Paris-Nord
Dia: 11 de março de 2009 (quarta-feira)
Horário: 14h
Local: sala H-324B do Centro de Tecnologia da UFRJ

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é.

Responsável: Nelson Maculan (maculan@cos.ufrj.br -- tel.:  21. 25628708)


Copie o link desta notícia para compartilhar:


www.eng.uerj.br/noticias/1236731618-Conferencia+do+Prof+Gerard+Plateau




Comente esta notícia

(Para perguntas, verifique acima a forma de contato na notícia)
Seu nome
Seu E-mail (não será divulgado)
Seu comentário
Código de verificação (Repita a sequência abaixo)

Todos os campos são obrigatórios


Regras para comentários:
  • Comentários anônimos serão excluídos;
  • A postagem de comentários com links externos será excluída;
  • Não publicamos denúncias. Nestes casos, você deve encaminhar aos órgãos cabíveis ou indicados na notícia;
  • Comentários que fujam ao teor da matéria serão excluídos;
  • Ofensas e quaisquer outras formas de difamação não serão publicadas;
  • Os autores da notícia não monitoram os comentários, portanto não há garantias que serão lidos e/ou respondidos. Procure a forma de contato na própria notícia

 

Não há comentários ainda.