| 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 10:24 |
|
