Degeneracy in transportation problems
type: Item
instance of: scholarly article
title: Degeneracy in transportation problems
zbMATH Open document ID: 0602.90095
DOI: 10.1016/0166-218X(86)90084-3
published in: Discrete Applied Mathematics
publication date: 1986-01-01T00:00:00Z
review text: The paper provides a systematic study of degeneracy as it appears in transportation problems. First the relationship between the degeneracy and the geometry of a transportation polytope is dicussed. Formulae for the minimum and maximum number of vertices are given. This part presents some new results. In the succeeding discussion the authors develop the basis of a procedure for generating transportation problems with various degree of degeneracy. Two such families of problems were solved using the program GNET (a general purpose transshipment problem solver). Interesting computational experiences and conclusions are also presented.
Mathematics Subject Classification ID: 90C08
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 3972630
zbMATH Keywords: degeneracy
zbMATH Keywords: transportation
zbMATH Keywords: minimum and maximum number of vertices
zbMATH Keywords: general purpose transshipment problem solver
zbMATH Keywords: computational experiences
author: Ming S. Hung
author: Walter O. Rom
author: Allan D. Waren
reviewed by: István Maros
MaRDI profile type: Publication
cites work: The alternating basis algorithm for assignment problems
cites work: Transportation polytopes
cites work: Exceptional Paper—Design and Implementation of Large Scale Primal Transshipment Algorithms
cites work: Some NP-complete problems in linear programming
cites work: A network simplex method
cites work: Theoretical Properties of the Network Simplex Method
cites work: Q3844775
cites work: Q5576685
full work available at URL: 0166-218x(86)90084-3
OpenAlex ID: W1984845663
description: scientific article; zbMATH DE number 3972630