Busca avançada
Ano de início
Entree

Otimização em poliedros quase-inteiros

Processo: 07/53616-8
Linha de fomento:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de setembro de 2007
Vigência (Término): 31 de agosto de 2009
Área do 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

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)

Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa:
Matéria(s) publicada(s) em Outras Mídias (0 total):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)