Column generation for extended formulations

DOI10.1007/S13675-013-0009-9zbMath1305.90312OpenAlexW3023456609MaRDI QIDQ458128

François Vanderbeck, Ruslan Sadykov

Publication date: 30 September 2014

Published in: EURO Journal on Computational Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s13675-013-0009-9

zbMATH Keywords

stabilizationcolumn-and-row generationextended formulations for MIP

Mathematics Subject Classification ID

Mixed integer programming (90C11)

Related Items (9)

Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem ⋮ The multi-trip container drayage problem with synchronization for efficient empty containers re-usage ⋮ Benders decomposition and column-and-row generation for solving large-scale linear programs with column-dependent-rows ⋮ Exact solution of network flow models with strong relaxations ⋮ Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes ⋮ A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching ⋮ Network-Based Approximate Linear Programming for Discrete Optimization ⋮ Arc flow formulations based on dynamic programming: theoretical foundations and applications ⋮ The time buffer approximated buffer allocation problem: a row-column generation approach

Uses Software

• Knapsack
• MCF
• BaPCod

Cites Work

• Unnamed Item
• A stabilized structured Dantzig-Wolfe decomposition method
• A note on branch-and-cut-and-price
• Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems
• 0-1 reformulations of the multicommodity capacitated network design problem
• Partitioning procedures for solving mixed-variables programming problems
• Exact solution of bin-packing problems using column generation and branch-and-bound
• Multicommodity network flows: The impact of formulation on decomposition
• Simultaneous column-and-row generation for large-scale linear programs with column-dependent-rows
• A generic view of Dantzig--Wolfe decomposition in mixed integer programming
• Approximate extended formulations
• Parallel Machine Scheduling by Column Generation
• Vehicle Scheduling in Public Transit and Lagrangean Pricing
• Using Extra Dual Cuts to Accelerate Column Generation
• Time-Indexed Formulations and the Total Weighted Tardiness Problem
• A Decomposition-Based Pricing Procedure for Large-Scale Linear Programs: An Application to the Linear Multicommodity Flow Problem
• Variable Disaggregation in Network Flow Problems with Piecewise Linear Costs
• Polyhedral Characterization of Discrete Dynamic Programming
• Branched Polyhedral Systems
• A Branch and Bound Algorithm for the Total Weighted Tardiness Problem
• A branch-and-cut algorithm for the resource-constrained minimum-weight arborescence problem
• A Minimal Algorithm for the 0-1 Knapsack Problem
• Time-Indexed Formulations for Machine Scheduling Problems: Column Generation
• An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
• Production Planning by Mixed Integer Programming

This page was built for publication: Column generation for extended formulations