A carregar...
Publicação
Combining Surrogate Duality with Improving Sequences for Integer Programming
Autores
Orientador(es)
Resumo(s)
Recently a new technique for solving pure integer programming problems has been suggested It consists on building a sequence of Lagrangean duals that progressively reduces the duality gap and, in a finite number of steps, converges to the optimal value of the original problem. The technique has, however, a drawback: to produce a new dual, sometimes, an enumeration step is needed thus deteriorating the performance of the procedure. In this note We study the conditions under which surrogate duality can play a role in helping on this situation. By using some results connecting Lagrangean and surrogate duality in integer programming, we will be able to conclude that a combined Lagrangean-surrogate approach may be helpful in avoiding some enumeration. We give a numerical example of 2 simple problem where such an improvement occurs.
Descrição
Palavras-chave
Contexto Educativo
Citação
Bárcia, P. and Paixão, J., Combining Surrogate Duality with Improving Sequences for Integer Programming (July, 1988). FEUNL Working Paper Series No. 91