authors 
Sethi, Awanti P. and Thompson, Gerald L. 
year 
1983 
title 
Solution of Constrained Generalized Transportation Problems Using the Pivot and Probe Algorithm 
source 
17 p. Pittsburgh PA: Design Research Center, CMU, December, 1983. DRC701783. includes bibliography 
summary 
In this paper the authors use a specialized version of their Pivot and Probe algorithm to solve generalized transportation problems with side constraints. The dual of an m x n generalized transportation problem with t side constraints is a linear program with m + n + t variables and up to m x n constraints. They solve the dual problem using the probe operation to select only the most important constraints to consider. Also presented is a computational experience on problems of sizes up to 180 x 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. Ô
h)0*0*0*°°
ÔŒ Also, for a fixed number of side constraints, the solution difficulty increases with size and density. The authors found that their method was able to solve problems of the quoted sizes relatively quickly, with relatively few pivots, and without using basis reinversion 
keywords 
linear programming, topology, planning, constraints, operations research, algorithms, methods 
series 
CADline 
references 
Contenttype: text/plain

last changed 
2003/06/02 08:24 
