Constructing general dual-feasible functions

By Rietz, J.; Alves, C.; de Carvalho, J. V.; Clautiaux, F.

Operations Research Letters



Dual-feasible functions have proved to be very effective for generating fast lower bounds and valid inequalities for integer linear programs with knapsack constraints. However, a significant limitation is that they are defined only for positive arguments. Extending the concept of dual-feasible function to the general domain and range R is not straightforward. In this paper, we propose the first construction principles to obtain general functions with domain and range R, and we show that they lead to non-dominated maximal functions.


Google Scholar: