A computational evaluation of two subgradient search methods
type: Item
instance of: scholarly article
title: A computational evaluation of two subgradient search methods
zbMATH Open document ID: 0618.90068
DOI: 10.1016/0305-0548(87)90027-X
author: Sanjiv Sarin
author: Mark H. Karwan
published in: Computers \& Operations Research
publication date: 1987-01-01T00:00:00Z
review text: The success of Lagrangean relaxation in discrete optimization is well documented. Part of this success is due to efficient procedures to find (near) optimal Lagrange multipliers, often by the use of subgradient search. This paper presents a comparison of the modified subgradient search technique of \textit{P. M. Camerini, L. Fratta} and \textit{F. Maffioli} [Math. Program. Study 3, 26-34 (1975; Zbl 0357.90031)] and the most widely employed subgradient search procedure. Empirical results in different discrete optimization problems are given and discussed. Cases in which the modified subgradient search procedure is significantly superior and inferior are represented. Both procedures are easily implemented and thus should both be tested in special applications.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 4003913
zbMATH Keywords: Lagrangean relaxation
zbMATH Keywords: optimal Lagrange multipliers
zbMATH Keywords: modified subgradient search
MaRDI profile type: Publication
cites work: The Traveling-Salesman Problem and Minimum Spanning Trees
cites work: The Lagrangian Relaxation Method for Solving Integer Programming Problems
cites work: Q4178782
cites work: A survey of various tactics for generating Lagrangian multipliers in the context of Lagrangian duality
cites work: Validation of subgradient optimization
cites work: Q4133397
cites work: Q3804448
cites work: A Multiplier Adjustment Method for the Generalized Assignment Problem
cites work: Surrogate duality in a branch-and-bound procedure for integer programming
full work available at URL: 0305-0548(87)90027-x
OpenAlex ID: W2000743687
Recommended article: On the computational efficiency of subgradient methods: a case study with Lagrangian bounds
Recommended article: A subgradient method for multiobjective optimization
Recommended article: Q5191905
Recommended article: Numerical performance of subgradient methods in solving nonsmooth optimization problems
Recommended article: An optimal subgradient algorithm with subspace search for costly convex optimization problems
Recommended article: ``Efficient” Subgradient Methods for General Convex Optimization
Recommended article: Computational comparison of two methods for constrained global optimization
Recommended article: A Subgradient Method for Vector Optimization Problems
Recommended article: Q4306792
Recommended article: A Subspace Study on Conjugate Gradient Algorithms
description: scientific article; zbMATH DE number 4003913