Computing maximal dual-feasible functions using a novel approach
Jürgen Rietz, Cláudio Alves, José Valério de Carvalho
Proceedings of the 10o Congreso Galego de Estatística e Investigación de Operacións, ISBN: 978-84-938642-2-4
Pontevedra, Spain, November 2011

ABSTRACT
Dual-feasible functions have been used in the broad area of combinatorial optimization to compute bounds and cutting planes for integer programming problems. These functions have been rediscovered recently, and studied in depth in dierent articles published in the literature. In this paper, we propose a new strategy for building families of staircase maximal dual-feasible functions using the properties of the dual solutions of a related linear programming problem. We describe the foundations of the strategy and we provide an example of a dual-feasible function generated in this way. Our study is completed by a comparison of this function with the best functions proposed in the literature.

BIBTEX ENTRY
@inproceedings{RietzAlvesCarvalhoXCGEIO11,
author = {J{\"u}rgen Rietz and Cl{\'a}udio Alves and Jos{\'e} Val{\'e}rio de Carvalho},
title = {Computing maximal dual-feasible functions using a novel approach},
booktitle = {Proceedings of the 10o Congreso Galego de Estatística e Investigaci{\'o}n de Operaci{\'o}ns},
address = {Pontevedra, Spain},
year = {2011}}