A generic view of Dantzig--Wolfe decomposition in mixed integer programming

DOI10.1016/j.orl.2005.05.009zbMath1109.90062OpenAlexW2033394039MaRDI QIDQ2494825

François Vanderbeck, Savelsbergh, Martin W. P.

Publication date: 30 June 2006

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2005.05.009

zbMATH Keywords

integer programmingLagrangian relaxationcolumn generationstabilization techniquesDantzig--Wolfe decomposition

Mathematics Subject Classification ID

Mixed integer programming (90C11)

Related Items

Dantzig-Wolfe reformulations for binary quadratic problems, Branch-and-price and constraint programming for solving a real-life technician dispatching problem, Column generation for a UAV assignment problem with precedence constraints, Dantzig-Wolfe decomposition approach to the vehicle assignment problem with demand uncertainty in a hybrid hub-and-spoke network, Consistency Cuts for Dantzig-Wolfe Reformulations, A generalization of column generation to accelerate convergence, Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems, Column generation algorithm for sensor coverage scheduling under bandwidth constraints, Dantzig-Wolfe decomposition for the facility location and production planning problem, A note on ``A LP-based heuristic for a time-constrained routing problem, Decomposition Branching for Mixed Integer Programming, Distributed asynchronous column generation, Application of decomposition techniques in a wildfire suppression optimization model, A tutorial on column generation and branch-and-price for vehicle routing problems, Column generation for extended formulations, Analytics Branching and Selection for the Capacitated Multi-Item Lot Sizing Problem with Nonidentical Machines, Automation and Combination of Linear-Programming Based Stabilization Techniques in Column Generation, Branching in branch-and-price: A generic scheme, Decomposition schemes and acceleration techniques in application to production-assembly-distribution system design, Primal Heuristics for Branch and Price: The Assets of Diving Methods, On LP relaxations for the pattern minimization problem, A new cross decomposition method for stochastic mixed-integer linear programming, A math-heuristic Dantzig-Wolfe algorithm for capacitated lot sizing, A stabilised scenario decomposition algorithm applied to stochastic unit commitment problems, The strength of Dantzig-Wolfe reformulations for the stable set and related problems, Avoiding redundant columns by adding classical Benders cuts to column generation subproblems, Solving capacitated part-routing problems with setup times and costs: a Dantzig-Wolfe decomposition-based solution approach, On a Three-Level Competitive Pricing Problem with Uniform and Mill Pricing Strategies, A Horizon Decomposition Approach for the Capacitated Lot-Sizing Problem with Setup Times, HYBRID CODING PSO-ACO CO-EVOLUTIONARY ALGORITHM FOR SOLVING MIXED-INTEGER PROGRAMMING PROBLEMS, Decomposition of loosely coupled integer programs: a multiobjective perspective, A Computational Investigation on the Strength of Dantzig-Wolfe Reformulations

Cites Work

• A solution approach of production planning problems based on compact formulations for single-item lot-sizing models. (Abstract of thesis)
• Computational study of a column generation algorithm for bin packing and cutting stock problems
• Branch-and-Price: Column Generation for Solving Huge Integer Programs
• Using Extra Dual Cuts to Accelerate Column Generation
• Analysis Of Lagrangian Decomposition For The Multi-Item Capacitated Lot-Sizing Problem
• A New Dantzig-Wolfe Reformulation and Branch-and-Price Algorithm for the Capacitated Lot-Sizing Problem with Setup Times
• Generating Alternative Mixed-Integer Programming Models Using Variable Redefinition
• Preprocessing and Probing Techniques for Mixed Integer Programming Problems
• Time-Indexed Formulations for Machine Scheduling Problems: Column Generation
• On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm
• The General Pickup and Delivery Problem
• Column Generation
• Selected Topics in Column Generation
• Implementing Mixed Integer Column Generation
• New classes of fast lower bounds for bin packing problems
• Unnamed Item
• Unnamed Item