ANÁLISE CONVEXA E MÉTODOS LIFT-AND-PROJECT PARA PROGRAMAÇÃO INTEIRA / CONVEX ANALYSIS AND LIFT-AND-PROJECT METHODS FOR INTEGER PROGRAMMING / ANÁLISIS CONVEXA Y MÉTODOS LIFT-AND-PROJECT PARA PROGRAMACIÓN ENTERA

AUTOR(ES)
DATA DE PUBLICAÇÃO

2001

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.

ASSUNTO(S)

otimizacao nao-diferenciavel 0-1 integer programming gauge functions proximal bundle methods support function simetrias lift-and-project disjunctive cuts simetry cortes dijuntivos steiner triple systems lift-and-project sistemas de triplas de steiner non smooth optimization programacao inteira 0-1 funcao suporte funcao gauge metodos de feixes proximais

ACESSO AO ARTIGO

Documentos Relacionados