Comparison of bundle and classical column generation

DOI10.1007/s10107-006-0079-zzbMath1152.90005OpenAlexW1984804966MaRDI QIDQ2476993

Yanyan Li

Publication date: 12 March 2008

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-006-0079-z

zbMATH Keywords

Dantzig-Wolfe decompositionLagrangian dualityVolume algorithmNonsmooth convex optimizationBundle algorithmCutting-plane algorithmsStabilized column generation

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Combinatorial optimization (90C27)

Related Items

Large-scale optimization with the primal-dual column generation method, A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple deliverymen, Analytic centre stabilization of column generation algorithm for the capacitated vehicle routing problem, Bin packing and cutting stock problems: mathematical models and exact algorithms, Using the primal-dual interior point algorithm within the branch-price-and-cut method, Exact and heuristic algorithms for order acceptance and scheduling with sequence-dependent setup times, Stabilizing branch‐and‐price for constrained tree problems, Robust ranking and portfolio optimization, An efficient and general approach for the joint order batching and picker routing problem, Newton acceleration on manifolds identified by proximal gradient methods, Lagrangian bounds for large‐scale multicommodity network design: a comparison between Volume and Bundle methods, Polyhedral results and stronger Lagrangean bounds for stable spanning trees, Consensus-based Dantzig-Wolfe decomposition, On the computational efficiency of subgradient methods: a case study with Lagrangian bounds, Incremental Bundle Methods using Upper Models, A tutorial on column generation and branch-and-price for vehicle routing problems, Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes, Asynchronous level bundle methods, A class of Dantzig-Wolfe type decomposition methods for variational inequality problems, Automation and Combination of Linear-Programming Based Stabilization Techniques in Column Generation, Branching in branch-and-price: A generic scheme, On parallelizing dual decomposition in stochastic integer programming, Large-scale unit commitment under uncertainty: an updated literature survey, Decomposition approaches for block-structured chance-constrained programs with application to hydro-thermal unit commitment, A new warmstarting strategy for the primal-dual column generation method, Bundle methods for sum-functions with ``easy components: applications to multicommodity network design, A stabilised scenario decomposition algorithm applied to stochastic unit commitment problems, Searching for optimal integer solutions to set partitioning problems using column generation, Computation of approximate \(\alpha \)-points for large scale single machine scheduling problem, The omnipresence of Lagrange, Regularized decomposition of large scale block-structured robust optimization problems, Ray projection for optimizing polytopes with prohibitively many constraints in set-covering column generation, An inexact bundle variant suited to column generation, \(\varepsilon\)-Constraint method for bi-objective competitive facility location problem with uncertain demand scenario, School bus routing—a column generation approach, On the choice of explicit stabilizing terms in column generation, Chebyshev center based column generation, A note on the primal-dual column generation method for combinatorial optimization, Large-scale unit commitment under uncertainty

Uses Software

• OR-Library
• XPRESS
• CUTGEN1

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An adapted step size algorithm for a 0-1 biknapsack Lagrangean dual
• An inexact bundle variant suited to column generation
• CUTGEN1: A problem generator for the standard one-dimensional cutting stock problem
• Newton's method for convex programming and Tschebyscheff approximation
• Stabilized column generation
• A Cholesky dual method for proximal piecewise linear programming
• Variable metric bundle methods: From conceptual to implementable forms
• The volume algorithm revisited: relation with bundle methods
• Extending Dantzig's bound to the bounded multiple-class binary knapsack problem
• The volume algorithm: Producing primal solutions with a subgradient method
• New variants of bundle methods
• Complexity estimates of some cutting plane methods based on the analytic barrier
• A descent method with linear programming subproblems for nondifferentiable convex optimization
• Ergodic, primal convergence in dual subgradient schemes for convex programming
• Methods of descent for nondifferentiable optimization
• A proximal trust-region algorithm for column generation stabilization
• Optimal Integer Solutions to Industrial Cutting-Stock Problems: Part 2, Benchmark Results
• An Inexact Bundle Approach to Cutting-Stock Problems
• An aggregate subgradient method for nonsmooth convex minimization
• The Cutting-Plane Method for Solving Convex Programs
• A Dual Method for Certain Positive Semidefinite Quadratic Programming Problems
• Decomposition and Nondifferentiable Optimization with the Projective Algorithm
• The B<scp>oxstep</scp> Method for Large-Scale Optimization
• A Column Generation Approach for Graph Coloring
• On constrained optimization by adjoint based quasi-Newton methods
• An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems
• Homogeneous Analytic Center Cutting Plane Methods for Convex Problems and Variational Inequalities
• A dual approach to solving nonlinear programming problems by unconstrained optimization
• Generalized Bundle Methods
• Complexity Analysis of an Interior Cutting Plane Method for Convex Feasibility Problems
• A Proximal Bundle Method with Approximate Subgradient Linearizations
• Convex Analysis
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• The omnipresence of Lagrange