Avoiding redundant columns by adding classical Benders cuts to column generation subproblems

DOI10.1016/J.DISOPT.2021.100626MaRDI QIDQ2019426zbMATH OpenOpenAlexFDO

Authors Marco E. Lübbecke, Stephen J. Maher, Jonas T. Witt

Publication date 21 April 2021

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2021.100626

zbMATH Keywords

Benders decompositioncolumn generationDantzig-Wolfe reformulationdomain reduction

Mathematics Subject Classification ID

Integer programming (90C10) Mixed integer programming (90C11) Combinatorial optimization (90C27)

Recommendations

• Using extra dual cuts to accelerate column generation
• A Primer in Column Generation
• Row-reduced column generation for degenerate master problems
• Benders decomposition and column-and-row generation for solving large-scale linear programs with column-dependent-rows
• Column generation for extended formulations

Cites work

• A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem
• A generic view of Dantzig--Wolfe decomposition in mixed integer programming
• A horizon decomposition approach for the capacitated lot-sizing problem with setup times
• A Lagrangean-Based Heuristic for Dynamic Multilevel Multiitem Constrained Lotsizing with Setup Times
• A Lagrangian-based heuristic for large-scale set covering problems
• A Primer in Column Generation
• An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts
• An integer optimality condition for column generation on zero-one linear programs
• Branch-and-price: Column generation for solving huge integer programs
• Column generation in the integral simplex method
• Comparing Dantzig-Wolfe decompositions and branch-and-price algorithms for the multi-item capacitated lot sizing problem
• Constraint programming based column generation for crew assignment
• Cost based filtering for the constrained knapsack problem
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 680242 (Why is no real title available?)
• scientific article; zbMATH DE number 4121754 (Why is no real title available?)
• Integral simplex using decomposition for the set partitioning problem
• On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm
• Path-reduced costs for eliminating arcs in routing and scheduling
• Period decompositions for the capacitated lot sizing problem with setup times
• SCIP: solving constraint integer programs
• Selected Topics in Column Generation

Cited in

(1)

• Using extra dual cuts to accelerate column generation

Describes a project that uses

Uses Software

• SCIP
• GCG
• ISUD

This page was built for publication: Avoiding redundant columns by adding classical Benders cuts to column generation subproblems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2019426)