Feasibility Pump Heuristics for Column Generation Approaches
PESNEAU, Pierre
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]
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]
VANDERBECK, François
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]
PESNEAU, Pierre
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]
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]
VANDERBECK, François
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
< Reduce
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Language
en
Communication dans un congrès
This item was published in
11th International Symposium on Experimental Algorithms, 2012-06-07, Bordeaux. 2012-06-07
Springer
English Abstract
Primal heuristics have become an essential component in mixed integer programming (MIP). Generic heuristic paradigms of the literature remain to be extended to the context of a column generation so- lution approach. As the ...Read more >
Primal heuristics have become an essential component in mixed integer programming (MIP). Generic heuristic paradigms of the literature remain to be extended to the context of a column generation so- lution approach. As the Dantzig-Wolfe reformulation is typically tighter than the original compact formulation, techniques based on rounding its linear programming solution have better chance to yield good primal so- lutions. However, the dynamic generation of variables requires specific adaptation of heuristic paradigms. We focus here on "feasibility pump" approaches. We show how such methods can be implemented in a context of dynamically defined variables, and we report on numerically testing "feasibility pump" for cutting stock and generalized assignment prob- lems.Read less <
Origin
Hal imported