Column Generation based Primal Heuristics
JONCOUR, Cédric
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
MICHEL, Sophie
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Laboratoire de Mathématiques Appliquées du Havre [LMAH]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Laboratoire de Mathématiques Appliquées du Havre [LMAH]
SADYKOV, Ruslan
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Leer más >
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
JONCOUR, Cédric
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
MICHEL, Sophie
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Laboratoire de Mathématiques Appliquées du Havre [LMAH]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Laboratoire de Mathématiques Appliquées du Havre [LMAH]
SADYKOV, Ruslan
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
SVERDLOV, Dmitry
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
VANDERBECK, François
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
< Leer menos
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Idioma
en
Communication dans un congrès
Este ítem está publicado en
International Symposium on Combinatorial Optimization (ISCO), 2010-03-24, HaMMamet. 2010-03-24, vol. 36, p. 695-702
Resumen en inglés
In the past decade, significant progress has been achieved in developing generic primal heuristics that made their way into commercial mixed integer programming (MIP) solver. Extensions to the context of a column generation ...Leer más >
In the past decade, significant progress has been achieved in developing generic primal heuristics that made their way into commercial mixed integer programming (MIP) solver. Extensions to the context of a column generation solution approach are not straightforward. The Dantzig-Wolfe decomposition principle can indeed be exploited in greedy, local search, rounding or truncated exact methods. The price coordination mechanism can bring a global view that may be lacking in some ''myopic'' approaches based on a compact formulation. However, the dynamic generation of variables requires specific adaptation of heuristic paradigms. The column generation literature reports many application specific studies where primal heuristics are a key to success. There remains to extract generic methods that could be seen as black-box primal heuristics for use across applications. In this paper we review generic classes of column generation based primal heuristics. We then focus on a so-called ''diving'' method in which we introduce diversification based on Limited Discrepancy Search. While being a general purpose approach, the implementation of our heuristic illustrates the technicalities specific to column generation. The method is numerically tested on variants of the cutting stock and vehicle routing problems.< Leer menos
Orígen
Importado de HalCentros de investigación