Dual-feasible functions for integer programming and combinatorial optimization: basics, extensions and applications

Abstract

[Extrato] The concept of dual-feasible function (DFF) has been used to improve the resolution of several combinatorial optimization problems involving knapsack inequalities like cutting and packing, scheduling, and vehicle routing problems. DFF were used for the first time by Lueker (1983) to obtain lower bounds for the bin-packing problem. Since then, the main application of DFF was in the computation of lower bounds, even though other applications do exist, as, for instance, the generation of valid inequalities for integer programs (Chvátal 1973).