Large-scale optimization with the primal-dual column generation method
From MaRDI portal
Abstract: The primal-dual column generation method (PDCGM) is a general-purpose column generation technique that relies on the primal-dual interior point method to solve the restricted master problems. The use of this interior point method variant allows to obtain suboptimal and well-centered dual solutions which naturally stabilizes the column generation. As recently presented in the literature, reductions in the number of calls to the oracle and in the CPU times are typically observed when compared to the standard column generation, which relies on extreme optimal dual solutions. However, these results are based on relatively small problems obtained from linear relaxations of combinatorial applications. In this paper, we investigate the behaviour of the PDCGM in a broader context, namely when solving large-scale convex optimization problems. We have selected applications that arise in important real-life contexts such as data analysis (multiple kernel learning problem), decision-making under uncertainty (two-stage stochastic programming problems) and telecommunication and transportation networks (multicommodity network flow problem). In the numerical experiments, we use publicly available benchmark instances to compare the performance of the PDCGM against recent results for different methods presented in the literature, which were the best available results to date. The analysis of these results suggests that the PDCGM offers an attractive alternative over specialized methods since it remains competitive in terms of number of iterations and CPU times even for large-scale optimization problems.
Recommendations
- A note on the primal-dual column generation method for combinatorial optimization
- New developments in the primal-dual column generation technique
- Dual-Optimal Inequalities for Stabilized Column Generation
- On the choice of explicit stabilizing terms in column generation
- A General Primal-Dual Envelope Method for Convex Programming Problems
Cites work
- scientific article; zbMATH DE number 3169929 (Why is no real title available?)
- scientific article; zbMATH DE number 3177183 (Why is no real title available?)
- scientific article; zbMATH DE number 1332320 (Why is no real title available?)
- scientific article; zbMATH DE number 477581 (Why is no real title available?)
- scientific article; zbMATH DE number 663895 (Why is no real title available?)
- scientific article; zbMATH DE number 1062478 (Why is no real title available?)
- L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming
- A Bundle Type Dual-Ascent Approach to Linear Multicommodity Min-Cost Flow Problems
- A Linear Programming Approach to the Cutting-Stock Problem
- A Version of the Bundle Idea for Minimizing a Nonsmooth Function: Conceptual Idea, Convergence Analysis, Numerical Results
- A bundle-type algorithm for routing in telecommunication data networks
- A computational study of a solver system for processing two-stage stochastic LPs with enhanced Benders decomposition
- A cutting plane method from analytic centers for stochastic programming
- A multicut algorithm for two-stage stochastic linear programs
- A new warmstarting strategy for the primal-dual column generation method
- A note on some analytic center cutting plane methods for convex feasibility and minimization problems
- A note on two problems in connexion with graphs
- A regularized decomposition method for minimizing a sum of polyhedral functions
- A stabilized structured Dantzig-Wolfe decomposition method
- A suggested computation for maximal multi-commodity network flows
- A survey of algorithms for convex multicommodity flow problems
- ACCPM with a nonlinear constraint and an active set strategy to solve nonlinear multicommodity flow problems
- An augmented Lagrangian algorithm for large scale multicommodity routing
- An extended model and a column generation algorithm for the planar multicommodity flow problem
- An interior point method in Dantzig-Wolfe decomposition
- Applications of second-order cone programming
- Boundedness of solutions for an elliptic equation with non-standard growth
- Comparison of bundle and classical column generation
- Complexity Analysis of an Interior Cutting Plane Method for Convex Feasibility Problems
- Complexity of some cutting plane methods that use analytic centers
- Decomposition and Nondifferentiable Optimization with the Projective Algorithm
- Elements of Large-Scale Mathematical Programming Part I: Concepts
- Generalized Bundle Methods
- Implementing Mixed Integer Column Generation
- Improving an interior-point algorithm for multicommodity flows by quadratic regularizations
- Interior point methods 25 years later
- Introduction to Stochastic Programming
- Large scale multiple kernel learning
- Learning the kernel matrix with semidefinite programming
- Multiple kernel learning algorithms
- New developments in the primal-dual column generation technique
- New variants of bundle methods
- On a new collection of stochastic linear programming test problems
- On constrained optimization by adjoint based quasi-Newton methods
- Partitioning procedures for solving mixed-variables programming problems
- Progress Made in Solving the Multicommodity Flow Problem
- Proximal-ACCPM: a versatile oracle based optimisation method
- Proximity control in bundle methods for convex nondifferentiable minimization
- Selected Topics in Column Generation
- SimpleMKL
- Solving Large-Scale Linear Multicommodity Flow Problems with an Active Set Strategy and Proximal-ACCPM
- Solving difficult multicommodity problems with a specialized interior-point algorithm
- Solving nonlinear multicommodity flow problems by the analytic center cutting plane method
- Solving real-world linear ordering problems using a primal-dual interior point cutting plane method
- SpicyMKL: a fast algorithm for multiple kernel learning with thousands of kernels
- Stabilized column generation
- The B<scp>oxstep</scp> Method for Large-Scale Optimization
- The Cutting-Plane Method for Solving Convex Programs
- The Decomposition Algorithm for Linear Programs
- The SHOGUN machine learning toolbox
- Using the primal-dual interior point algorithm within the branch-price-and-cut method
- Warm start of the primal-dual method applied in the cutting-plane scheme
Cited in
(20)- On solving large-scale multistage stochastic optimization problems with a new specialized interior-point approach
- A branch and price algorithm for EOS constellation imaging and downloading integrated scheduling problem
- Projective Cutting-Planes for Robust Linear Programming and Cutting Stock Problems
- A new warmstarting strategy for the primal-dual column generation method
- A note on the primal-dual column generation method for combinatorial optimization
- Consensus-based Dantzig-Wolfe decomposition
- A specialized primal-dual interior point method for the plastic truss layout optimization
- The vehicle allocation problem: alternative formulation and branch-and-price method
- Projective cutting-planes
- Solving large scale optimization problems in the transportation industry and beyond through column generation
- New developments in the primal-dual column generation technique
- Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
- A column generation-based heuristic for the split delivery vehicle routing problem with time windows
- A new interior-point approach for large separable convex quadratic two-stage stochastic problems
- Exact approaches to the robust vehicle routing problem with time windows and multiple deliverymen
- A branch-price-and-cut algorithm for the vehicle routing problem with time windows and multiple deliverymen
- A conjugate direction based simplicial decomposition framework for solving a specific class of dense convex quadratic programs
- Computational aspects of column generation for nonlinear and conic optimization: classical and linearized schemes
- Regularized identification with internal positivity side-information
- Design and implementation of a modular interior-point solver for linear optimization
This page was built for publication: Large-scale optimization with the primal-dual column generation method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q266408)
