CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design
supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

PDF papers
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. DRC-70-17-83. 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 Content-type: text/plain
last changed 2003/06/02 08:24
pick and add to favorite papersHOMELOGIN (you are user _anon_329463 from group guest) CUMINCAD Papers Powered by SciX Open Publishing Services 1.002