Computing
valid inequalities for general integer programs using an extension of dual
feasible functions to negative arguments
Jürgen Rietz, Cláudio Alves, José Valério de Carvalho, François Clautiaux
Proceedings
of the 1st International Conference on Operations Research and Enterprise
Systems - ICORES 2012
Vilamoura, Portugal, February 2012
ABSTRACT
Dual feasible functions (DFFs) were used with much success to compute bounds for several combinatorial
optimization problems and to derive valid inequalities for some linear integer programs. A major limitation of
these functions is that their domain remains restricted to the set of positive arguments. To tackle more general
linear integer problems, the extension of DFFs to negative arguments is essential. In this paper, we show how
these functions can be generalized to this case. We explore the properties required for DFFs with negative
arguments to be maximal, we analyze additional properties of these DFFs, we prove that many classical
maximal DFFs cannot be extended in this way, and we present some non-trivial examples.
BIBTEX ENTRY
@inproceedings{RietzAlvesCarvalhoClautiauxICORES12,
author = {J{\"u}rgen Rietz and Cl{\'a}udio Alves and Jos{\'e} Val{\'e}rio de Carvalho and Fran\c{c}ois Clautiaux},
title = {Computing
valid inequalities for general integer programs using an extension of dual
feasible functions to negative arguments},
booktitle = {Proceedings
of the 1st International Conference on Operations Research and Enterprise
Systems - ICORES 2012},
address = {Vilamoura, Portugal},
year = {2012}}