Computing valid inequalities for general integer programs using an extension of maximal dual feasible functions to negative arguments

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.