An equivalent subproblem relaxation for improving the solution of a class of transportation scheduling problems
type: Item
instance of: scholarly article
title: An equivalent subproblem relaxation for improving the solution of a class of transportation scheduling problems
zbMATH Open document ID: 0536.90061
DOI: 10.1016/0377-2217(84)90015-8
author: Fred Glover
author: Darwin D. Klingman
author: Nancy V. Phillips
published in: European Journal of Operational Research
publication date: 1984-01-01T00:00:00Z
review text: To improve an algorithm by \textit{B. Gavish} and \textit{E. Shlifer} [ibid. 3, 122-134 (1979; Zbl 0392.90055)] for a class of transportation scheduling problems, \textit{G. P. White} [ibid. 9, 190-193 (1982; Zbl 0473.90054)] proposes the use of an alternative subproblem as a relaxation within a branch and bound framework. White's subproblem replaces an assignment problem relaxation used in Gavish and Shlifer's paper [loc. cit.] with a bipartite weighted matching problem, observing that the latter is susceptible to a 'Hungarian-type' of algorithm due to \textit{E. Lawler} [''Combinatorial optimization: Networks and matroids'' (1976; Zbl 0413.90040)]. The purpose of this note is to show that the bipartite weighted matching problem, applying a special case of a result of \textit{A. Charnes, F. Glover} and \textit{D. Klingman} [Nav. Res. Logist. Q. 18, 277-281 (1971; Zbl 0226.90025)], is equivalent to a 'quasi-transportation' problem - i.e., a transportation problem in which exactly one origin and one destination have a non-unit supply and demand. Empirical studies of \textit{F. Glover} and \textit{D. Klingman} [Techn. Rep. 212, Army Office Res., Research Triangle, Durham, NC, USA (1980)] have shown that the quasi- transportation problem can be solved very efficiently by a primal simplex type of code that exploits an alternating path basis structure due to \textit{R. S. Barr, F. Glover} and \textit{D. Klingman} [Eur. J. Oper. Res. 2, 137-144 (1978; Zbl 0376.90068)].
Mathematics Subject Classification ID: 90C08
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 3852790
zbMATH Keywords: primal simplex algorithm
zbMATH Keywords: transportation scheduling
zbMATH Keywords: relaxation
zbMATH Keywords: bipartite weighted matching
zbMATH Keywords: alternating path basis structure
MaRDI profile type: Publication
full work available at URL: 0377-2217(84)90015-8
OpenAlex ID: W2037942733
cites work: The lower bounded and partial upper bounded distribution model
cites work: The alternating basis algorithm for assignment problems
cites work: The generalized alternating path algorithm for transportation problems
cites work: Exceptional Paper—Design and Implementation of Large Scale Primal Transshipment Algorithms
cites work: An approach for solving a class of transportation scheduling problems
cites work: Q4101626
cites work: The traveling-salesman problem and minimum spanning trees: Part II
cites work: A polynomially bounded algorithm for a singly constrained quadratic program
cites work: Q3048571
cites work: Pivot Strategies for Primal-Simplex Network Codes
cites work: An improvement in the Gavish-Shlifer algorithm for a class of transportation scheduling problems
description: scientific article; zbMATH DE number 3852790