Otimização em poliedros quase-inteiros

• Processo: 07/53616-8
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de setembro de 2007
• Data de Término da vigência: 31 de agosto de 2009
• Área de conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Cid Carvalho de Souza
• Beneficiário: Claudia Akemi Furushima
• Instituição Sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Assunto(s): Otimização combinatória Combinatória poliédrica Branch-and-cut Algoritmos
• Palavra(s)-Chave do Pesquisador: Algoritmos Branch-And-Cut | Combinatoria Poliedrica | Otimizacao Combinatoria

Resumo

Considere o problema de Programação Linear Inteira cujas soluções devem satisfazer a $P=\{x \in \bbR?n: Ax \leq b\}$, sendo $\bbB?n$ o conjunto dos vetores binários de dimensão $n$, $A$ uma matriz $(m+1)\times n$ com elementos em $\{0,-1,1\}$ e $b$ um vetor de inteiros. Além disso, suponha que as linhas de $A$ podem ser particionadas de modo que $A=\left[\begin{array}{c}U \\ \pi \end{array} \right]$ sendo $U$ uma matriz totalmente unimodular $m\times n$ e $\pi$ um vetor de $n$ elementos. Suponha ainda que $P$ não corresponda a um poliedro inteiro, i.e., que a restrição adicional leve a um poliedro com pelo menos um vértice fracionário. Neste projeto procurar-se-á encontrar desigualdades válidas fortes para o poliedro $P$ satisfazendo as condições gerais descritas acima, exceto possivelmente pela inclusão de condições especiais sobre o vetor $b$. O objetivo é tentar desenvolver algoritmos do tipo branch-and-cut mais gerais para problemas com grande gama de aplicações, como é o caso dos problemas da partição, da cobertura e do empacotamento. (AU)