Constructing general dual-feasible functions
CLAUTIAUX, François
Université de Bordeaux [UB]
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
< Réduire
Université de Bordeaux [UB]
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Langue
en
Article de revue
Ce document a été publié dans
Operations Research Letters. 2015, vol. 43, n° 4, p. 5
Elsevier
Résumé en anglais
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 ...Lire la suite >
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.< Réduire
Mots clés en anglais
Integer linear programming
Dual-feasible functions
Generalization
Origine
Importé de halUnités de recherche