On compact formulations for integer programs solved by column generation

DOI10.1007/s10479-005-3455-9zbMath1091.90052OpenAlexW2120018445MaRDI QIDQ817199

Jacques Desrosiers, Daniel Villeneuve, Marco E. Lübbecke, François Soumis

Publication date: 7 March 2006

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://depositonce.tu-berlin.de/handle/11303/15493

zbMATH Keywords

integer programmingcolumn generationbranch-and-bound

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items

Using the primal-dual interior point algorithm within the branch-price-and-cut method, A stabilized structured Dantzig-Wolfe decomposition method, Simultaneously exploiting two formulations: an exact Benders decomposition approach, Exact solution of network flow models with strong relaxations, Dantzig-Wolfe decomposition and branch-and-price solving in G12, Branching in branch-and-price: A generic scheme, From High-Level Model to Branch-and-Price Solution in G12, Deriving compact extended formulations via LP-based separation techniques, New exact techniques applied to a class of network flow formulations, A Horizon Decomposition Approach for the Capacitated Lot-Sizing Problem with Setup Times, Cutting planes for branch-and-price algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The shortest path problem with forbidden paths
• A unified approach for price directive decomposition procedures in integer programming
• Exact solution of bin-packing problems using column generation and branch-and-bound
• An exact algorithm for IP column generation
• Branch-and-price algorithms for the one-dimensional cutting stock problem
• LP models for bin packing and cutting stock problems
• Mathematical Methods of Organizing and Planning Production
• Parallel Machine Scheduling by Column Generation
• Branch-and-Price: Column Generation for Solving Huge Integer Programs
• The Preferential Bidding System at Air Canada
• 2-Path Cuts for the Vehicle Routing Problem with Time Windows
• Decomposition Principle for Linear Programs
• A Linear Programming Approach to the Cutting-Stock Problem
• Routing with time windows by column generation
• A Method of Decomposition for Integer Programs
• A Column Generation Approach for Graph Coloring
• A Branch-and-Price Algorithm for the Generalized Assignment Problem
• Solving Parallel Machine Scheduling Problems by Column Generation
• On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm
• Exact Algorithm for Minimising the Number of Setups in the One-Dimensional Cutting Stock Problem