A survey of dual-feasible and superadditive functions |
| |
Authors: | François Clautiaux Cláudio Alves José Valério de Carvalho |
| |
Institution: | 1.LIFL, UMR CNRS 8022,Université des Sciences et Technologies de Lille, INRIA,Villeneuve d’Ascq,France;2.Centro de Investiga??o Algoritmi da Universidade do Minho, Escola de Engenharia,Universidade do Minho,Braga,Portugal |
| |
Abstract: | Dual-feasible functions are valuable tools that can be used to compute both lower bounds for different combinatorial problems
and valid inequalities for integer programs. Several families of functions have been used in the literature. Some of them
were defined explicitly, and others not. One of the main objectives of this paper is to survey these functions, and to state
results concerning their quality. We clearly identify dominant subsets of functions, i.e. those which may lead to better bounds or stronger cuts. We also describe different frameworks that can be used to create
dual-feasible functions. With these frameworks, one can get a dominant function based on other ones. Two new families of dual-feasible
functions obtained by applying these methods are proposed in this paper. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|