A technique for speeding up the solution of the Lagrangean dual

DOI10.1007/BF01582057zbMath0806.90081OpenAlexW1993986344WikidataQ59592629 ScholiaQ59592629MaRDI QIDQ1315429

James B. Orlin, Dimitris J. Bertsimas

Publication date: 19 February 1995

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

Full work available at URL: https://doi.org/10.1007/bf01582057

zbMATH Keywords

Lagrangean relaxationpolynomial algorithmLP relaxationoptimal dual multipliersoptimal solution value

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Combinatorial optimization (90C27)

Related Items

A hybrid approach of bundle and Benders applied large mixed linear integer problem, Minmax combinatorial optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Survivable networks, linear programming relaxations and the parsimonious property
• Matrix multiplication via arithmetic progressions
• A new Lagrangian relaxation approach to the generalized assignment problem
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• Finding minimum-cost flows by double scaling
• Geometric algorithms and combinatorial optimization
• Facets and algorithms for capacitated lot sizing
• A new algorithm for minimizing convex functions over convex sets
• A Cutting Plane Algorithm for the Linear Ordering Problem
• Uncapacitated lot-sizing: The convex hull of solutions
• A Strong Cutting Plane Algorithm for Production Scheduling with Changeover Costs
• Solving 0-1 Integer Programming Problems Arising from Large Scale Planning Models
• Solving Large-Scale Zero-One Linear Programming Problems
• Tailoring Benders decomposition for uncapacitated network design
• Solving Multi-Item Capacitated Lot-Sizing Problems Using Variable Redefinition
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• On the symmetric travelling salesman problem: A computational study
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• Improved Algorithms for Bipartite Network Flow
• A Dual-Ascent Procedure for Large-Scale Uncapacitated Network Design
• Validation of subgradient optimization
• Fast Approximation Algorithms for Fractional Packing and Covering Problems
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II