NDLI: An Investigation of Interior-Point Algorithms for the Linear Transportation Problem

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Jdice, J. Bastos, F. Paixo, J. Portugal, L. Terlaky, T.
Copyright Year	1996
Abstract	Recently, Resende and Veiga [SIAM J. Optim., 3 (1993), pp. 516537] proposed an efficient implementation of the dual affine (DA) interior-point algorithm for the solution of linear transportation models with integer costs and right-hand-side coefficients. This procedure incorporates a preconditioned conjugate gradient (PCG) method for solving the linear system that is required in each iteration of the DA algorithm. In this paper, we introduce an incomplete $QR$ decomposition (IQRD) preconditioning for the PCG algorithm. Computational experience shows that the IQRD preconditioning is appropriate in this instance and is more efficient than the preconditioning introduced by Resende and Veiga. We also show that the primal dual (PD) and the predictor corrector (PC) interior-point algorithms can also be implemented by using the same type of technique. A comparison among these three algorithms is included and indicates that the PD and PC algorithms are more appropriate for the solution of transportation problems with well-scaled cost and right-hand-side coefficients and assignment problems with poorly scaled cost coefficients. On the other hand, the DA algorithm seems to be more efficient for assignment problems with well-scaled cost coefficients and transportation problems whose cost coefficients are badly scaled.
Starting Page	1202
Ending Page	1223
Page Count	22
File Format	PDF
ISSN	10648275
DOI	10.1137/S1064827593258280
e-ISSN	10957197
Issue Number	5
Volume Number	17
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	1996-09-01
Access Restriction	Subscribed
Subject Keyword	preconditioned conjugate gradient methods large-scale problems Special problems of linear programming Iterative methods for linear systems linear transportation models interior-point algorithms Large-scale problems
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computational Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

On Geometrical Properties of Preconditioners in IPMs for Classes of Block-Angular Problems

Element-by-Element Preconditioners for Large Partially Separable Optimization Problems

Quadratic regularizations in an interior-point method for primal block-angular problems

Solving Some Large Scale Semidefinite Programs via the Conjugate Residual Method

New Preconditioners for KKT Systems of Network Flow Problems

Using a Massively Parallel Processor to Solve Large Sparse Linear Programs by an Interior-Point Method

Preconditioning Dense Linear Systems from Large-Scale Semidefinite Programming Problems (1998)

An interior-point approach for primal block-angular problems

An Investigation of the Interior Point Algorithms for the Linear Transportation Problem (1993)

An Investigation of Interior-Point Algorithms for the Linear Transportation Problem

Similar Documents

On Geometrical Properties of Preconditioners in IPMs for Classes of Block-Angular Problems

Element-by-Element Preconditioners for Large Partially Separable Optimization Problems

Quadratic regularizations in an interior-point method for primal block-angular problems

Solving Some Large Scale Semidefinite Programs via the Conjugate Residual Method

New Preconditioners for KKT Systems of Network Flow Problems

Using a Massively Parallel Processor to Solve Large Sparse Linear Programs by an Interior-Point Method

Preconditioning Dense Linear Systems from Large-Scale Semidefinite Programming Problems (1998)

An interior-point approach for primal block-angular problems

An Investigation of the Interior Point Algorithms for the Linear Transportation Problem (1993)

An Investigation of Interior-Point Algorithms for the Linear Transportation Problem