Título: | CONVEX ANALYSIS AND LIFT-AND-PROJECT METHODS FOR INTEGER PROGRAMMING | ||||||||||||
Autor: |
PABLO ANDRES REY |
||||||||||||
Colaborador(es): |
OSCAR PORTO - Orientador CLAUDIA A SAGASTIZABAL - Coorientador |
||||||||||||
Catalogação: | 06/AGO/2001 | Língua(s): | PORTUGUESE - BRAZIL |
||||||||||
Tipo: | TEXT | Subtipo: | THESIS | ||||||||||
Notas: |
[pt] Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio. [en] All data contained in the documents are the sole responsibility of the authors. The data used in the descriptions of the documents are in conformity with the systems of the administration of PUC-Rio. |
||||||||||||
Referência(s): |
[pt] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=1794&idi=1 [en] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=1794&idi=2 [es] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=1794&idi=4 |
||||||||||||
DOI: | https://doi.org/10.17771/PUCRio.acad.1794 | ||||||||||||
Resumo: | |||||||||||||
Algorithms for general 0-1 mixed integer programs can be
successfully developed by using lift-and-project methods to
generate cuts. Cuts are generated by solving a cut-
generation-program that depends on a certain normalization.
From a theoretical point of view, the good numerical
behavior of these cuts is not completely understood yet,
specially, concerning to the normalization chosen. We
consider a general normalization given by an arbitrary
closed convex set, extending the theory developed in the
90's. We present a theoretical framework covering a wide
group of already known normalizations. We also introduce
new normalizations and analyze the properties of the
associated cuts. In this work, we also propose a new
updating rule for the prox parameter of a variant of the
proximal bundle methods, making use of all the information
available at each iteration. Proximal bundle methods are
well known for their efficiency in nondifferentiable
optimization. Finally, we introduce a way to eliminate
redundant solutions ( due to geometrical symmetries ) of
combinatorial integer program. This can be done by using
the information about the problem symmetry in order to
generate inequalities, which added to the formulation of
the problem, eliminate this symmetry without affecting
solution of the integer problem.
|
|||||||||||||
|