Solution of constrained generalized transportation problems using the pivot and probe algorithm
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.
- On a nonbasic dual method for the transportation problem
- The pivot and probe algorithm for solving a linear program
- A Treatment of Transportation Problems by Primal Partition Programming
- scientific article; zbMATH DE number 3858851
- Solution of large dense transportation problems using a parallel primal algorithm
- A primal algorithm for solving a capacitated network flow problem with additional linear constraints
- Accelerated Algorithms for Labeling and Relabeling of Trees, with Applications to Distribution Problems
- An operator theory of parametric programming for the generalized transportation problem-III-weight operators
- An operator theory of parametric programming for the generalized transportation problem: I. Basic theory
- An operator theory of parametric programming for the generalized transportation problem: II Rim, cost and bound operators
- An operator theory of parametric programming for the generalized transportation problem—IV—global operators
- Benefit-Cost Analysis of Coding Techniques for the Primal Transportation Algorithm
- Exceptional Paper—Design and Implementation of Large Scale Primal Transshipment Algorithms
- scientific article; zbMATH DE number 3175708 (Why is no real title available?)
- scientific article; zbMATH DE number 3791941 (Why is no real title available?)
- scientific article; zbMATH DE number 3523333 (Why is no real title available?)
- Implementation and computational comparisons of primal, dual and primal-dual computer codes for minimum cost network flow problems
- On the Generalized Transportation Problem
- Solving Constrained Transportation Problems
- Solving embedded generalized network problems
- Solving Generalized Networks
- Solving singularly constrained generalized network problems
- The Dual Method for the Generalized Transportation Problem
- The Generalized Stepping Stone Method for the Machine Loading Model
- The pivot and probe algorithm for solving a linear program
- Network flow problems with one side constraint: A comparison of three solution methods
- Probing through the intersection of hyperplanes
- A pivot generation approach for the classical Hitchcock transportation problem
- Transportation problem with nonlinear side constraints a branch and bound approach
- SMT production scheduling: a generalized transportation approach
- scientific article; zbMATH DE number 912072 (Why is no real title available?)
- The pivot and probe algorithm for solving a linear program
- A survey of dynamic network flows
This page was built for publication: Solution of constrained generalized transportation problems using the pivot and probe algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1820696)
