Accession Number:

ADA008358

Title:

Solving Singularly Constrained Transshipment Problems

Descriptive Note:

Research rept.

Corporate Author:

TEXAS UNIV AT AUSTIN CENTER FOR CYBERNETIC STUDIES

Personal Author(s):

• Glover, Fred
• Karney, D.
• Klingman, D.
• Russell, R.

Report Date:

1974-12-01

Pagination or Media Count:

32.0

Abstract:

This paper develops a primal simplex procedure to solve transshipment problems with an arbitrary additional constraint. The procedure incorporates efficient methods for pricing-out the basis, determining representations, and implementing the change of basis. These methods exploit the near triangularity of the basis in order to take full advantage of the computational schemes and list structures used in solving the pure transshipment problem. Also reported is the development of a computer code, IO PNETS-I for solving large scale singularly constrained transshipment problems. This code has demonstrated its efficiency over a wide range of problems and has succeeded in solving a singularly constrained transshipment problem with 3000 nodes and 12,000 variables in less than 5 minutes on a CDC 6600. Additionally, a fast method for determining near optimal integer solutions is also developed. Computational results show that the near optimum integer solution value is usually within a half of one percent of the value of the optimum continuous solution value.

Descriptors:

• *LINEAR PROGRAMMING
• CODING
• COMPUTATIONS
• COMPUTER PROGRAMS
• EFFICIENCY
• NETWORK FLOWS
• NUMBERS
• OPTIMIZATION
• PAPER
• PURITY
• RANGE(EXTREMES)
• SIMPLEX METHOD
• SOLUTIONS(GENERAL)

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE