Solution of constrained generalized transportation problems using the pivot and probe algorithm
type: Item
instance of: scholarly article
title: Solution of constrained generalized transportation problems using the pivot and probe algorithm
zbMATH Open document ID: 0614.90075
DOI: 10.1016/0305-0548(86)90059-6
author: G. L. Thompson
author: Awanti P. Sethi
published in: Computers \& Operations Research
publication date: 1986-01-01T00:00:00Z
full work available at URL: https://figshare.com/articles/journal_contribution/Solution_of_constrained_generalized_transportation_problems_using_the_pivot_and_probe_algorithm/6708035
review text: We use a specialized version of our pivot and probe algorithm to solve generalized transportation problems with side constraints. The dual of an \(m\times n\) generalized transportation problem with t side constraints is a linear program with \(m+n+t\) variables and up to \(m\times n\) constraints. We solve the dual problem using the probe operation to select only the most important constraints to consider. We present computational experience on problems of sizes up to 180\(\times 180\), having various degrees of density and having as many as 10 side constraints. It was found that for a given size and density, problems become harder to solve as the number of side constraints increases. Also, for a fixed number of side constraints, the solution difficulty increases with size and density. We found that our method was able to solve problems of the quoted sizes relatively quickly, with relatively few pivots, and without using basis reinversion.
Mathematics Subject Classification ID: 90C08
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 3995453
zbMATH Keywords: pivot and probe algorithm
zbMATH Keywords: generalized transportation problems
zbMATH Keywords: side constraints
zbMATH Keywords: computational experience
MaRDI profile type: Publication
OpenAlex ID: W2025387250
cites work: An operator theory of parametric programming for the generalized transportation problem: I. Basic theory
cites work: An operator theory of parametric programming for the generalized transportation problem: II Rim, cost and bound operators
cites work: An operator theory of parametric programming for the generalized transportation problem-III-weight operators
cites work: An operator theory of parametric programming for the generalized transportation problem—IV—global operators
cites work: On the Generalized Transportation Problem
cites work: The Dual Method for the Generalized Transportation Problem
cites work: Exceptional Paper—Design and Implementation of Large Scale Primal Transshipment Algorithms
cites work: Solving Generalized Networks
cites work: Q3294638
cites work: A primal algorithm for solving a capacitated network flow problem with additional linear constraints
cites work: The Generalized Stepping Stone Method for the Machine Loading Model
cites work: Implementation and computational comparisons of primal, dual and primal-dual computer codes for minimum cost network flow problems
cites work: Q4101626
cites work: Q3968758
cites work: Solving singularly constrained generalized network problems
cites work: Solving Constrained Transportation Problems
cites work: Solving embedded generalized network problems
cites work: The pivot and probe algorithm for solving a linear program
cites work: Accelerated Algorithms for Labeling and Relabeling of Trees, with Applications to Distribution Problems
cites work: Benefit-Cost Analysis of Coding Techniques for the Primal Transportation Algorithm
description: scientific article; zbMATH DE number 3995453