Worst-case analysis of maximal dual feasible functions

By Rietz, Juergen; Alves, Claudio; Valerio de Carvalho, J. M.

Optimization Letters



Dual feasible functions have been used to compute fast lower bounds and valid inequalities for integer linear problems. In this paper, we analyze the worst-case performance of the lower bounds provided by some of the best functions proposed in the literature. We describe some worst-case examples for these functions, and we report on new results concerning the best parameter choice for one of these functions.


Google Scholar: