The Boxstep Method for Large-Scale Optimization

R. E. Marsten
R. E. Marsten
Massachusetts Institute of Technology, Cambridge, Massachusetts
Search for more papers by this author
,
W. W. Hogan
W. W. Hogan
Federal Energy Administration, Washington, D. C.
Search for more papers by this author
,
J. W. Blankenship
J. W. Blankenship
Institute for Defense Analyses, Arlington, Virginia
Search for more papers by this author

R. E. Marsten

Massachusetts Institute of Technology, Cambridge, Massachusetts

Search for more papers by this author

W. W. Hogan

Federal Energy Administration, Washington, D. C.

Search for more papers by this author

J. W. Blankenship

Institute for Defense Analyses, Arlington, Virginia

Search for more papers by this author

Published Online:1 Jun 1975https://doi.org/10.1287/opre.23.3.389

Abstract

A new strategy is presented for large-scale optimization. The Boxstep method creates an algorithmic continuum between feasible-directions methods and cutting-plane methods. Several specific applications are described and computational results are reported.

Cited by
- Solving a multi-horizon stochastic facility location problem with capacity expansion
  2 December 2025 | Computational Management Science, Vol. 23, No. 1
- A branch-and-price algorithm for energy aware task scheduling of constellations of nanosatellites
  Computers & Operations Research, Vol. 185
- Nested Set-Covering/Packing Problem: Degeneracy Alleviation and Dual Stabilization
  Siqi Guo,
  Fan Xiao,
  Zhe Liang
  11 July 2025 | Operations Research, Vol. 73, No. 6
- Solving multi-stage stochastic facility location problems with modular capacity adjustments
  Computers & Operations Research, Vol. 183
- Neural benders decomposition for mixed-integer programming
  12 December 2024 | TOP, Vol. 33, No. 3
- Last fifty years of integer linear programming: A focus on recent practical advances
  European Journal of Operational Research, Vol. 324, No. 3
- Pricing filtering in Dantzig-Wolfe decomposition
  Operations Research Letters, Vol. 58
- Polyak Minorant Method for Convex Optimization
  30 March 2024 | Journal of Optimization Theory and Applications, Vol. 203, No. 3
- Implementation of an oracle-structured bundle method for distributed optimization
  30 November 2023 | Optimization and Engineering, Vol. 25, No. 3
- Stabilized Benders decomposition for energy planning under climate uncertainty
  European Journal of Operational Research, Vol. 316, No. 1
- Multi-period facility location and capacity expansion with modular capacities and convex short-term costs
  Computers & Operations Research, Vol. 163
- Facility Location: A Guide to Modeling and Solving Complex Problem Variants via Lagrangian Relaxation Heuristics
  28 June 2024
- Simplicial decomposition of variational inequalities with multiple nonlinear column generation
  AIMS Mathematics, Vol. 9, No. 6
- Using Lagrangian relaxation to locate hydrogen production facilities under uncertain demand: a case study from Norway
  1 March 2023 | Computational Management Science, Vol. 20, No. 1
- Upward scalable vehicle routing problem of automobile inbound logistics with pickup flexibility
  Transportation Research Part E: Logistics and Transportation Review, Vol. 177
- Assessment of Lagrangean decomposition for short-term planning of integrated refinery-petrochemical operations
  Computers & Chemical Engineering, Vol. 174
- Machine Learning–Supported Prediction of Dual Variables for the Cutting Stock Problem with an Application in Stabilized Column Generation
  Sebastian Kraul,
  Markus Seizinger,
  Jens O. Brunner
  29 March 2023 | INFORMS Journal on Computing, Vol. 35, No. 3
- The p-Lagrangian relaxation for separable nonconvex MIQCQP problems
  22 February 2022 | Journal of Global Optimization, Vol. 84, No. 1
- Application of the Level Method for Computing Locational Convex Hull Prices
  IEEE Transactions on Power Systems, Vol. 37, No. 5
- Stabilized Column Generation Via the Dynamic Separation of Aggregated Rows
  Luciano Costa,
  Claudio Contardo,
  Guy Desaulniers,
  Julian Yarkony
  8 November 2021 | INFORMS Journal on Computing, Vol. 34, No. 2
- Smooth and Flexible Dual Optimal Inequalities
  Naveed Haghani,
  Claudio Contardo,
  Julian Yarkony
  7 October 2021 | INFORMS Journal on Optimization, Vol. 4, No. 1
- Optimizing production capacity and safety stocks in general acyclic supply chains
  Computers & Operations Research, Vol. 120
- Mixed-Integer Linear Optimization: Primal–Dual Relations and Dual Subgradient and Cutting-Plane Methods
  29 February 2020
- Standard Bundle Methods: Untrusted Models and Duality
  29 February 2020
- Exact Branch-Price-and-Cut Algorithms for Vehicle Routing
  Luciano Costa,
  Claudio Contardo,
  Guy Desaulniers
  28 June 2019 | Transportation Science, Vol. 53, No. 4
- Detecting critical node structures on graphs: A mathematical programming approach
  19 September 2018 | Networks, Vol. 73, No. 1
- Unconstrained Optimization
  10 November 2019
- The fixed charge transportation problem: a strong formulation based on Lagrangian decomposition and column generation
  18 May 2018 | Journal of Global Optimization, Vol. 72, No. 3
- Branch-and-Price for the Pickup and Delivery Problem with Time Windows and Scheduled Lines
  Veaceslav Ghilas,
  Jean-François Cordeau,
  Emrah Demir,
  Tom Van Woensel
  29 June 2018 | Transportation Science, Vol. 52, No. 5
- Biomass feedstock supply chain design – a taxonomic review and a decomposition-based methodology
  13 August 2018 | International Journal of Production Research, Vol. 56, No. 17
- Automation and Combination of Linear-Programming Based Stabilization Techniques in Column Generation
  A. Pessoa,
  R. Sadykov,
  E. Uchoa,
  F. Vanderbeck
  15 May 2018 | INFORMS Journal on Computing, Vol. 30, No. 2
- An exact approach to extend network lifetime in a general class of wireless sensor networks
  Information Sciences, Vol. 433-434
- Stabilized column generation for the temporal knapsack problem using dual-optimal inequalities
  14 October 2016 | OR Spectrum, Vol. 39, No. 2
- Integrated Aircraft Routing, Crew Pairing, and Tail Assignment: Branch-and-Price with Many Pricing Problems
  Sebastian Ruther,
  Natashia Boland,
  Faramroze G. Engineer,
  Ian Evans
  9 August 2016 | Transportation Science, Vol. 51, No. 1
- Constraint Aggregation in Column Generation Models for Resource-Constrained Covering Problems
  Daniel Porumbel,
  François Clautiaux
  11 January 2017 | INFORMS Journal on Computing, Vol. 29, No. 1
- Known Concepts and Solution Techniques
  9 November 2016
- Minimizing value-at-risk in single-machine scheduling
  22 June 2016 | Annals of Operations Research, Vol. 248, No. 1-2
- Inexact stabilized Benders’ decomposition approaches with application to chance-constrained problems with finite support
  26 May 2016 | Computational Optimization and Applications, Vol. 65, No. 3
- Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation
  22 December 2015 | Optimization and Engineering, Vol. 17, No. 4
- Integrated short‐term scheduling and production planning in an ethylene plant based on Lagrangian decomposition
  6 July 2016 | The Canadian Journal of Chemical Engineering, Vol. 94, No. 9
- Lower bounding procedure for the asymmetric quadratic traveling salesman problem
  European Journal of Operational Research, Vol. 253, No. 3
- Large-scale optimization with the primal-dual column generation method
  3 September 2015 | Mathematical Programming Computation, Vol. 8, No. 1
- Dual Inequalities for Stabilized Column Generation Revisited
  Timo Gschwind,
  Stefan Irnich
  5 February 2016 | INFORMS Journal on Computing, Vol. 28, No. 1
- Efficient Lagrangian Decomposition Approach for Solving Refinery Production Scheduling Problems Involving Operational Transitions of Mode Switching
  17 June 2015 | Industrial & Engineering Chemistry Research, Vol. 54, No. 25
- Exact approaches for lifetime maximization in connectivity constrained wireless multi-role sensor networks
  European Journal of Operational Research, Vol. 241, No. 1
- Bunker Purchasing in Liner Shipping
  14 December 2014
- A Time-Indexed Generalized Vehicle Routing Model and Stabilized Column Generation for Military Aircraft Mission Planning
- Convex proximal bundle methods in depth: a unified analysis for inexact oracles
  7 September 2014 | Mathematical Programming, Vol. 148, No. 1-2
- A column generation approach to extend lifetime in wireless sensor networks with coverage and connectivity constraints
  Computers & Operations Research, Vol. 52
- Bunker purchasing with contracts
  1 May 2014 | Maritime Economics & Logistics, Vol. 16, No. 4
- Column generation bounds for numerical microaggregation
  18 February 2014 | Journal of Global Optimization, Vol. 60, No. 2
- Integer programming models for the multidimensional assignment problem with star costs
  European Journal of Operational Research, Vol. 235, No. 3
- Lagrangian relaxation based decomposition for well scheduling in shale-gas systems
  Computers & Chemical Engineering, Vol. 63
- Searching for optimal integer solutions to set partitioning problems using column generation
  17 October 2013 | International Transactions in Operational Research, Vol. 21, No. 2
- A hybrid implementation mechanism of tradable network permits system which obviates path enumeration: An auction mechanism with day-to-day capacity control
  Transportation Research Part E: Logistics and Transportation Review, Vol. 60
- A Hybrid Implementation Mechanism of Tradable Network Permits System Which Obviates Path Enumeration: An Auction Mechanism with Day-to-day Capacity Control
  Procedia - Social and Behavioral Sciences, Vol. 80
- Stabilizing branch‐and‐price for constrained tree problems
  20 September 2012 | Networks, Vol. 61, No. 2
- Hybrid Bilevel-Lagrangean Decomposition Scheme for the Integration of Planning and Scheduling of a Network of Batch Plants
  24 January 2013 | Industrial & Engineering Chemistry Research, Vol. 52, No. 5
- New developments in the primal–dual column generation technique
  European Journal of Operational Research, Vol. 224, No. 1
- Column Generation for a Multitrip Vehicle Routing Problem with Time Windows, Driver Work Hours, and Heterogeneous Fleet
  Mathematical Problems in Engineering, Vol. 2013
- Gap Inequalities for the Max-Cut Problem: A Cutting-Plane Algorithm
- On Parallelizing Dual Decomposition in Stochastic Integer Programming
  SSRN Electronic Journal, Vol. 24
- A new Lagrangian decomposition approach applied to the integration of refinery planning and crude-oil scheduling
  Computers & Chemical Engineering, Vol. 35, No. 12
- Chebyshev center based column generation
  Discrete Applied Mathematics, Vol. 159, No. 18
- New Stabilization Procedures for the Cutting Stock Problem
  François Clautiaux,
  Cláudio Alves,
  José Valério de Carvalho,
  Jürgen Rietz,
  2 December 2010 | INFORMS Journal on Computing, Vol. 23, No. 4
- Column Generation
  14 January 2011
- Lagrangean Relaxation-Based Techniques for Solving Facility Location Problems
  13 January 2011
- Stabilized Branch-and-Price for the Rooted Delay-Constrained Steiner Tree Problem
- A tutorial on column generation and branch-and-price for vehicle routing problems
  5 June 2010 | 4OR, Vol. 8, No. 4
- Performances improvement of the column generation algorithm: application to vehicle routing problems
  22 January 2010 | 4OR, Vol. 8, No. 2
- Bibliography
  15 August 2011
- On the choice of explicit stabilizing terms in column generation
  Discrete Applied Mathematics, Vol. 157, No. 6
- Exact and Asymptotically Exact Solutions for a Class of Assortment Problems
  C. Arbib,
  F. Marinelli,
  20 June 2008 | INFORMS Journal on Computing, Vol. 21, No. 1
- An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts
  1 August 2007 | Mathematical Programming, Vol. 115, No. 2
- Comparison of bundle and classical column generation
  12 December 2006 | Mathematical Programming, Vol. 113, No. 2
- The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches
  23 October 2007 | Computational Optimization and Applications, Vol. 40, No. 1
- Accelerating column generation for variable sized bin-packing problems
  European Journal of Operational Research, Vol. 183, No. 3
- Primal-Dual Variable Neighborhood Search for the Simple Plant-Location Problem
  Pierre Hansen,
  Jack Brimberg,
  Dragan Urošević,
  Nenad Mladenović,
  20 July 2007 | INFORMS Journal on Computing, Vol. 19, No. 4
- Interior point stabilization for column generation
  Operations Research Letters, Vol. 35, No. 5
- An extended model and a column generation algorithm for the planar multicommodity flow problem
  16 April 2007 | Networks, Vol. 50, No. 1
- Increasing the Robustness of Boosting Algorithms within the Linear-programming Framework
  24 February 2007 | The Journal of VLSI Signal Processing Systems for Signal, Image, and Video Technology, Vol. 48, No. 1-2
- A column generation approach for the maximal covering location problem
  12 June 2007 | International Transactions in Operational Research, Vol. 14, No. 4
- A branch-and-price algorithm for the capacitated facility location problem
  European Journal of Operational Research, Vol. 179, No. 3
- Stabilized column generation for highly degenerate multiple-depot vehicle scheduling problems
  Computers & Operations Research, Vol. 34, No. 3
- Acceleration of cutting‐plane and column generation algorithms: Applications to network design
  2 October 2006 | Networks, Vol. 49, No. 1
- Searching for Optimal Integer Solutions to Set Partitioning Problems Using Column Generation
  SSRN Electronic Journal, Vol. 33
- A stabilized column generation scheme for the traveling salesman subtour problem
  Discrete Applied Mathematics, Vol. 154, No. 15
- A Trust Region Target Value Method for Optimizing Nondifferentiable Lagrangian Duals of Linear Programs
  9 June 2006 | Mathematical Methods of Operations Research, Vol. 64, No. 1
- Lagrangian duality applied to the vehicle routing problem with time windows
  Computers & Operations Research, Vol. 33, No. 5
- A proximal trust-region algorithm for column generation stabilization
  Computers & Operations Research, Vol. 33, No. 4
- BoxStep methods for crew pairing problems
  Optimization and Engineering, Vol. 7, No. 1
- Selected Topics in Column Generation
  Marco E. Lübbecke,
  Jacques Desrosiers,
  1 December 2005 | Operations Research, Vol. 53, No. 6
- Lower Bounds for the Capacitated Facility Location Problem Based on Column Generation
  Andreas Klose,
  Andreas Drexl,
  1 November 2005 | Management Science, Vol. 51, No. 11
- A branch-and-price approach to p-median location problems
  Computers & Operations Research, Vol. 32, No. 6
- Using Extra Dual Cuts to Accelerate Column Generation
  José M. Valério de Carvalho,
  1 May 2005 | INFORMS Journal on Computing, Vol. 17, No. 2
- A Primer in Column Generation
- Implementing Mixed Integer Column Generation
- Advanced Column Generation Techniques for Crew Pairing Problems
- An Exact Column Generation Approach to the Capacitated Facility Location Problem
- A Robust Linear Programming Based Boosting Algorithm
- A column generation approach to capacitated p-median problems
  Computers & Operations Research, Vol. 31, No. 6
- A column generation procedure for the side constrained traffic equilibrium problem
  Transportation Research Part B: Methodological, Vol. 38, No. 1
- Duty Scheduling in Public Transit
- A relaxação Lagrangeana/surrogate e o método de geração de colunas: novos limitantes e novas colunas
  Pesquisa Operacional, Vol. 23, No. 1
- Abordagens complementares para problemas de p-medianas
  Production, Vol. 13, No. 3
- Lagrangian Relaxation
  19 November 2001
- Pure competition, regulated and Stackelberg equilibria: Application to the energy system of Québec
  European Journal of Operational Research, Vol. 125, No. 1
- The Efficiency of Ballstep Subgradient Level Methods for Convex Optimization
  Krzysztof C. Kiwiel,
  Torbjörn Larsson,
  P. O. Lindberg,
  1 February 1999 | Mathematics of Operations Research, Vol. 24, No. 1
- Stabilized column generation
  Discrete Mathematics, Vol. 194, No. 1-3
- Moving asymptotes and active set strategy for constrained optimization design in magnetostatic problems
  24 June 2005 | International Journal for Numerical Methods in Engineering, Vol. 38, No. 6
- Design of private backbone networks — I: time varying traffic
  European Journal of Operational Research, Vol. 67, No. 3
- The BT-Algorithm for Minimizing a Nonsmooth Functional Subject to Linear Constraints
- A regularized decomposition method for minimizing a sum of polyhedral functions
  Mathematical Programming, Vol. 35, No. 3
- Méthodes de décomposition et décentralisation en programmation linéaire
  29 March 2011 | RAIRO - Operations Research, Vol. 20, No. 4
- A generalized Benders decomposition approach to reactive source planning in power systems
  26 February 2009
- An aggregate subgradient method for nonsmooth convex minimization
  Mathematical Programming, Vol. 27, No. 3
- Surrogate duality relaxation for job shop scheduling
  Discrete Applied Mathematics, Vol. 5, No. 1
- A heuristic decomposition approach to optimal control in a water supply model
  European Journal of Operational Research, Vol. 11, No. 4
- Secant approximation methods for convex optimization
  25 February 2009
- ON A BUNDLE ALGORITHM FOR NONSMOOTH OPTIMIZATION
- A survey of various tactics for generating Lagrangian multipliers in the context of Lagrangian duality
  European Journal of Operational Research, Vol. 3, No. 4
- Nondifferentiable Optimization and Large Scale Linear Programming
- Nondifferentiable optimization and large scale linear programming
- Optimisation non Differentiable: Methodes de Faisceaux
  25 August 2006
- A Survey of Lagrangean Techniques for Discrete Optimization
- UNCONSTRAINED DISCRETE NONLINEAR PROGRAMMING
  Engineering Optimization, Vol. 4, No. 2
- Mathematical - Programming Solution of Optimum Dispatch
- On convergence rates of subgradient optimization methods
  Mathematical Programming, Vol. 13, No. 1
- A dual algorithm for the one-machine scheduling problem
  Mathematical Programming, Vol. 11, No. 1
- An introduction to nonlinear programming—IV Numerical methods for constrained minimization
  Computers & Electrical Engineering, Vol. 3, No. 4
- Approaches to the Cutting Stock Problem
  9 July 2007 | A I I E Transactions, Vol. 8, No. 2
- OPTIMIZATION FOR SPARSE SYSTEMS

Volume 23, Issue 3

May-June 1975

Pages 389-601

Article Information

Metrics

Information

Published Online:June 01, 1975

Cite as

R. E. Marsten, W. W. Hogan, J. W. Blankenship, (1975) The Boxstep Method for Large-Scale Optimization. Operations Research 23(3):389-405.

https://doi.org/10.1287/opre.23.3.389

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

The Boxstep Method for Large-Scale Optimization

Abstract

Volume 23, Issue 3

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News