Defesa de Dissertação de Mestrado: André Willik Valenti
Document Actions
Defesa de Dissertação de Mestrado: Claudia Akemi Furushima Porto
Algoritmos para Resolução do Problema de Empacotamento de Conjuntos Utilizando Poliedros Quase Inteiros.
| What | Defesa de Mestrado |
|---|---|
| When |
10/12/2010 from 14:00 to 16:00 |
| Where | Auditório do IC - Sala 85 - IC 2 |
| Add event to calendar |
vCal
iCal
|
Seja $P$ um poliedro, onde $P = \{x \in \bbR^n :Ax \leq \one^m\}$, e $S = P \cap \bbB^n$, sendo $\bbB^n$ o conjunto de vetores bin\'arios de dimensão $n$, $A$ uma matriz de tamanho $m \times n$ e apenas coeficientes com valores em $\{0, 1\}$ e $\one^m$ um vetor de tamanho $m$ com elementos de valor $1$.
Neste trabalho visamos resolver problemas de maximização de uma função de domínio $S$, conhecidos também pelo nome de empacotamento, através de um algoritmo de {\em branch-and-bound} com adição de cortes. A idéia aqui consiste em desmembrá-los em vários subproblemas da forma $P_i = A_i'x \leq \one^{m_i'}$, sendo $\bigcup P_i = P$ e $A_i'$ uma submatriz de $A$ de tamanho $m_i'\times n$, com $m_i' - 1$ linhas formando uma matriz Totalmente Unimodular, no nosso caso uma matriz de Rede pura refletida, e $A'$ uma matriz Quase Totalmente Unimodular .
Sabemos que estes problemas pertencem à classe de problemas NP-difíceis, e portanto tentar resolvê-los em sua otimalidade é uma tarefa árdua, exceto quando as restrições do problemas formam sua própria envoltória convexa. Portanto, com a intenção de encolher o poliedro $P$ e assim tentarmos agilizar a convergência do algoritmo, inserimos alguns planos de corte à instância.
Através do estudo da envoltória convexa definida por uma matriz Quase Totalmente Unimodular, encontramos uma família de desigualdades válidas fortes para $P_i$, e as inserimos. O intuito deste trabalho foi utilizarmos tal estudo para adicionarmos cortes fáceis de serem encontrados e fortes o suficiente para diminuirmos o tempo necessário para obter a solução ótima das instâncias tratadas.
Concurso Público para Professor Doutor - MS-3
