The transportation problem revisited—preprocessing before using the primal–dual algorithm

S Haddadi and O Slimani
Additional contact information
S Haddadi: University of the 8th of May, 1945, Guelma, Algeria
O Slimani: Badji Mokhtar University, Lanos Lab, Annaba, Algeria

Journal of the Operational Research Society, 2012, vol. 63, issue 7, 1006-1009

Abstract: We give a necessary condition for the existence of a feasible solution for the transportation problem through a set of admissible cells, and an algorithm to find a set of admissible cells that satisfies the necessary condition. Either there exists a feasible solution through the admissible cells (which is therefore optimal since the complementary slackness conditions hold) or we could begin using the primal–dual algorithm (PDA) at this point. Our approach has two important advantages: Our O(mn) procedure for updating dual variables takes much less computing time than any procedure for solving a maximum flow problem in the primal phase of the PDA. We are never concerned by the degeneracy problem as we are not seeking basic solutions, but admissible cells. An example is presented for illustrating our approach. We finally provide computational results for a set of 30 randomly generated instances. Comparison of our method with the PDA reveals a real speed up.

Date: 2012
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.palgrave-journals.com/jors/journal/v63/n7/pdf/jors2011106a.pdf Link to full text PDF (application/pdf)
http://www.palgrave-journals.com/jors/journal/v63/n7/full/jors2011106a.html Link to full text HTML (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:pal:jorsoc:v:63:y:2012:i:7:p:1006-1009

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().